CODEWITHSUNDEEP
pythonmatrixtime-complexity
Patrick_Chong
Patrick_Chong

Reputation: 534

Turning negative entries positive in a matrix by checking adjacent entries- only certain conversions allowed each pass, what's the time complexity?

I am given an (nxm) matrix of positive and negative integers.

The goal is to try and convert all negative numbers into positive ones, and if this is possible, return the number of passes of the matrix required to do this, otherwise return -1.

Here are the rules:

I have written an accepted solution to the problem, but I can't seem to work out the Time Complexity of the solution.

My solution:

  1. Create a Boolean matrix to mark the negative entries that have been turned positive in the current pass (we will reset this matrix after each pass)

  2. Iterate over all entries of the matrix

  3. For every negative number we stumble across check all 4 of its adjacent entries and see if there are any positive entries. If so, convert it to positive and mark it in the boolean matrix.

  4. Increment number of passes each time we iterate over the whole matrix.

  5. We are done when we iterate over the entire matrix and have not made a single change to it (i.e. conversion from negative to positive).

  6. If there are any negative entries left, return -1, otherwise return the number of passes.

I can't seem to think of a worst case- any suggestions on the time complexity of this solution? My initial thought are that it is O(n), where n is the size of the matrix.

For reference, here is my solution:

def minimumPassesOfMatrix(matrix):
    numberOfPasses = 0
    ChangesMade = True

    while ChangesMade:
        negToPosMarket = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        ChangesMade = False
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] < 0:
                    positiveAdjacent = checkAdjacentEntriesForPositive(matrix, row, col, negToPosMarket)
                    if positiveAdjacent:
                        matrix[row][col] *= -1
                        negToPosMarket[row][col] = True
                        ChangesMade = True
        if not ChangesMade:
            break
        numberOfPasses += 1

    if all(matrix[row][col] >= 0 for row in range(len(matrix)) for col in range(len(matrix[0]))):  #notebook double for loop list comp!
        return numberOfPasses

    print(matrix)

    return -1


def checkAdjacentEntriesForPositive(matrix, row, col, negToPosMarket):
    matrixHeight = len(matrix) - 1
    matrixWidth = len(matrix[0]) - 1

    if not OutOfBounds(row + 1, col, matrixHeight, matrixWidth) and not negToPosMarket[row + 1][col]:
        if matrix[row + 1][col] > 0:
            return True
    if not OutOfBounds(row - 1, col, matrixHeight, matrixWidth) and not negToPosMarket[row - 1][col]:
        if matrix[row - 1][col] > 0:
            return True
    if not OutOfBounds(row, col + 1, matrixHeight, matrixWidth) and not negToPosMarket[row][col + 1]:
        if matrix[row][col + 1] > 0:
            return True
    if not OutOfBounds(row, col - 1, matrixHeight, matrixWidth) and not negToPosMarket[row][col - 1]:
        if matrix[row][col - 1] > 0:
            return True

    return False


def OutOfBounds(row, col, matrixHeight, matrixWidth):
    return row < 0 or col < 0 or row > matrixHeight or col > matrixWidth

Upvotes: 0

Views: 160

Answers (1)

Alain T.
Alain T.

Reputation: 42133

The worst case scenario would be a positive number at one corner of the matrix with everything else being negative. This will require (n+m-2) passes to flip the opposite corner. The time complexity would be (n+m)xnxm if you go through every position on each pass.

If you use a set of coordinates instead, this can be reduced to nxm

Place the coordinates of positive values in a set. At each pass convert their negative neighbours to positive and place these former negative's coordinates into a new set for the next pass. This way, you only process each item once.

Here's a example in Python:

def makePos(matrix):
    m = len(matrix)
    n = len(matrix[0])
    plusCoords = {(r,c) for r,row in enumerate(matrix)
                        for c,val in enumerate(row)
                        if val>0} # initial set of + coordinates    
    passes = 0
    iterations = 0
    while plusCoords:      # more passes for new + coordinates
        passes += 1        # count passes
        nextCoords = set() # coordinates of new positives 
        for r,c in plusCoords: # go through this pass's coords
            iterations += 1
            for dr,dc in [(-1,0),(0,-1),(0,1),(1,0)]: # neigbors
                nr,nc = r+dr, c+dc
                if nr not in range(m): continue
                if nc not in range(n): continue
                if matrix[nr][nc] < 0:           # flip to positive
                    nextCoords.add((nr,nc))      # track flips
        for nr,nc in nextCoords:   
            matrix[nr][nc] *= -1         # update matrix
        plusCoords = nextCoords          # coords for next pass
    return passes - 1, iterations

                            # passes
M = [ [10,-1,-1,-1,-1],     # 0 1 2 3 4
      [-1,-1,-1,-1,-1],     # 1 2 3 4 5
      [-1,-1,-1,-1,-1]]     # 2 3 4 5 6 

print(*makePos(M))  # 6 15  (6 passes,15 iterations)

Note that the for dr,dc in [(-1,0),(0,-1),(0,1),(1,0)]: loop counts as O(1) here because it does a fixed amount of work for the r,c coordinates. The nextCoords.add((nr,nc)) function is O(1) because nextCoords is a set.

Upvotes: 1

Related Questions