algoadvance

Leetcode 3033. Modify the Matrix

Problem Statement

You are given a 2D integer matrix matrix and an integer x. You need to return a new matrix such that every element in the new matrix is the sum of all elements in the original matrix except the ones that are in the same row or in the same column as the original element.

Here is a more formal description:

Clarifying Questions

  1. Are there any constraints on the size of the matrix or the values within the matrix?
    • To formulate an efficient solution, understanding constraints help in optimizing the logic and data structure usage.
  2. Are there any performance guarantees or expectations?
    • Knowing the expected maximum size can help in choosing approaches that best fit expected use cases.
  3. Should the function modify the original matrix in-place or return a new one?
    • This can affect the choice in how memory is managed.
  4. How are edge cases (like empty matrices or single-element matrices) handled?
    • Edge case handling ensures robustness in different scenarios.

Code

#include <vector>
#include <numeric>
#include <iostream>

std::vector<std::vector<int>> modifyMatrix(const std::vector<std::vector<int>>& matrix, int x) {
    int rows = matrix.size();
    if (rows == 0) return {};
    int cols = matrix[0].size();
    if (cols == 0) return {};
    
    // Calculate the sum of each row and each column
    std::vector<int> rowSum(rows, 0), colSum(cols, 0);
    int totalSum = 0;
    
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            rowSum[i] += matrix[i][j];
            colSum[j] += matrix[i][j];
            totalSum += matrix[i][j];
        }
    }
    
    // Create the resulting matrix
    std::vector<std::vector<int>> result(rows, std::vector<int>(cols, 0));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            // Subtract the sum of current row and column, then add back the current element as it's excluded twice
            result[i][j] = totalSum - rowSum[i] - colSum[j] + matrix[i][j];
        }
    }
    
    return result;
}

// Function for printing the matrix (for debugging purposes)
void printMatrix(const std::vector<std::vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    std::vector<std::vector<int>> result = modifyMatrix(matrix, 0);
    
    printMatrix(result);
    
    return 0;
}

Strategy

  1. Sum Calculation:
    • Calculate the total sum of the matrix.
    • Calculate the sum of each row and each column.
  2. Matrix Transformation:
    • For each element in the matrix, compute the desired value by subtracting the sum of the row and column it belongs to from the total sum and then adding back the element itself (since it was subtracted twice).
  3. Edge Case Handling:
    • Include checks for empty rows or columns to ensure the function handles such cases properly.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI