1975. Maximum Matrix Sum LeetCode Solution

In this guide, you will get 1975. Maximum Matrix Sum LeetCode Solution with the best time and space complexity. The solution to Maximum Matrix Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Matrix Sum solution in C++
Maximum Matrix Sum solution in Java
Maximum Matrix Sum solution in Python
Additional Resources

1975. Maximum Matrix Sum LeetCode Solution image

Problem Statement of Maximum Matrix Sum

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(1)

1975. Maximum Matrix Sum LeetCode Solution in C++

class Solution {
 public:
  long long maxMatrixSum(vector<vector<int>>& matrix) {
    long absSum = 0;
    int minAbs = INT_MAX;
    // 0 := even number of negatives
    // 1 := odd number of negatives
    int oddNeg = 0;

    for (const vector<int>& row : matrix)
      for (const int num : row) {
        absSum += abs(num);
        minAbs = min(minAbs, abs(num));
        if (num < 0)
          oddNeg ^= 1;
      }

    return absSum - oddNeg * minAbs * 2;
  }
};
/* code provided by PROGIEZ */

1975. Maximum Matrix Sum LeetCode Solution in Java

class Solution {
  public long maxMatrixSum(int[][] matrix) {
    long absSum = 0;
    int minAbs = Integer.MAX_VALUE;
    // 0 := even number of negatives
    // 1 := odd number of negatives
    int oddNeg = 0;

    for (int[] row : matrix)
      for (final int num : row) {
        absSum += Math.abs(num);
        minAbs = Math.min(minAbs, Math.abs(num));
        if (num < 0)
          oddNeg ^= 1;
      }

    return absSum - oddNeg * minAbs * 2;
  }
}
// code provided by PROGIEZ

1975. Maximum Matrix Sum LeetCode Solution in Python

class Solution:
  def maxMatrixSum(self, matrix: list[list[int]]) -> int:
    absSum = 0
    minAbs = math.inf
    # 0 := even number of negatives
    # 1 := odd number of negatives
    oddNeg = 0

    for row in matrix:
      for num in row:
        absSum += abs(num)
        minAbs = min(minAbs, abs(num))
        if num < 0:
          oddNeg ^= 1

    return absSum - oddNeg * minAbs * 2
 # code by PROGIEZ