Scale Engineer

Maximum Matrix Sum

Med
#1800Time: O(N*N). We iterate through the N x N matrix up to three times. Since N is the side length of the matrix, the total number of cells is N*N. Each pass takes O(N*N) time, so the total time complexity is O(N*N).Space: O(1). We only use a few variables to store the counts, sums, and flags, which does not depend on the input matrix size.1 company
Patterns
Greedy
Data structures
ArrayMatrix
Companies
Honeywell

Prompt

You are given an n x n integer matrix. You can do the following operation any number of times:

  • Choose any two adjacent elements of matrix and multiply each of them by -1.

Two elements are considered adjacent if and only if they share a border.

Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.

 

Example 1:

Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.

Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.

 

Constraints:

  • n == matrix.length == matrix[i].length
  • 2 <= n <= 250
  • -105 <= matrix[i][j] <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the key observation that any two elements in the matrix can have their signs flipped together. This is because an operation on adjacent cells (a, b) can be combined with an operation on (b, c) to flip a and c, leaving b unchanged. This implies we can move a pair of sign flips to any two cells. Consequently, the parity of the count of negative numbers is an invariant. We can make all numbers positive if and only if the initial count of negative numbers is even. If it's odd, one number must remain negative. To maximize the sum, this should be the number with the smallest absolute value. A zero in the matrix allows us to flip any single number's sign (by pairing it with the zero), effectively changing the parity and allowing all numbers to become non-negative. This approach calculates the necessary components in separate passes over the matrix.

Algorithm

  • First Pass: Iterate through the n x n matrix to count the number of negative elements (neg_count) and to check if a zero exists (has_zero).
  • Second Pass: Iterate through the matrix again to calculate the sum of the absolute values of all elements (total_sum).
  • Conditional Third Pass: If neg_count is odd and has_zero is false, iterate through the matrix a third time to find the minimum absolute value among all elements (min_abs).
  • Result Calculation:
    • If neg_count is even or has_zero is true, the result is total_sum.
    • Otherwise, the result is total_sum - 2 * min_abs.

Walkthrough

This method systematically gathers the required information by iterating over the matrix multiple times. Each pass has a distinct responsibility, making the logic clear and separated.

First, we determine the parity of negative numbers and the existence of a zero. Then, we calculate the total potential sum by summing up all absolute values. Finally, if necessary, we make a third pass to find the minimum absolute value to calculate the penalty for having an odd number of negatives without a zero. This separation of concerns can make the code easier to read and debug for some, despite being less performant.

class Solution {    public long maxMatrixSum(int[][] matrix) {        int n = matrix.length;        int negCount = 0;        boolean hasZero = false;                // First pass: count negatives and check for zeros        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (matrix[i][j] < 0) {                    negCount++;                }                if (matrix[i][j] == 0) {                    hasZero = true;                }            }        }                long totalSum = 0;        // Second pass: calculate sum of absolute values        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                totalSum += Math.abs(matrix[i][j]);            }        }                if (negCount % 2 == 0 || hasZero) {            return totalSum;        } else {            // Third pass: find minimum absolute value            long minAbs = Long.MAX_VALUE;            for (int i = 0; i < n; i++) {                for (int j = 0; j < n; j++) {                    minAbs = Math.min(minAbs, Math.abs(matrix[i][j]));                }            }            return totalSum - 2 * minAbs;        }    }}

Complexity

Time

O(N*N). We iterate through the N x N matrix up to three times. Since N is the side length of the matrix, the total number of cells is N*N. Each pass takes O(N*N) time, so the total time complexity is O(N*N).

Space

O(1). We only use a few variables to store the counts, sums, and flags, which does not depend on the input matrix size.

Trade-offs

Pros

  • The logic is correct and guaranteed to find the maximum sum.

  • The separation of passes makes the purpose of each part of the code very explicit and easy to follow.

Cons

  • Less efficient than a single-pass solution as it traverses the matrix multiple times.

  • The code is slightly more verbose due to the separated loops.

Solutions

class Solution { public long maxMatrixSum ( int [][] matrix ) { long s = 0 ; int cnt = 0 ; int mi = Integer . MAX_VALUE ; for ( var row : matrix ) { for ( var v : row ) { s += Math . abs ( v ); mi = Math . min ( mi , Math . abs ( v )); if ( v < 0 ) { ++ cnt ; } } } if ( cnt % 2 == 0 || mi == 0 ) { return s ; } return s - mi * 2 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem