Minimum Passes Of Matrix

Tags

Minimum Passes Of Matrix

Category

Graphs

Difficulty

Medium

Problem Statement

Given a matrix of integers, determine the minimum number of passes required to convert all negative values to positive. In a single pass, every negative value that is adjacent (horizontally or vertically) to a positive value is converted to positive. A pass processes all such conversions simultaneously. If it is not possible to convert all negatives, return -1.

Intuition

This is a multi-source BFS problem. All initially positive values are "sources" that can flip adjacent negatives. In the first pass, all negatives adjacent to the initial positives flip. In the second pass, all negatives adjacent to the newly flipped positives flip, and so on. Each BFS level corresponds to one pass.

This is analogous to the "rotting oranges" problem where positive values spread like an infection.

Approach

  1. Scan the matrix and add all positive value positions to a queue. Count the total number of negatives.
  2. If there are no negatives, return 0.
  3. Perform BFS level by level: a. For each positive in the current queue level, check its four neighbors. b. If a neighbor is negative, flip it to positive, decrement the negative count, and add it to the queue for the next level. c. Increment the pass counter after each level (only if at least one conversion occurred).
  4. After BFS completes, if any negatives remain, return -1. Otherwise, return the number of passes.

Pseudocode

function minimumPassesOfMatrix(matrix):
    queue = []
    negativeCount = 0

    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if matrix[i][j] > 0:
                queue.enqueue((i, j))
            else if matrix[i][j] < 0:
                negativeCount += 1

    if negativeCount == 0:
        return 0

    passes = 0
    while queue is not empty:
        size = length(queue)
        converted = false
        for k from 0 to size - 1:
            (row, col) = queue.dequeue()
            for (newRow, newCol) in neighbors(row, col):
                if inBounds(newRow, newCol) and matrix[newRow][newCol] < 0:
                    matrix[newRow][newCol] = abs(matrix[newRow][newCol])
                    negativeCount -= 1
                    converted = true
                    queue.enqueue((newRow, newCol))
        if converted:
            passes += 1

    if negativeCount > 0:
        return -1
    return passes

Time & Space Complexity

  • Time: O(n * m), where n and m are the dimensions of the matrix. Each cell is enqueued and processed at most once.
  • Space: O(n * m) for the BFS queue in the worst case (e.g., all positive values initially).

Key Insights

  • Multi-source BFS is the key technique: all initial positives are enqueued simultaneously, and BFS levels correspond to passes.
  • Zeros are inert: they are neither converted nor do they convert others.
  • The number of passes equals the number of BFS levels that produce at least one conversion.
  • Negatives that are entirely surrounded by zeros or other negatives (with no path to a positive) can never be converted.

Edge Cases

  • No negatives in the matrix: return 0.
  • No positives in the matrix: return -1 (nothing can trigger conversion).
  • Negatives isolated by zeros from all positives: return -1.
  • Matrix with only zeros: return 0 (no negatives to convert).
  • Single cell matrix: return 0 if positive or zero, -1 if negative (assuming no positive source).

Linked mentions