Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in plain language

The input is a square matrix of integers. One operation chooses two cells that share an edge and reverses both signs. The operation may be repeated any number of times, and the goal is to make the matrix’s total sum as large as possible.

It is tempting to search for a sequence of local flips, but the actual positions of the negative values are a distraction. The answer depends on only three statistics: the sum of every absolute value, the number of negative entries, and the smallest absolute value in the matrix.

Deriving the optimal solution

When the matrix has no zero, each operation changes the negativity of exactly two entries, so the number of negative entries keeps the same parity. A zero changes the situation: negating it still leaves zero, so pairing it with a negative entry can eliminate that one negative without creating another.

To flip any chosen pair of cells, take a path between them and apply the operation to every edge on that path. The two endpoints are flipped once, while every internal cell is flipped twice and returns to its original value. Because every cell in the grid is connected to every other cell, signs can therefore be rearranged in pairs. If one endpoint is zero, the same path construction effectively flips only the other endpoint.

This gives three cases:

  1. If the matrix contains zero, use it as the endpoint paired with any unmatched negative. Every nonzero value can become positive, so the maximum is the sum of all absolute values.
  2. If there is no zero and the number of negative entries is even, the negatives can be paired off and every value can become positive. The maximum is again the sum of all absolute values.
  3. If there is no zero and the number of negative entries is odd, one value must remain negative. To lose as little as possible, leave the value with the smallest absolute value negative. Relative to the all-positive sum, that costs twice its absolute value.

The implementation does not need a separate zero branch. If the negative count is odd and the matrix contains zero, the smallest absolute value is zero, so subtracting twice that value changes nothing.

For example, consider [[1, 2, 3], [-1, -2, -3], [1, 2, 3]]. There are three negative entries, the sum of all absolute values is 18, and the smallest absolute value is 1. One negative sign must remain, so the best possible sum is 18 - 2 * 1 = 16.

The matrix must be scanned once. For an n x n matrix, the algorithm takes O(n^2) time, which is optimal because every entry can affect the answer, and O(1) extra space.

Python solution

from typing import List


class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        """Return the largest sum reachable by flipping adjacent pairs."""
        absolute_sum = 0
        negative_count = 0
        smallest_absolute_value = float("inf")

        for row in matrix:
            for value in row:
                absolute_value = abs(value)
                absolute_sum += absolute_value
                smallest_absolute_value = min(
                    smallest_absolute_value,
                    absolute_value,
                )

                if value < 0:
                    negative_count += 1

        if negative_count % 2 == 1:
            # Without zero, odd parity forces one value to stay negative;
            # with zero, the minimum is zero and the penalty vanishes.
            absolute_sum -= 2 * smallest_absolute_value

        return absolute_sum

Why the algorithm is correct

First suppose the matrix has no zero. Every operation toggles the negativity of two entries, so negative-count parity cannot change. If that parity is even, pair flips can make every entry positive, reaching the sum of all absolute values. If it is odd, every reachable matrix must contain at least one negative entry.

Because a path of edge operations can flip any selected pair of cells, every sign arrangement with the original parity is reachable in this zero-free case. With odd parity, it is therefore possible to make every entry except a chosen one positive. Leaving the smallest-magnitude entry negative subtracts the least possible amount from the all-positive sum: twice that magnitude.

If the matrix contains zero, a path from zero to any selected nonzero cell flips that cell while leaving zero’s value unchanged. Every nonzero entry can therefore become positive, so the sum of all absolute values is reachable. In the code, the smallest absolute value is then zero, and the same formula returns this sum even when the original negative count is odd. The algorithm thus reaches the correct upper bound in every case.

Interview follow-ups

Why is counting negative entries enough when their positions differ?

The grid is connected, and applying operations along a path flips only that path’s two endpoints in the final result. Without zero, this can transform the matrix into any sign pattern with the same negative-count parity. With zero, using it as one endpoint can effectively flip one nonzero entry at a time. Positions affect the operation sequence, but not the maximum sum.

How would the solution change for a rectangular matrix?

It would not change as long as the matrix is nonempty and cells sharing an edge are adjacent. A rectangular grid is still connected, so the same path argument and zero-aware parity cases apply. Scan all m * n entries, then subtract twice the smallest absolute value only when the negative count is odd. The complexity becomes O(mn) time and O(1) extra space.

What if some cells are blocked and the remaining grid is disconnected?

Process every connected component independently. In a component without zero, negative-count parity is invariant, so subtract twice that component’s smallest absolute value when its negative count is odd. A component containing zero has no penalty because its zero can absorb an unmatched flip. A DFS, BFS, or disjoint-set traversal can identify the components in O(V + E) time and O(V) auxiliary space in the general case.

What if the interviewer asks for an explicit sequence of operations?

First choose the final sign pattern. Make every nonzero value positive when the negative count is even or a zero exists; with odd negative count and no zero, leave a minimum-magnitude value negative. Pair the negative cells that must change. If one negative is unmatched and zero exists, pair that negative with the zero. For each pair, choose a grid path and apply the operation along every edge of that path; internal cells flip twice, so only the endpoints change. This constructs a valid sequence, though the number of reported operations can be much larger than the O(n^2) work needed to compute only the maximum sum.

Why does a zero let an odd number of negatives reach the all-positive sum?

Negating zero does not change its value. Apply the operation along a path from an unmatched negative entry to a zero: the negative endpoint becomes positive, every internal cell is flipped twice, and the zero endpoint remains zero. Negative-count parity is therefore not invariant when zero exists. The formula captures the resulting all-nonnegative state automatically because the smallest absolute value is zero, making the penalty 2 * 0 = 0.

Can the matrix be processed as a stream?

Yes. The result needs only the running absolute-value sum, negative count, and smallest absolute value. Rows can be consumed one at a time without retaining the full matrix, so the computation still uses O(1) state beyond the current input chunk. The final answer cannot be emitted until the stream ends because a later entry may introduce either a smaller magnitude or another negative value.

What edge cases should be tested?

Test matrices with no negatives, an even number of negatives, and an odd number of negatives. Include a zero with odd negative parity, repeated minimum magnitudes, all-negative matrices of both parities, and the largest allowed magnitudes to confirm the language’s integer type can hold the total. A 2 x 2 matrix is useful for checking the smallest valid dimensions and hand-verifying reachable sign patterns.