Problem of The Day: Maximum Matrix Sum

Problem Statement

Intuition

The problem involves maximizing the sum of the elements in a matrix while being allowed to flip the signs of any row or column. The first thought is to leverage the flexibility of sign flipping to ensure that as many negative numbers as possible are converted to positive, as positive numbers contribute more to the sum. However, the signs of the numbers in a column or row affect each other, so care must be taken to minimize the overall effect of negative values.

Approach

1. Sorting Rows:
   • Start by sorting each row of the matrix. This ensures that smaller values (negative or positive) can be easily identified for potential adjustments.

2. Column Adjustment:

   • For every column, check consecutive rows to identify whether their signs are negative. If both are negative, flip their signs to make them positive.

3. Row-wise Adjustment:

   • For each row, calculate the cumulative product of signs and identify the smallest absolute value. Adjust the smallest value in the row based on the cumulative sign to ensure a consistent sign for the row.

4. Global Smallest Adjustment:

   • Identify the globally smallest value in the first column and flip its sign based on the cumulative sign across all rows. This ensures consistency while minimizing the impact of small absolute values.
5. Summation:
   • Compute the total sum of the adjusted matrix, where all adjustments ensure the maximum possible sum.

Complexity

• Time complexity:

  • Sorting each row takes \(O(m \cdot n \log n)\), where \(m\) is the number of rows and \(n\) is the number of columns.
  • Column adjustments take \(O(m \cdot n)\).
  • Overall, the time complexity is approximately \(O(m \cdot n \log n)\).

• Space complexity:

  • The algorithm operates directly on the input matrix, so no additional space is required apart from a few variables, leading to \(O(1)\) space complexity.

Code

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        # Initialize variables
        ROWS = len(matrix)
        COLS = len(matrix[0])
        res = 0

        # Sort each row for easier manipulation
        matrix = [sorted(row) for row in matrix]

        # Adjust signs in columns
        for col in range(COLS):
            for row in range(ROWS - 1):
                if matrix[row][col] < 0 and matrix[row + 1][col] < 0:
                    matrix[row][col] *= -1
                    matrix[row + 1][col] *= -1

        # Adjust signs within each row
        for row in range(ROWS):
            sign = 1
            smallest = float('inf')
            r, c = 0, 0
            for col in range(COLS):
                sign *= (-1 if matrix[row][col] < 0 else 1)
                matrix[row][col] = abs(matrix[row][col])
                if smallest > matrix[row][col]:
                    smallest = matrix[row][col]
                    r, c = row, col

            # Sort row and ensure the smallest value aligns with the sign
            matrix[row] = sorted(matrix[row])
            matrix[row][0] *= sign

        # Global smallest adjustment
        smallest = float('inf')
        sign = 1
        r = 0
        for row in range(ROWS):
            sign *= (1 if matrix[row][0] > 0 else -1)
            matrix[row][0] = abs(matrix[row][0])
            if smallest > matrix[row][0]:
                smallest = matrix[row][0]
                r = row

        matrix[r][0] *= sign

        # Calculate the total sum
        for col in range(COLS):
            for row in range(ROWS):
                res += matrix[row][col]

        return res

Editorial Solution

Approach: Journey From Minus to Plus

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total_sum = 0
        min_abs_val = float("inf")
        negative_count = 0

        for row in matrix:
            for val in row:
                total_sum += abs(val)
                if val < 0:
                    negative_count += 1
                min_abs_val = min(min_abs_val, abs(val))

        # Adjust if the count of negative numbers is odd
        if negative_count % 2 != 0:
            total_sum -= 2 * min_abs_val

        return total_sum

• time: O(m*n)
• space: O(1)