Maximum Matrix Sum solution and explanation
Google
9 more videos on this problem
Maximum Matrix Sum | Simple Thought Process | Leetcode 1975 | codestorywithMIKcodestorywithMIK · 18:33 · 12K views
Maximum Matrix Sum - Leetcode 1975 - PythonNeetCodeIO · 16:07 · 10K views
Maximum Matrix Sum | Leetcode 1975Techdose · 12:33 · 2K views
Maximum Matrix Sum | LeetCode 1975 | Greedy Sign Flipping Study Placement · 6:52 · 2K views
1975. Maximum Matrix Sum | Pattern Recognition | GreedyAryan Mittal · 6:42 · 1K views
1975. Maximum Matrix Sum | Leetcode Daily - PythonLeetcode Daily · 7:40 · 1K views
1975. Maximum Matrix Sum (Leetcode Medium)Programming Live with Larry · 8:41 · 818 views
Daily Leetcode #2106: Jan 05, 2026 - 1975. Maximum Matrix SumProgramming Live with Larry · 6:31 · 465 views
Solving LeetCode 1975 Maximum Matrix Sum | Greedy | Adobe Interview QuestionCode Harmony · 15:21 · 414 views
Maximum Matrix Sum | Leetcode 1975 | Multiple Example Dry Runs | Java Code | Developer CoderDeveloper Coder · 15:47 · 230 views
The problem
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
matrixand 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].length2 <= n <= 250-105 <= matrix[i][j] <= 105
Approach overview
Problem Overview: You are given an n x n integer matrix. You can repeatedly choose two adjacent cells and multiply both values by -1. The goal is to maximize the total sum of the matrix after any number of such operations.
The key observation is that every operation flips the sign of exactly two elements. Because flips happen in pairs, the parity of negative numbers across the matrix becomes the only constraint. Once you recognize this, the problem reduces to maximizing the contribution of absolute values while respecting that parity.
Approach 1: Minimize Overall Negative Signs (Greedy, O(n*m) time, O(1) space)
Treat every element by its absolute value and try to make all numbers positive. Iterate through the matrix once, accumulating the sum of abs(value), counting how many elements are negative, and tracking the smallest absolute value seen. If the number of negatives is even, you can flip signs in pairs until all numbers become positive. If the count is odd, one value must remain negative due to the pair-flip constraint. In that case, subtract 2 * minAbs from the total absolute sum so the smallest magnitude element carries the negative sign. This greedy strategy works because keeping the smallest magnitude negative minimizes the loss in total sum. The algorithm simply scans the matrix once and performs constant-time updates.
Approach 2: Dynamic Adjustment with Parity Check (Greedy reasoning, O(n*m) time, O(1) space)
This method frames the same insight using a running adjustment strategy. While iterating through the grid, maintain three pieces of state: the cumulative absolute sum, the number of negative elements, and the smallest absolute value encountered. After the traversal, evaluate the parity of the negative count. An even count means every element can effectively be turned positive through valid adjacent flips. An odd count forces exactly one negative to remain, so the optimal configuration is the total absolute sum minus twice the smallest absolute value. This formulation highlights the parity constraint explicitly and mirrors how many interview candidates reason through the problem using greedy logic over a grid traversal.
Recommended for interviews: The greedy parity approach is what interviewers expect. It shows you recognized that adjacency operations effectively allow sign propagation across the grid, reducing the problem to counting negatives and tracking the minimum absolute value. A brute-force simulation of sign flips would be unnecessarily complex. Demonstrating the parity insight and finishing with a single pass over the matrix signals strong problem‑solving instincts.
Approach 1: Minimize Overall Negative Signs
To maximize the sum of the matrix, we should aim to minimize the negative influence. Notice that flipping any pair of adjacent elements will keep the number of negative elements consistent in terms of parity (even or odd). Therefore, the key is to ensure the sum of the negative values is minimized while keeping the matrix's parity even, allowing us to theoretically flip elements to achieve a positive parity. It implies that to maximize the sum, the total count of negative numbers should remain even by flipping the sign of the element with the smallest absolute value.
def maxMatrixSum(matrix):
n = len(matrix)
min_abs = abs(matrix[0][0])
sum_ = 0
neg_count = 0
for i in range(n):
for j in range(n):
if matrix[i][j] < 0:
neg_count += 1
sum_ += abs(matrix[i][j])
min_abs = min(min_abs, abs(matrix[i][j]))
if neg_count % 2 != 0:
sum_ -= 2 * min_abs
return sum_public class MaxMatrixSum {
public int maxMatrixSum(int[][] matrix) {
int n = matrix.length;
int minAbs = Math.abs(matrix[0][0]);
int sum = 0;
int negCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] < 0) negCount++;
sum += Math.abs(matrix[i][j]);
minAbs = Math.min(minAbs, Math.abs(matrix[i][j]));
}
}
if (negCount % 2 != 0) {
sum -= 2 * minAbs;
}
return sum;
}
}#include <vector>
#include <cmath>
using namespace std;
int maxMatrixSum(vector<vector<int>>& matrix) {
int n = matrix.size();
int minAbs = abs(matrix[0][0]);
int sum = 0;
int negCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] < 0) negCount++;
sum += abs(matrix[i][j]);
minAbs = min(minAbs, abs(matrix[i][j]));
}
}
if (negCount % 2 != 0) {
sum -= 2 * minAbs;
}
return sum;
}function maxMatrixSum(matrix) {
let n = matrix.length;
let minAbs = Math.abs(matrix[0][0]);
let sum = 0;
let negCount = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] < 0) negCount++;
sum += Math.abs(matrix[i][j]);
minAbs = Math.min(minAbs, Math.abs(matrix[i][j]));
}
}
if (negCount % 2 !== 0) {
sum -= 2 * minAbs;
}
return sum;
}#include <stdio.h>
#include <stdlib.h>
int maxMatrixSum(int** matrix, int n) {
int minAbs = abs(matrix[0][0]);
int sum = 0;
int negCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] < 0) negCount++;
sum += abs(matrix[i][j]);
if (abs(matrix[i][j]) < minAbs) {
minAbs = abs(matrix[i][j]);
}
}
}
if (negCount % 2 != 0) {
sum -= 2 * minAbs;
}
return sum;
}public class Solution {
public int MaxMatrixSum(int[][] matrix) {
int n = matrix.Length;
int minAbs = Math.Abs(matrix[0][0]);
int sum = 0;
int negCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] < 0) negCount++;
sum += Math.Abs(matrix[i][j]);
minAbs = Math.Min(minAbs, Math.Abs(matrix[i][j]));
}
}
if (negCount % 2 != 0) {
sum -= 2 * minAbs;
}
return sum;
}
}The Python code follows similar logic, scanning the matrix to determine the total sum and number of negatives, then adjusting by twice the minimum absolute value if negatives are odd to maximize the sum.
Time Complexity: O(n^2) due to iterating through every element in the matrix.
Space Complexity: O(1) as no extra space is required aside from input size constants.
Approach 2: Dynamic Adjustment with Parity Check
This approach further explores the combination of summing absolute values and preserving parity. Since the act of flipping adjacent pairs maintains the overall parity of negatives, the challenge is to manage the balance of signs dynamically while ensuring operations help convert the majority of negative numbers or maintain equilibrium by pairing onto the minimal interference possible.
def maxMatrixSumOptimized(matrix):
n = len(matrix)
min_abs = abs(matrix[0][0])
total_sum = 0
neg_count = 0
for i in range(n):
for j in range(n):
val_abs = abs(matrix[i][j])
total_sum += val_abs
if matrix[i][j] < 0:
neg_count += 1
min_abs = min(min_abs, val_abs)
if neg_count % 2 != 0:
total_sum -= 2 * min_abs
return total_sumpublic class MaximalSum {
public int maxMatrixSumOptimized(int[][] matrix) {
int n = matrix.length;
int minAbsVal = Math.abs(matrix[0][0]);
long totalSum = 0;
int negativeCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int valueAbs = Math.abs(matrix[i][j]);
totalSum += valueAbs;
if (matrix[i][j] < 0) negativeCount++;
minAbsVal = Math.min(minAbsVal, valueAbs);
}
}
if (negativeCount % 2 != 0) {
totalSum -= 2 * minAbsVal;
}
return (int) totalSum;
}
}#include <vector>
#include <cmath>
using namespace std;
int maxMatrixSumOptimized(vector<vector<int>>& matrix) {
int n = matrix.size();
int minAbsVal = abs(matrix[0][0]);
long long totalSum = 0;
int negativeCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int valueAbs = abs(matrix[i][j]);
totalSum += valueAbs;
if (matrix[i][j] < 0) negativeCount++;
minAbsVal = min(minAbsVal, valueAbs);
}
}
if (negativeCount % 2 != 0) {
totalSum -= 2 * minAbsVal;
}
return totalSum;
}function maxMatrixSumOptimized(matrix) {
let n = matrix.length;
let minAbsVal = Math.abs(matrix[0][0]);
let totalSum = 0;
let negativeCount = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
let valueAbs = Math.abs(matrix[i][j]);
totalSum += valueAbs;
if (matrix[i][j] < 0) negativeCount++;
minAbsVal = Math.min(minAbsVal, valueAbs);
}
}
if (negativeCount % 2 !== 0) {
totalSum -= 2 * minAbsVal;
}
return totalSum;
}#include <stdio.h>
#include <stdlib.h>
int maxMatrixSumOptimized(int** matrix, int n) {
int minAbsVal = abs(matrix[0][0]);
long totalSum = 0;
int negativeCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int valueAbs = abs(matrix[i][j]);
totalSum += valueAbs;
if (matrix[i][j] < 0) negativeCount++;
if (valueAbs < minAbsVal) minAbsVal = valueAbs;
}
}
if (negativeCount % 2 != 0) {
totalSum -= 2 * minAbsVal;
}
return totalSum;
}public class Solution {
public int MaxMatrixSumOptimized(int[][] matrix) {
int n = matrix.Length;
int minAbsVal = Math.Abs(matrix[0][0]);
long totalSum = 0;
int negativeCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int valueAbs = Math.Abs(matrix[i][j]);
totalSum += valueAbs;
if (matrix[i][j] < 0) negativeCount++;
minAbsVal = Math.Min(minAbsVal, valueAbs);
}
}
if (negativeCount % 2 != 0) {
totalSum -= 2 * minAbsVal;
}
return (int) totalSum;
}
}Pythons' path again involves a straightforward count alongside an abs sum tally during navigation, adjusting by the minimal absolute if parity from negative numbers ends unequally, ensuring optimal matrix positivity.
Time Complexity: O(n^2), examining collectively.
Space Complexity: O(1), requiring minimum free variables.
Approach 3: Greedy
If there is a zero in the matrix, or the number of negative numbers in the matrix is even, then the maximum sum is the sum of the absolute values of all elements in the matrix.
Otherwise, if there are an odd number of negative numbers in the matrix, there will be one negative number left in the end. We choose the number with the smallest absolute value and make it negative, so that the final sum is maximized.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
function maxMatrixSum(matrix: number[][]): number {
let [s, cnt, mi] = [0, 0, Infinity];
for (const row of matrix) {
for (const x of row) {
if (x < 0) {
++cnt;
}
const y = Math.abs(x);
s += y;
mi = Math.min(mi, y);
}
}
return cnt % 2 === 0 ? s : s - 2 * mi;
}func maxMatrixSum(matrix [][]int) int64 {
var s int64
mi, cnt := 1<<30, 0
for _, row := range matrix {
for _, x := range row {
if x < 0 {
cnt++
x = -x
}
mi = min(mi, x)
s += int64(x)
}
}
if cnt%2 == 0 {
return s
}
return s - int64(mi*2)
}impl Solution {
pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {
let mut s = 0;
let mut mi = i32::MAX;
let mut cnt = 0;
for row in matrix {
for &x in row.iter() {
cnt += if x < 0 { 1 } else { 0 };
let y = x.abs();
mi = mi.min(y);
s += y as i64;
}
}
if cnt % 2 == 0 {
s
} else {
s - (mi as i64 * 2)
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Minimize Overall Negative Signs | Time Complexity: O(n^2) due to iterating through every element in the matrix. |
| Dynamic Adjustment with Parity Check | Time Complexity: O(n^2), examining collectively. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Minimize Overall Negative Signs | O(n*m) | O(1) | Best general solution. Single pass greedy strategy using absolute sum and smallest value tracking. |
| Dynamic Adjustment with Parity Check | O(n*m) | O(1) | Useful when reasoning about parity constraints of negative counts during traversal. |
Frequently asked questions
Is Maximum Matrix Sum easy or hard?
Maximum Matrix Sum is rated Medium on LeetCode. The implementation is simple, but the key challenge is recognizing that pair sign flips only affect the parity of negative numbers, which leads to the greedy solution.
Maximum Matrix Sum Python/Java solution
Python and Java implementations follow the same pattern: iterate through the matrix, accumulate the sum of absolute values, count negatives, and record the smallest absolute value. If negatives are odd, subtract 2 × minAbs from the total before returning the result.
How to solve Maximum Matrix Sum in O(n)?
Flatten the matrix conceptually and process each element once. Compute the sum of absolute values, count how many numbers are negative, and track the smallest absolute value. If the negative count is odd, subtract twice the smallest absolute value from the total sum. This yields an O(n*m) traversal, which is linear relative to the number of elements.
What is the best approach for Maximum Matrix Sum?
The optimal approach is a greedy strategy that sums absolute values of all elements while tracking the number of negative values and the smallest absolute element. If the count of negatives is even, all values can effectively become positive. If it is odd, subtract twice the smallest absolute value from the total. This runs in O(n*m) time with O(1) extra space.
Is Maximum Matrix Sum asked at Google/Amazon/Meta?
Maximum Matrix Sum appears in interview preparation sets and has been reported in interviews at large tech companies that test greedy reasoning and matrix traversal. Problems like this commonly appear at Amazon, Google, and other companies focusing on algorithmic fundamentals.
What data structure is used in Maximum Matrix Sum?
The problem mainly uses a matrix (2D array) and constant tracking variables such as negative count and minimum absolute value. No advanced data structures are required; the solution relies on greedy reasoning and simple iteration.
What is the time complexity of Maximum Matrix Sum?
The optimal solution runs in O(n*m) time because the algorithm scans every cell of the matrix once. Only constant extra variables are maintained, so the space complexity is O(1).