Sum in a Matrix - Practice Coding Problems

Sum in a Matrix - Problem

You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:

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

2. Identify the highest number amongst all those removed in step 1. Add that number to your score.

Return the final score.

Input & Output

Example 1 — Basic Matrix

$ Input: nums = [[7,9,8,6,2],[6,1],[1]]

› Output: 25

💡 Note: Round 1: Remove [9,6,1], max=9, score=9. Round 2: Remove [8,1], max=8, score=17. Round 3: Remove [7], max=7, score=24. Round 4: Remove [6], max=6, score=30. Wait, let me recalculate: After removing 9,6,1 we have [[7,8,6,2],[1],[]]. Max is 8, score=17. Continue until matrix empty.

Example 2 — Single Row

$ Input: nums = [[1]]

› Output: 1

💡 Note: Only one element in the matrix. Remove 1, add to score. Final score = 1.

Example 3 — Multiple Equal Elements

$ Input: nums = [[1,2,3],[1,2,3],[1,2,3]]

› Output: 12

💡 Note: Round 1: Remove [3,3,3], max=3, score=3. Round 2: Remove [2,2,2], max=2, score=5. Round 3: Remove [1,1,1], max=1, score=6. Total = 3+2+1 = 6.

Constraints

1 ≤ nums.length ≤ 50
1 ≤ nums[i].length ≤ 50
1 ≤ nums[i][j] ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with different row sizes

Extract Maximums

Find and remove largest from each row

Calculate Score

Sum the maximum of extracted elements

Key Takeaway

🎯 Key Insight: Sort rows first to avoid repeated maximum searches, then process systematically.

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to efficiently extract maximum elements from each row repeatedly. The optimal approach uses sorting each row first then processing column-wise, achieving O(nm log m) time. Space complexity is O(1) with in-place modifications.

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue Optimization	O(nm log m)	O(1)	Use max heaps to efficiently track and extract maximum elements from each row
Brute Force Simulation	O(n²m²)	O(1)	Simulate the process exactly as described, finding max in each row repeatedly
Sort Each Row First	O(nm log m + nm²)	O(1)	Sort all rows initially, then repeatedly take the largest element from each row

Priority Queue Optimization — Algorithm Steps

Convert each row to max heap
For each round, extract max from each heap
Find maximum among extracted values and add to score

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Max Heaps

Convert each row to a max heap structure

Extract Maximums

Pop maximum from each heap in O(log m) time

Find Round Max

Compare extracted values to find round maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(int* arr, int size) {
    MaxHeap* heap = malloc(sizeof(MaxHeap));
    heap->data = malloc(size * sizeof(int));
    heap->size = size;
    heap->capacity = size;
    memcpy(heap->data, arr, size * sizeof(int));
    
    // Build heap
    for (int i = size / 2 - 1; i >= 0; i--) {
        int parent = i;
        while (2 * parent + 1 < heap->size) {
            int largest = parent;
            int left = 2 * parent + 1;
            int right = 2 * parent + 2;
            
            if (left < heap->size && heap->data[left] > heap->data[largest]) {
                largest = left;
            }
            
            if (right < heap->size && heap->data[right] > heap->data[largest]) {
                largest = right;
            }
            
            if (largest != parent) {
                int temp = heap->data[parent];
                heap->data[parent] = heap->data[largest];
                heap->data[largest] = temp;
                parent = largest;
            } else {
                break;
            }
        }
    }
    
    return heap;
}

int extractMax(MaxHeap* heap) {
    if (heap->size == 0) return INT_MIN;
    
    int max = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    
    // Heapify down
    int parent = 0;
    while (2 * parent + 1 < heap->size) {
        int largest = parent;
        int left = 2 * parent + 1;
        int right = 2 * parent + 2;
        
        if (left < heap->size && heap->data[left] > heap->data[largest]) {
            largest = left;
        }
        
        if (right < heap->size && heap->data[right] > heap->data[largest]) {
            largest = right;
        }
        
        if (largest != parent) {
            int temp = heap->data[parent];
            heap->data[parent] = heap->data[largest];
            heap->data[largest] = temp;
            parent = largest;
        } else {
            break;
        }
    }
    
    return max;
}

int solution(int** nums, int numsSize, int* numsColSize) {
    MaxHeap** heaps = malloc(numsSize * sizeof(MaxHeap*));
    int heapCount = 0;
    
    // Create heaps for non-empty rows
    for (int i = 0; i < numsSize; i++) {
        if (numsColSize[i] > 0) {
            heaps[heapCount++] = createHeap(nums[i], numsColSize[i]);
        }
    }
    
    int score = 0;
    
    while (heapCount > 0) {
        int roundMax = INT_MIN;
        
        // Extract max from each heap
        for (int i = 0; i < heapCount; i++) {
            if (heaps[i]->size > 0) {
                int maxVal = extractMax(heaps[i]);
                if (maxVal > roundMax) {
                    roundMax = maxVal;
                }
            }
        }
        
        // Remove empty heaps
        int newHeapCount = 0;
        for (int i = 0; i < heapCount; i++) {
            if (heaps[i]->size > 0) {
                heaps[newHeapCount++] = heaps[i];
            }
        }
        heapCount = newHeapCount;
        
        score += roundMax;
    }
    
    return score;
}

int main() {
    // Simplified parsing for demo
    int numsSize = 2;
    int** nums = malloc(numsSize * sizeof(int*));
    int* numsColSize = malloc(numsSize * sizeof(int));
    
    // Example: [[7,9,8,6,2],[6,1]]
    nums[0] = malloc(5 * sizeof(int));
    nums[0][0] = 7; nums[0][1] = 9; nums[0][2] = 8; nums[0][3] = 6; nums[0][4] = 2;
    numsColSize[0] = 5;
    
    nums[1] = malloc(2 * sizeof(int));
    nums[1][0] = 6; nums[1][1] = 1;
    numsColSize[1] = 2;
    
    printf("%d\n", solution(nums, numsSize, numsColSize));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(nm log m)

Building heaps takes O(nm), then m rounds with n heap extractions of O(log m) each

⚡ Linearithmic

Space Complexity

O(1)

Heapify in-place, only using constant extra space for variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

445 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Priority Queue Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler