Sum in a Matrix - Video Solutions

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.