Minimum Passes On Matrix

Question 1

Define the main question

Answer 1

Write a function that takes in an integer matrix of potentially unequal height and width and returns the minimum number of passes required to convert all negative integers in the matrix to positive integers.

A negative integer in the matrix can only be converted to a positive integer if one or more of its adjacent elements is positive. An adjacent element is an element that is to the left, to the right, above, or below the current element in the matrix. Converting a negative to a positive simply involves multiplying it by -1

Note that the 0 value is neither positive nor negative, meaning that a 0 can’t convert an adjacent negative to a positive.

A single pass through the matrix involves converting all the negative integers that can be converted at a particular point in time.

Question 2

Sample Input:

matrix = [
[0, -1, -3, 2, 0],
[1, -2, -5 -1, -3],
[3, 0, 0, -4, -1], ]

Answer 2

Output:

3

Question 3

Hint 1

Answer 3

The brute-force approach to solving this problem is to simply iterate through the entire matrix, find all positive values, and change their negative neighbors to positive. You then repeat this process until no more negative neighbors exist. This approach works, but it doesn’t run in an optimal time complexity; can you think of a another way to solve this?

Question 4

Hint 2

Answer 4

The approach discussed in Hint #1 has you look at the same elements in the matrix multiple times. How can you ensure that you never process the same
element more than once?

Question 5

Hint 3

Answer 5

Once a positive value has been found and you change its neighbors to positives, this positive value can no longer lead to the conversion of any more negative values. Instead, its neighbors (that you just changed to positives) have the possibility of changing their own neighbors to positives. After you change a negative value to positive, you should store its position so that you can check if it can flip any of its neighbors in the next pass of the matrix.

Can something similar to a breadth-first search help you do this?

Question 6

Hint 4

Answer 6

You can solve this problem in 0(w * h) time, where w and h are the width and height of the matrix, by implementing a breadth-first search, starting from all the positive-value positions in the array. Initialize a queue that stores the positions of all positive values, iterate through the queue, dequeue elements out, and consider all of their neighbors.

If any of their neighbors are negative, change them to positive, and store their positions in a secondaryqueue. Once the first queue is empty, increment your number of passes, and iterate through the second queue you created (the one with the positions of
negatives that were changed to positives).

Repeat this process until no values are converted during a pass.

Question 7

HInt 5

Answer 7

The approach discussed in Hint #4 can work using either one or two queues. If you decide to use only one queue, you’ll need to differentiate the values that were already positive when the current pass started from the values that were changed to positive during the current pass.

Question 8

Define the main function of Solution 1:

Answer 8

def **minimumPassesOfMatrix**(matrix):
_passes_ = **convertNegatives** (matrix)
 return _passes_ - 1 if not **containsNegative**(matrix) else -1

Question 9

Define the time and space complexity of Solution 1

Answer 9

0(W \* h) time | 0(w \* h) space - where w is the 
# width of the matrix and h is the height

Question 10

Define the convertNegatives()

Answer 10

def **convertNegatives** (matrix) :
 nextPassQueue=getAllPositivePositions(matrix)
_passes_ = 0

while len(nextPassQueue) \> 0:
 currentPassQueue = nextPassQueue
 nextPassQueue = []

while len (currentPassQueue) > 0: <>

passes += 1

return passes

Question 11

Define the While-Loop Structure of the ConvertNegatives()

Answer 11

while len(nextPassOueue) \> 0:
 currentPassQueue = nextPassQueue
 nextPassOueue = []

while len(currentPassQueue) > 0:

In Python, popping elements from the start of a list is an O(n)-time operation. To make this an 0(1)-time operation, we could use the “deque’ object. For our time complexity analysis, we’ll assume this runs in 0(1) time. Also, for this particular solution (Solution #1), we could actually just turn this queue into a stack and replace pop(e) with the constant-time pop() operation.

currentRow, currentCol = currentPassQueue.pop(0)

adjacentPositions = getAdjacentPositions (currentRow, currentCol, matrix)
for position in adjacentPositions:
row, col = position

value = matrix[row] [col]
if value < 0:
matrix[row] [col] *= - 1
nextPassQueue.append ( [row, coll)

Question 12

Define getAllPositivePositions()

Answer 12

def **getAllPositivePositions** (*matrix*) :
_positivePositions_ = []

for row in range (len(matrix)):
for col in range (len(matrix[row])) :
value = matrix [row] [col]

if value > 0:
positivePositions.append ([row, col])
return positivePositions

Question 13

Define getAdjacentPositions()

Answer 13

def getAdjacentPositions (*row*, *col*, *matrix*) :
_adjacentPositions_ = []

if row > 0:
adjacentPositions. append ([row - 1, col] )
if row < len(matrix) - 1:
adjacentPositions.append( [row + 1, col] )
if col > 0:
adjacentPositions.append ([row, col - 1] )
if col < len (matrix [0] ) - 1:
adjacentPositions.append ( [row, col + 1] )

return adjacentpositions

Question 14

Define ContainsNegative()

Answer 14

def containsNegative(matrix):
for row in matrix:
for value in row:
if value < 0:
return True
return False