You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:
Return the final score.
Example 1:
Input: nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]] Output: 15 Explanation: In the first operation, we remove 7, 6, 6, and 3. We then add 7 to our score. Next, we remove 2, 4, 5, and 2. We add 5 to our score. Lastly, we remove 1, 2, 3, and 1. We add 3 to our score. Thus, our final score is 7 + 5 + 3 = 15.
Example 2:
Input: nums = [[1]] Output: 1 Explanation: We remove 1 and add it to the answer. We return 1.
Constraints:
1 <= nums.length <= 3001 <= nums[i].length <= 5000 <= nums[i][j] <= 103Problem Overview: You are given an m x n matrix. During each step, select the largest value remaining in every row, then add the maximum among those selected values to the answer. Continue until all elements are removed. The goal is to compute the total sum of these chosen maximums.
Approach 1: Greedy with Row Sorting (O(m * n log n) time, O(1) extra space)
This approach relies on sorting each row so the largest values naturally line up by column. First, sort every row in non‑decreasing order using a standard sort. After sorting, iterate column by column from right to left (largest values). For each column j, scan all rows and take the maximum value max(nums[i][j]). Add this value to the total sum. Sorting ensures that each column represents the "current largest remaining" element of every row, which perfectly simulates the removal process without explicitly removing elements.
The key insight: after sorting, the last column holds the largest elements, the second-last column holds the second largest, and so on. This transforms the simulation into a simple column-wise scan. Time complexity is O(m * n log n) due to sorting each row of length n, and space complexity is O(1) ignoring the sort implementation. This solution heavily relies on sorting and basic traversal of a matrix.
Approach 2: Priority Queue Simulation (O(m * n log n) time, O(m * n) space)
This version simulates the process exactly using a priority queue (heap). Convert each row into a max heap so you can repeatedly extract its largest element. During each round, pop the maximum element from every row's heap and track the largest value among those popped numbers. Add that largest value to the answer.
This continues for n rounds because each row contains n elements. Heap operations cost O(log n), and you perform one extraction per row per round, resulting in O(m * n log n) total time. The space complexity is O(m * n) because all elements are stored inside heaps. This method mirrors the problem statement closely and is easier to reason about if you think in terms of simulation rather than structural transformation.
Recommended for interviews: The greedy sorting approach is the one interviewers usually expect. It demonstrates the ability to transform a simulation problem into a structured greedy solution by reorganizing the data first. The heap approach still works and shows familiarity with array processing and priority queues, but it uses more memory and doesn’t exploit the key observation about sorted columns.
Greedy Approach: The idea is to iterate through the given matrix and select the maximum number from each row. Gather these selected numbers and choose the largest among them to add to your score. Repeat this process by adjusting the remaining numbers until the matrix becomes empty.
This solution uses a greedy approach where on each iteration we pick the maximum number from each row, remove it, and then take the maximum out of these to add to the score. We keep repeating the steps until the matrix becomes empty.
Time Complexity: O(n * m * min(n, m)), where n is the number of rows and m is the number of columns. Space Complexity: O(n), used for storing the maximum value in each row during each iteration.
Priority Queue Approach: In this method, we use a max-heap to efficiently manage and access the maximum numbers from each iteration. Push maximum elements from each row into a heap and use it to ever-increase the score by extracting the largest numbers available.
This Java solution constructs a priority queue to maintain the largest possible elements retrieved from each row. By resolving the maximum number selection through heap operations, we optimize the retrieval process while updating scores as needed.
Java
JavaScript
Time Complexity: O(n * m log(n*m)), due to the heap operations. Space Complexity: O(n * m) due to heap storage requirements.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n * m * min(n, m)), where n is the number of rows and m is the number of columns. Space Complexity: O(n), used for storing the maximum value in each row during each iteration. |
| Priority Queue Approach | Time Complexity: O(n * m log(n*m)), due to the heap operations. Space Complexity: O(n * m) due to heap storage requirements. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Row Sorting | O(m * n log n) | O(1) | Best general solution. Simple implementation and optimal space usage. |
| Priority Queue Simulation | O(m * n log n) | O(m * n) | Useful when directly simulating the process or practicing heap operations. |
6367. Sum in a Matrix | Leetcode Biweekly Contest 104 | Solution Code. • Optimization • 556 views views
Watch 9 more video solutions →Practice Sum in a Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor