Maximum Matrix Sum
Problem Description
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
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.
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
The goal here is to turn negative numbers into positive ones to get the highest sum possible. Since operations are constrained to pairs of adjacent elements, it’s important to make the best use of these flips. Let’s see how we can approach this to get the maximum sum!
Optimal Approach
Intuition
To maximize the sum of the matrix, let’s first imagine the best-case scenario: what if all the numbers in the matrix were positive? In that case, we’d get the highest sum possible. Since we can flip adjacent pairs of numbers by multiplying them by -1, we could theoretically turn all the numbers positive. So, we begin by calculating the sum of the absolute values of all the elements. This would represent the maximum sum if we could make all the numbers positive.
Now, there’s a catch. If there is an odd number of negative elements, we can’t flip them all to positive because one negative will remain. This leads us to a simple rule: if there’s an even number of negative elements, we can flip all of them to positive. However, if there’s an odd number, one element has to stay negative, which means we can’t achieve the ideal sum.
To minimize the effect of that remaining negative number, we should aim to make it the smallest value in the matrix. As we calculate the sum of the absolute values, we also keep track of the smallest absolute value. If we end up with an odd number of negative elements, we’ll subtract twice this smallest absolute value from the sum. This ensures that we’re making the best possible adjustment to account for the unavoidable negative number, leaving us with the highest sum we can achieve.
Why Subtract the minimum negative twice?
Imagine that we want all elements in the matrix to be positive, as it would give us the highest possible sum. But when there is an odd number of negative elements, we can't flip them all to positive. One negative will always remain.
Now, the minimum negative number (the smallest negative number) is the one that we ideally want to flip to positive, but we can't. So, in the initial step when we calculate the sum using absolute values, we're essentially treating that negative number as though it were positive, which is not correct.
To correct this, we need to "remove" the positive addition of that number and make it negative again, since it couldn't be flipped. To do this:
- We subtract it once to remove its positive contribution.
- To make it negative again, we subtract it a second time.
So, subtracting it twice ensures that we effectively adjust for the smallest negative number, keeping the sum as high as possible given that we have one remaining negative element.
Approach
Step 1: Initialize Variables
We begin by setting up three variables. totalSum is initialized to 0, which will store the sum of the absolute values of all elements in the matrix. Next, minAbsVal is set to INT_MAX to track the smallest absolute value encountered in the matrix. Finally, negativeCount is initialized to 0 to keep a count of the negative numbers in the matrix.
Step 2: Traverse the Matrix
We then traverse the matrix row by row. For each row, we process each element val. The absolute value of val is added to totalSum to compute the total sum of absolute values. If val is negative, we increment negativeCount to record its occurrence. Simultaneously, minAbsVal is updated to the smaller of its current value and the absolute value of val. This ensures we always have the smallest absolute value stored, which is critical for later adjustments.
Step 3: Adjust the Sum for Odd Negative Count
Once the entire matrix has been traversed, we check if the total count of negative numbers (negativeCount) is odd. If it is odd, we adjust totalSum by subtracting 2 * minAbsVal. This adjustment handles the one negative number that cannot be flipped, ensuring that the final sum remains as large as possible.
Step 4: Return the Result
After the necessary adjustments, the value of totalSum now represents the maximum sum that can be achieved for the matrix. We return this value as the final result.
Dry Run
Input: nums = [[1, 2, 3], [-1, -2, -3], [1, 2, 3]]
Initialization:
totalSum: 0, to store the sum of absolute values of all elements.
minAbsVal: INT_MAX, to track the smallest absolute value.
negativeCount: 0, to count the number of negative elements in the matrix.
Matrix Traversal:
We process the matrix row by row, updating the variables as we go.
Row 1: nums[0] = [1, 2, 3]
- Element 1:
Add abs(1) to totalSum → totalSum = 1.
Update minAbsVal → minAbsVal = min(INT_MAX, 1) = 1.
Element is not negative, so negativeCount remains 0. - Element 2:
Add abs(2) to totalSum → totalSum = 3.
Update minAbsVal → min(1, 2) = 1.
Element is not negative, so negativeCount remains 0. - Element 3:
Add abs(3) to totalSum → totalSum = 6.
Update minAbsVal → min(1, 3) = 1.
Element is not negative, so negativeCount remains 0.
Row 2: nums[1] = [-1, -2, -3]
- Element -1:
Add abs(-1) to totalSum → totalSum = 7.
Update minAbsVal → min(1, 1) = 1.
Element is negative, increment negativeCount → negativeCount = 1. - Element -2:
Add abs(-2) to totalSum → totalSum = 9.
Update minAbsVal → min(1, 2) = 1.
Element is negative, increment negativeCount → negativeCount = 2. - Element -3:
Add abs(-3) to totalSum → totalSum = 12.
Update minAbsVal → min(1, 3) = 1.
Element is negative, increment negativeCount → negativeCount = 3.
Row 3: nums[2] = [1, 2, 3]
- Element 1:
Add abs(1) to totalSum → totalSum = 13.
Update minAbsVal → min(1, 1) = 1.
Element is not negative, so negativeCount remains 3. - Element 2:
Add abs(2) to totalSum → totalSum = 15.
Update minAbsVal → min(1, 2) = 1.
Element is not negative, so negativeCount remains 3. - Element 3:
Add abs(3) to totalSum → totalSum = 18.
Update minAbsVal → min(1, 3) = 1.
Element is not negative, so negativeCount remains 3.
Adjust for Odd Negative Count:
After traversing the entire matrix, negativeCount = 3, which is odd. To maximize the sum, subtract 2 * minAbsVal from totalSum.
totalSum = totalSum - 2 * minAbsVal → totalSum = 18 - 2 * 1 = 16.
Final Output:
The maximum achievable matrix sum is 16.
Return 16.
Code for All Languages
C++
class Solution {
public:
long long maxMatrixSum(vector<vector<int>>& matrix) {
// Initialize variables to store total sum, minimum absolute value, and negative count
long long totalSum = 0;
int minAbsVal = INT_MAX;
int negativeCount = 0;
// Traverse each row of the matrix
for (const auto& row : matrix) {
// Traverse each element in the row
for (int val : row) {
// Add the absolute value of the element to the total sum
totalSum += abs(val);
// Increment negative count if the element is negative
if (val < 0) {
negativeCount++;
}
// Update the smallest absolute value encountered
minAbsVal = min(minAbsVal, abs(val));
}
}
// Adjust the total sum if the count of negative numbers is odd
if (negativeCount % 2 != 0) {
// Subtract twice the smallest absolute value to account
// for the unflippable negative
totalSum -= 2 * minAbsVal;
}
// Return the final computed maximum sum
return totalSum;
}
};Java
class Solution {
public long maxMatrixSum(int[][] matrix) {
// Initialize variables to store total sum,
// minimum absolute value, and negative count
long totalSum = 0;
int minAbsVal = Integer.MAX_VALUE;
int negativeCount = 0;
// Traverse each row of the matrix
for (int[] row : matrix) {
// Traverse each element in the row
for (int val : row) {
// Add the absolute value of the element to the total sum
totalSum += Math.abs(val);
// Increment negative count if the element is negative
if (val < 0) {
negativeCount++;
}
// Update the smallest absolute value encountered
minAbsVal = Math.min(minAbsVal, Math.abs(val));
}
}
// Adjust the total sum if the count of negative numbers is odd
if (negativeCount % 2 != 0) {
// Subtract twice the smallest absolute value to
// account for the unflippable negative
totalSum -= 2 * minAbsVal;
}
// Return the final computed maximum sum
return totalSum;
}
}Python
class Solution:
def maxMatrixSum(self, matrix: List[List[int]]) -> int:
# Initialize variables to store total sum, minimum absolute value, and negative count
totalSum = 0
minAbsVal = float('inf')
negativeCount = 0
# Traverse each row in the matrix
for row in matrix:
# Traverse each element in the row
for val in row:
# Add the absolute value of the element to the total sum
totalSum += abs(val)
# Increment negative count if the element is negative
if val < 0:
negativeCount += 1
# Update the smallest absolute value encountered
minAbsVal = min(minAbsVal, abs(val))
# Adjust the total sum if the count of negative numbers is odd
if negativeCount % 2 != 0:
# Subtract twice the smallest absolute value to account for the unflippable negative
totalSum -= 2 * minAbsVal
# Return the final computed maximum sum
return totalSumJavascript
var maxMatrixSum = function(matrix) {
// Initialize variables to store total sum, minimum absolute value, and negative count
let totalSum = 0;
let minAbsVal = Infinity;
let negativeCount = 0;
// Traverse the matrix row by row
for (let row of matrix) {
// Traverse each element in the row
for (let val of row) {
// Add the absolute value of the element to the total sum
totalSum += Math.abs(val);
// Increment negative count if the element is negative
if (val < 0) {
negativeCount++;
}
// Update the smallest absolute value encountered
minAbsVal = Math.min(minAbsVal, Math.abs(val));
}
}
// Adjust the total sum if the count of negative numbers is odd
if (negativeCount % 2 !== 0) {
// Subtract twice the smallest absolute value to account for the unflippable negative
totalSum -= 2 * minAbsVal;
}
// Return the final computed maximum sum
return totalSum;
};Time Complexity : O(n*m)
Matrix Traversal
For a matrix of size n x m, we traverse each row and column exactly once.
For each element in the matrix, we perform an addition to the total sum, a comparison to update the smallest absolute value, and a check to determine if the element is negative. Each of these operations takes constant time, so traversing all elements in the matrix takes O(n * m) time.
Final Adjustment
After traversal, we check if the negative count is odd and subtract twice the smallest absolute value from the total sum. These are constant-time operations, so this step takes O(1) time.
Overall Time Complexity
The total time complexity is O(n * m).
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space includes the constant number of variables, such as totalSum, minAbsVal, negativeCount, and loop counters, which take O(1) space.
Since no additional data structures are used beyond the input matrix, the auxiliary space complexity is O(1).
Total Space Complexity: O(n * m)
The input matrix nums itself takes O(n * m) space, where n is the number of rows and m is the number of columns. No additional data structures are created, so the total space complexity is dominated by the matrix size.
Thus, the total space complexity is O(n * m).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an m x n integer matrix grid. Return the maximum sum of the elements of an hourglass.
Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:
1) i - k <= r <= i + k,
2) j - k <= c <= j + k, and
3) (r, c) is a valid position in the matrix.