Sum in a Matrix - Video Solutions
6367. Sum in a Matrix | Leetcode Biweekly Contest 104 | Solution Code.
Sum in a Matrix - Video Solution
Watch 9 video solutions for Sum in a Matrix, a medium level problem involving Array, Sorting, Heap (Priority Queue). This walkthrough by Optimization has 556 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:
- From each row in the matrix, select the largest number and remove it. In the case of a tie, it does not matter which number is chosen.
- Identify the highest number amongst all those removed in step 1. Add that number to your score.
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] <= 103
Approach Overview
Problem 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.
Complexity Analysis
| 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. |