2679. Sum in a Matrix
Problem Description
In this problem, we are provided with a 0-indexed 2D integer array nums
, which represents a matrix. The goal is to calculate a score based on specific operations performed on this matrix. We start with a score of 0
, and we repeatedly perform the following two-part operation until the matrix is empty:
- From each row in the matrix, select and remove the largest number. If any row has multiple largest numbers (i.e., a tie), any of them can be selected.
- After removing these numbers from each row, identify the largest number among them and add that number to the score.
The required output is the final score once there are no more numbers left in the matrix.
It's important to keep track of the largest numbers being selected during each operation and ensuring that the correct value (the maximum from these selections) is added appropriately to the score.
Intuition
The intuition behind the solution comes from the way the operations on the matrix are defined. Since we always need to select the largest number from each row and find the overall maximum to add to the score, sorting the rows can simplify the problem. By sorting each row, we guarantee that the largest number in each row will be at the end.
This operation effectively "flips" the matrix so that each row becomes a column. Then, the algorithm iterates through the new "rows" (original columns) and computes the maximum value. This value is the one that should be added to the score since it represents the largest value that would be selected from the original rows during an iteration.
By continuing to sum these maxima for all "new rows," we accumulate the total score. The benefit of this approach is that the whole process takes place with a complexity close to that of the sorting operation itself, which is efficient compared to a naive approach that might involve multiple iterations for each step.
The use of Python's built-in functions like sort()
, max()
, and map()
allows for a concise and efficient implementation of this intuition.
Learn more about Sorting and Heap (Priority Queue) patterns.
Solution Approach
The implementation of the solution follows the steps that correspond to its intuitive approach described previously. Let's walk through each part of the implementation:
-
Sort each row of the
nums
matrix. In Python, this can be achieved using thesort()
method, which sorts the elements of a list in ascending order. By sorting each row, we ensure that the largest number in each row will be at the end.- This is done with the following line of code:
1for row in nums: 2 row.sort()
- This is done with the following line of code:
-
The next step is to find the largest number that was removed from each row and add that to the score. Since the rows are sorted, we can use the fact that in Python, the
max()
function can be applied to a list of lists by using thezip(*iterables)
function. Thezip(*nums)
effectively transposes the matrix, so the last elements of each original row (which are the largest due to the sort) become the elements of the new "rows."-
This "transposition" and finding the maximum occurs in the following line of code:
1return sum(map(max, zip(*nums)))
-
The
map()
function appliesmax
to each new row (actually a column of the original matrix) and finds the maximum element, which corresponds to the maximum number we removed from the original rows. -
Finally, the
sum()
function takes the iterable produced bymap()
(which consists of the largest numbers from each operation) and sums them up, thus calculating the final score.
-
The combination of sort()
, max()
, zip()
, and map()
provides an elegant and efficient solution. It uses sorting to rearrange the elements, a matrix transpose operation to work across rows as if they were columns, the max()
function to grab the largest values in a straightforward manner, and sum()
to accumulate these values into the final score.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider the following small matrix for our example:
1nums = [ 2 [4, 5, 6], 3 [1, 2, 9], 4 [7, 8, 3] 5]
Let's walk through the steps of the solution approach using this matrix:
-
Sort each row of the
nums
matrix in ascending order:Before sorting:
1[ 2 [4, 5, 6], 3 [1, 2, 9], 4 [7, 8, 3] 5]
After sorting each row:
1[ 2 [4, 5, 6], 3 [1, 2, 9], 4 [3, 7, 8] 5]
As per the first step, rows are sorted, and now the largest number in each row is at the end.
-
Using
zip(*nums)
, we transpose the matrix so we can easily access the largest numbers (the last elements of each row):Transposed and zipped matrix (effectively "flip" so that each row is now a column):
1[ 2 [4, 1, 3], 3 [5, 2, 7], 4 [6, 9, 8] 5]
-
For each new row (originally a column), we select the maximum value (which, in this case, would be the originally last item of each row due to sorting).
Largest numbers, which are the maxima of the transposed rows:
- The max of the first transposed row is
4
- The max of the second transposed row is
7
- The max of the third transposed row is
9
- The max of the first transposed row is
-
Finally, we sum up these maxima to get the final score, which is
4 + 7 + 9 = 20
.
The sum of these maxima gives us the solution to the problem, which is the final score. In this example, the score is 20
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def matrix_sum(self, nums: List[List[int]]) -> int:
5 # Sort each row of the matrix in ascending order
6 for row in nums:
7 row.sort()
8
9 # Transpose the matrix to access columns as rows
10 transposed_matrix = zip(*nums)
11
12 # Find the max element in each column (since rows are sorted, it is the last element in each row after transposition)
13 # And compute the sum of these maximum values
14 return sum(map(max, transposed_matrix))
15
16# Example of using the Solution class to find matrix sum
17# matrix = [
18# [1, 2, 3],
19# [4, 5, 6],
20# [7, 8, 9]
21# ]
22# sol = Solution()
23# print(sol.matrix_sum(matrix)) # Output: 18
24
1class Solution {
2 // Method to calculate the sum of the maximum elements in each column of the matrix.
3 public int matrixSum(int[][] matrix) {
4 // Sort each row of the matrix to ensure elements are in non-decreasing order.
5 for (int[] row : matrix) {
6 Arrays.sort(row);
7 }
8
9 // Initialize the sum that will eventually store the answer.
10 int sum = 0;
11
12 // Traverse each column of the sorted matrix to find the maximum element.
13 for (int col = 0; col < matrix[0].length; ++col) {
14 int maxInColumn = 0; // Variable to keep track of the max element in the current column.
15
16 // Iterate through each row to find the maximum element for the current column.
17 for (int[] row : matrix) {
18 maxInColumn = Math.max(maxInColumn, row[col]); // Update the max for the column if a larger element is found.
19 }
20
21 // After finding the maximum element in the column, add it to the sum.
22 sum += maxInColumn;
23 }
24
25 // Return the final sum, which is the total of all maximum elements in each column.
26 return sum;
27 }
28}
29
1#include <vector>
2#include <algorithm> // Include algorithm library for sort and max functions
3
4class Solution {
5public:
6 // Function that calculates the sum of maximum elements in each column after sorting each row
7 int matrixSum(vector<vector<int>>& matrix) {
8 // Sort each row in ascending order
9 for (auto& row : matrix) {
10 sort(row.begin(), row.end());
11 }
12
13 int totalSum = 0; // Initialize sum of max elements to 0
14
15 // Loop through each column
16 for (int col = 0; col < matrix[0].size(); ++col) {
17 int maxElem = 0; // Variable to store the max element in the current column
18
19 // Loop through each row to find the max element in the current column
20 for (auto& row : matrix) {
21 // Update maxElem if we find a larger element in current column
22 maxElem = max(maxElem, row[col]);
23 }
24
25 // Add the max element of the current column to the total sum
26 totalSum += maxElem;
27 }
28
29 // Return the total sum of max elements of all columns
30 return totalSum;
31 }
32};
33
1function matrixSum(matrix: number[][]): number {
2 // Sort each row in the matrix to have numbers in ascending order
3 for (const row of matrix) {
4 row.sort((a, b) => a - b);
5 }
6
7 let totalSum = 0; // Initialize a variable to store the sum of maximums from each column
8
9 // Iterate over the columns of the matrix
10 for (let columnIndex = 0; columnIndex < matrix[0].length; ++columnIndex) {
11 let maxInColumn = 0; // Initialize a variable to store the maximum value in the current column
12
13 // Iterate over each row to find the maximum value in the current column
14 for (const row of matrix) {
15 maxInColumn = Math.max(maxInColumn, row[columnIndex]);
16 }
17
18 // Add the maximum value of the current column to the total sum
19 totalSum += maxInColumn;
20 }
21
22 return totalSum; // Return the computed sum
23}
24
Time and Space Complexity
Time Complexity:
The time complexity of the matrixSum
method involves two steps: sorting the rows of the matrix and finding the maximum element of each column after transposition.
-
Sorting: Each row is sorted individually using
row.sort()
, which typically uses Tim Sort, an algorithm with a worst-case time complexity ofO(n log n)
for sorting a list ofn
elements. Ifm
represents the number of rows andn
represents the number of columns innums
, then the sorting step has a time complexity ofO(m * n log n)
. -
Finding max and summing: The
zip(*nums)
function is used to transpose the matrix, andmap(max, ...)
is used to find the maximum element in each column. Since there aren
columns, and finding the max takesO(m)
time for each column, this step has a time complexity ofO(m * n)
. The final summing of these values is done inO(n)
.
Combining the two steps, the overall time complexity is O(m * n log n) + O(m * n) + O(n)
, which simplifies to O(m * n log n)
because O(m * n log n)
is the dominating term.
Space Complexity:
-
Sorting: Sorting is done in-place for each row, so no additional space is proportional to the size of the input matrix is used. Therefore, it does not increase the asymptotic space complexity.
-
Transposing and finding max: The
zip
function returns an iterator of tuples, which, when combined withmap
, doesn't create a list of the entire transposed matrix but rather creates one tuple at a time. Thus, the space required for this operation isO(n)
for storing the maximums of each column.
Thus, the space complexity of the matrixSum
method is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.