Entry for Jan 5th, 2026.
IfihanMotion™1 started a Leetcode wave after solving problems every day last year. She’s an exceptional person, and I’m glad we work together on multiple projects (one of which is @sdsaprogram2).
Anyway, I took a look at today’s Leetcode problem and I thought it was interesting. Faced some weird corners that make problem-solving fun, so I wrote about it.
Initially, I was confused about whether to apply the operations directly or not. I was confused about how applying the operations directly will converge since I could apply the operations countless times. But that was a signal to think about something else.
“Apply countless times” means that we can move the sign to anywhere we want in the matrix. We also have two possible cases
- Even negatives
- Odd negatives
The simple idea is that if we have even negatives in the matrix, we can eventually get rid of all of them. But if we have odd, then one of the numbers in the matrix needs to hold the negative value.
So initial approach was
- Get total sum of absolute values (to know the max value possible from the matrix)
- Keep track of the number of negative values we’ve seen
- If we’ve seen negative values keep track of the max negative value (aka the negative value closest to zero)
- Then after looping through the matrix, check if we’ve seen even or odd negatives
- If even, return the max possible sum
- If odd, the remove the absolute value of the max negative value and then add the negative value (which subtracts it, lol)
class Solution {
public long maxMatrixSum(int[][] matrix) {
// minimize negatives in the matrix
// what's a bit confusing is that I can execute the operation any number of times
// what's the max I can get though?
// there are probably paths I can go down and that I should ignore
// how do I converge at a solution? what's the stopping point
// since I know the max, do I just see how close I can get?
// tricky because a lower number now is okay if in the next iteration I'm able
// to get a higher value
// Leetcode hints helped me realize I shouldn't think about applying the operations, but instead think about
// final states. What are the possible final states? No negative value or one negative value. Let's work
// with that.
long maxSum = 0;
long minNeg = 0;
long negCnt = 0;
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[r].length; c++) {
long curr = (long) matrix[r][c];
long abs = Math.abs(curr);
maxSum += abs;
// negative number
if (curr < 0) {
negCnt++;
if (minNeg == 0) {
minNeg = curr;
} else {
// we want the negative number that's closest to zero
// for minimum impact.
minNeg = Math.max(minNeg, curr);
}
}
}
}
if (negCnt % 2 == 0) {
return maxSum;
}
return maxSum - Math.abs(minNeg) + minNeg;
}
}
The problem with the above approach is that it didn’t handle 2 cases
- If we have a zero present and an odd amount of negative values
- If we don’t have a zero present and an odd amount of negative values.
I will later realize that these 2 are the same case, but I treated them differently because I saw the zero error first ( sigh). So, to solve the zero issue, I added the following to the code above
...
long negCnt = 0;
boolean zeroPresent = false;
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[r].length; c++) {
...
if (curr == 0) {
zeroPresent = true;
}
}
...
if (negCnt % 2 == 0 || zeroPresent) {
return maxSum;
}
}
This solved the specific test case Input: [[-1,0,-1],[-2,1,3],[3,2,2]] but failed another that hit number 2 above. So,
the most important idea is that we can move our negative sign to ANY number we want.
- If we have a zero, move the negative to it
- If we don’t have a zero, move the negative to the closest number we have available
So at the end of the day we’ll need to subtract the absolute version of this value we’ve removed from the maxSum and then add the negative value. To adapt this change, we also had to change how we track the min value. Instead of looking for the smallest negative value, we now look for the smallest absolute value in the whole matrix period.
This allows us later to handle the above case like so
return maxSum - (2 * Math.abs(minNeg));
which essentially reads: The smallest absolute value should be removed from the sum and then should be subtracted from what is left.
Final code
class Solution {
public long maxMatrixSum(int[][] matrix) {
long maxSum = 0;
long minNeg = Math.abs(matrix[0][0]);
long negCnt = 0;
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[r].length; c++) {
long curr = (long) matrix[r][c];
maxSum += Math.abs(curr);
if (curr < 0) negCnt++;
minNeg = Math.min(minNeg, Math.abs(matrix[r][c]));
}
}
if (negCnt % 2 == 0) {
return maxSum;
}
return maxSum - (2 * Math.abs(minNeg));
}
}