Sum in a Matrix - Solution & Explanation

Q: Is Sum in a Matrix easy or hard?

Sum in a Matrix is generally classified as a medium difficulty problem. The implementation is straightforward once you recognize the key insight that sorting rows aligns the removal order. Without that observation, many developers initially attempt a more complex heap-based simulation.

Q: Sum in a Matrix Python/Java solution

In Python or C++, the typical solution sorts each row with built-in sorting and then scans columns to compute the maximum value per column. In Java or JavaScript, another implementation uses priority queues to simulate repeatedly removing the largest values from each row.

Q: How to solve Sum in a Matrix in O(n)?

A true O(n) solution is not feasible because the matrix must be processed row by row and typically sorted. The best practical solution is O(m * n log n) using row sorting. This step organizes elements so the column-wise maximum can be computed efficiently.

Q: What is the best approach for Sum in a Matrix?

The greedy approach that sorts each row is the most efficient and simplest to implement. After sorting rows, iterate column by column and take the maximum element across rows for each column. This works because sorting aligns the largest remaining elements in the same column positions. The overall complexity is O(m * n log n) time with O(1) extra space.

Q: Is Sum in a Matrix asked at Google/Amazon/Meta?

Problems involving matrix processing, greedy reasoning, and heap-based simulation frequently appear in interviews at companies like Amazon and Google. While this exact problem may vary, the patterns of sorting rows, using priority queues, and transforming simulations into greedy solutions are common interview topics.

Q: What data structure is used in Sum in a Matrix?

The main data structures used are arrays for representing the matrix and optionally a priority queue (max heap) for simulation. The greedy solution relies primarily on array sorting, while the alternative solution uses heaps to repeatedly extract the largest element from each row.

Q: What is the time complexity of Sum in a Matrix?

The optimal solution runs in O(m * n log n) time. Each of the m rows must be sorted, and sorting a row of length n costs O(n log n). After sorting, scanning columns to compute the answer takes O(m * n).

MediumArray Sorting Heap (Priority Queue)Matrix8 min read

Practice this problem

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 <= 300
1 <= nums[i].length <= 500
0 <= nums[i][j] <= 10³

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.

Approach 1: Greedy Approach

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.

Code

Python C++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Priority Queue Approach

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.

Code

Java JavaScript

Java

JavaScript

Complexity

Time Complexity: O(n * m log(n*m)), due to the heap operations. Space Complexity: O(n * m) due to heap storage requirements.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

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(nm)), due to the heap operations. Space Complexity: O(n m) due to heap storage requirements.
Default Approach	—

Detailed 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.

Video Solution

6367. Sum in a Matrix | Leetcode Biweekly Contest 104 | Solution Code. • Optimization • 556 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Sum in a Matrix easy or hard?

Sum in a Matrix is generally classified as a medium difficulty problem. The implementation is straightforward once you recognize the key insight that sorting rows aligns the removal order. Without that observation, many developers initially attempt a more complex heap-based simulation.

Sum in a Matrix Python/Java solution

In Python or C++, the typical solution sorts each row with built-in sorting and then scans columns to compute the maximum value per column. In Java or JavaScript, another implementation uses priority queues to simulate repeatedly removing the largest values from each row.

How to solve Sum in a Matrix in O(n)?

A true O(n) solution is not feasible because the matrix must be processed row by row and typically sorted. The best practical solution is O(m * n log n) using row sorting. This step organizes elements so the column-wise maximum can be computed efficiently.

What is the best approach for Sum in a Matrix?

The greedy approach that sorts each row is the most efficient and simplest to implement. After sorting rows, iterate column by column and take the maximum element across rows for each column. This works because sorting aligns the largest remaining elements in the same column positions. The overall complexity is O(m * n log n) time with O(1) extra space.

Is Sum in a Matrix asked at Google/Amazon/Meta?

Problems involving matrix processing, greedy reasoning, and heap-based simulation frequently appear in interviews at companies like Amazon and Google. While this exact problem may vary, the patterns of sorting rows, using priority queues, and transforming simulations into greedy solutions are common interview topics.

What data structure is used in Sum in a Matrix?

The main data structures used are arrays for representing the matrix and optionally a priority queue (max heap) for simulation. The greedy solution relies primarily on array sorting, while the alternative solution uses heaps to repeatedly extract the largest element from each row.

What is the time complexity of Sum in a Matrix?

The optimal solution runs in O(m * n log n) time. Each of the m rows must be sorted, and sorting a row of length n costs O(n log n). After sorting, scanning columns to compute the answer takes O(m * n).

Ready to solve this problem?

Practice Sum in a Matrix with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance61.1%

Approaches3

Reading time8 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Greedy Approach

Code

Complexity

Approach 2: Priority Queue Approach

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents