LeetCode 1975: Maximum Matrix Sum Explained | Optimal Solution & Code

by

Problem (rephrased)

You’re given an n x n integer matrix. You may perform the following operation any number of times:

  • Pick two adjacent cells (share an edge) and multiply both values by -1.

Your goal is to maximize the sum of all elements in the matrix.

Key Insight

The operation flips the signs of exactly two adjacent cells.

So, ignoring zeros for a moment:

  • Flipping two numbers changes the count of negative numbers by an even amount (0, 2, or -2).
  • Therefore, the parity (odd/even) of the number of negative elements is an invariant: it does not change.

Why adjacency doesn’t really restrict us

Even though you can only flip adjacent pairs, the grid is connected. Using a path of adjacent flips, you can effectively “transport” a sign flip across the matrix.

A common way to see it:

  • Consider any path between two cells A and B.
  • If you apply the operation along each edge on the path (in order), every internal cell gets flipped twice (cancels out), while only endpoints get flipped once.
  • Net effect: you can flip the signs of any two cells you want, while leaving all others unchanged.

✅ Result: The only real global restriction is parity of negatives (unless there’s a zero, discussed next).

What’s the best possible sum?

Step 1: “Ideal world” — make everything positive

If you could choose signs freely, you’d turn every element into |a[i][j]|, giving: absSum=∑∣aij∣\text{absSum} = \sum |a_{ij}|absSum=∑∣aij​∣

That’s the maximum possible sum of magnitudes.

Step 2: Parity constraint decides if you can reach that ideal

Case A: Number of negatives is even

You can pair up negatives and flip them away (conceptually), so you can make all values non-negative.

✅ Answer = absSum

Case B: Number of negatives is odd

If there is no zero, parity cannot change, meaning:

  • You cannot make all numbers positive.
  • You must leave exactly one number negative.

To maximize the final sum, the negative one should hurt as little as possible → choose the element with the smallest absolute value.

If minAbs = min |a[i][j]|, then leaving -minAbs instead of +minAbs reduces the total by 2 * minAbs: answer=absSum−2⋅minAbs\text{answer} = \text{absSum} – 2 \cdot \text{minAbs}answer=absSum−2⋅minAbs

Case C: There is at least one zero

A zero is special because flipping it doesn’t change it:

  • 0 * (-1) = 0

So if a zero is adjacent (or can be made adjacent through sequences), you can use it to flip the sign of a single element without “paying” a second sign flip effectively affecting parity in the negative-count sense.

Practical takeaway:

  • If there is a 0, you can always achieve the “all non-negative” configuration.

✅ Answer = absSum

Final Formula

Compute:

  • absSum = Σ |a[i][j]|
  • negCount = number of elements < 0
  • minAbs = minimum |a[i][j]|
  • hasZero = any element == 0

Then:

  • If negCount is even or hasZero is true → absSum
  • Else → absSum - 2 * minAbs

Algorithm

  1. Initialize:
    • absSum = 0
    • negCount = 0
    • minAbs = +∞
    • hasZero = false
  2. For each value x in the matrix:
    • absSum += abs(x)
    • if x < 0: negCount++
    • if x == 0: hasZero = true
    • minAbs = min(minAbs, abs(x))
  3. Apply the rule above and return.

Complexity

  • Time: O(n^2) (one pass through the matrix)
  • Space: O(1)
  • Use 64-bit integer (long long / long / Python int) because sums can be large.

Python Implementation

class Solution:
    def maxMatrixSum(self, matrix):
        abs_sum = 0
        neg_count = 0
        min_abs = float("inf")
        has_zero = False

        for row in matrix:
            for x in row:
                if x < 0:
                    neg_count += 1
                if x == 0:
                    has_zero = True

                ax = abs(x)
                abs_sum += ax
                min_abs = min(min_abs, ax)

        if has_zero or neg_count % 2 == 0:
            return abs_sum
        return abs_sum - 2 * min_abs

Common Pitfalls

  • Forgetting zeros: With a zero present, odd negative parity no longer blocks you from reaching absSum.
  • Using 32-bit integers: The sum of absolute values can overflow in languages like C++/Java if you use int.
  • Overthinking adjacency: You don’t need to simulate operations; the parity + min-abs logic is enough.