Maximum Matrix Sum - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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).

MediumArray Greedy Matrix21 min readAsked at: Amazon, Microsoft, Meta +3

Practice this problem

Problem Statement

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
-10⁵ <= matrix[i][j] <= 10⁵

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.

This C solution calculates the absolute sum of the matrix and finds the element with the minimal absolute value. If there's an odd number of negative numbers in the matrix, we subtract twice the minimal absolute to make the total sum maximal, as flipping all negative numbers still requires flipping one more to achieve an even count.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) because we need to iterate over each element in the matrix.
Space Complexity: O(1) as we use a constant amount of additional space.

Try this approach in the editor →

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.

The optimized C version is highly similar to the previous submissions, aiming to calculate the absolute sum through each matrix element while counting negative entries and retrieving the minimum absolute value to handle an odd scenario efficiently for maximal matrix topping-up.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2); the necessity exists in exploring each point.
Space Complexity: O(1); friendly constant load aside typical iteration encapsulation.

Try this approach in the editor →

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).

Code

Python Java C++Go TypeScript Rust JavaScript

Python

Java

C++

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Minimize Overall Negative Signs	Time Complexity: O(n^2) because we need to iterate over each element in the matrix. Space Complexity: O(1) as we use a constant amount of additional space.
Dynamic Adjustment with Parity Check	Time Complexity: O(n^2); the necessity exists in exploring each point. Space Complexity: O(1); friendly constant load aside typical iteration encapsulation.
Greedy	—

Detailed 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.

Video Solution

Maximum Matrix Sum | Simple Thought Process | Leetcode 1975 | codestorywithMIK • codestorywithMIK • 12,448 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Maximum Matrix Sum with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance67.6%

Approaches3

Reading time21 min

Asked at

Amazon Microsoft Meta Honeywell Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Minimize Overall Negative Signs

Code

Complexity

Approach 2: Dynamic Adjustment with Parity Check

Code

Complexity

Approach 3: Greedy

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents