Delete Greatest Value in Each Row - Practice Coding Problems

Delete Greatest Value in Each Row - Problem

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
Add the maximum of deleted elements to the answer.

Note: The number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

Input & Output

Example 1 — Basic Matrix

$ Input: grid = [[1,2,1],[3,4,5],[6,7,2]]

› Output: 16

💡 Note: Round 1: Remove max from each row: [2,5,7], max=7, add to result. Round 2: Remove max from remaining: [1,4,6], max=6, add to result. Round 3: Remove last elements: [1,3,2], max=3, add to result. Total: 7+6+3=16

Example 2 — Single Row

$ Input: grid = [[1,2,3,4]]

› Output: 10

💡 Note: Round 1: max=4, Round 2: max=3, Round 3: max=2, Round 4: max=1. Total: 4+3+2+1=10

Example 3 — Single Column

$ Input: grid = [[7],[3],[1]]

› Output: 7

💡 Note: Only one column, so we take the maximum element from it: max([7,3,1]) = 7

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 50
1 ≤ grid[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3×3 matrix with positive integers

Process Rounds

Each round removes max from each row, adds max of removed to result

Final Sum

Sum of maximums from each round

Key Takeaway

🎯 Key Insight: Sort each row in descending order first to make finding maximums O(1) per row

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we need to simulate the process of repeatedly removing maximum elements from each row. The optimal approach is to sort each row in descending order first, then process columns from left to right. Time: O(m*n*log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(m*n²)	O(1)	Repeatedly find and remove maximum from each row, add max of removed to result
Sort Each Row First	O(mnlog n)	O(1)	Sort all rows in descending order, then process columns from left to right

Brute Force Simulation — Algorithm Steps

Step 1: While grid has columns, find max element in each row
Step 2: Remove these max elements and find the maximum among them
Step 3: Add this maximum to the result sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Max in Each Row

Scan each row to find maximum element

Remove and Collect

Remove max elements and find overall maximum

Add to Result

Add the maximum of removed elements to final answer

Code -

solution.c — C

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

int solution(int** grid, int* gridSizes, int gridRowSize) {
    int result = 0;
    
    while (1) {
        // Check if any row has elements
        int hasElements = 0;
        for (int i = 0; i < gridRowSize; i++) {
            if (gridSizes[i] > 0) {
                hasElements = 1;
                break;
            }
        }
        if (!hasElements) break;
        
        int maxElements[1000];
        int maxCount = 0;
        
        // Find and remove max from each row
        for (int i = 0; i < gridRowSize; i++) {
            if (gridSizes[i] > 0) {
                // Find max element and its index
                int maxVal = grid[i][0];
                int maxIdx = 0;
                for (int j = 1; j < gridSizes[i]; j++) {
                    if (grid[i][j] > maxVal) {
                        maxVal = grid[i][j];
                        maxIdx = j;
                    }
                }
                
                // Remove max element by shifting
                for (int j = maxIdx; j < gridSizes[i] - 1; j++) {
                    grid[i][j] = grid[i][j + 1];
                }
                gridSizes[i]--;
                maxElements[maxCount++] = maxVal;
            }
        }
        
        // Add max of removed elements to result
        if (maxCount > 0) {
            int maxOfMax = maxElements[0];
            for (int i = 1; i < maxCount; i++) {
                if (maxElements[i] > maxOfMax) {
                    maxOfMax = maxElements[i];
                }
            }
            result += maxOfMax;
        }
    }
    
    return result;
}

int main() {
    // Simple implementation for small inputs
    int grid[100][100];
    int gridSizes[100];
    int gridRowSize = 0;
    
    // Read grid (simplified parsing)
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse [[1,2,3],[4,5,6]] format
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']' || *(ptr+1) != '\0') {
        if (*ptr == '[') {
            ptr++;
            gridSizes[gridRowSize] = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    int num = 0;
                    while (*ptr >= '0' && *ptr <= '9') {
                        num = num * 10 + (*ptr - '0');
                        ptr++;
                    }
                    grid[gridRowSize][gridSizes[gridRowSize]++] = num;
                } else {
                    ptr++;
                }
            }
            gridRowSize++;
        }
        ptr++;
    }
    
    // Convert to pointer array
    int* gridPtrs[100];
    for (int i = 0; i < gridRowSize; i++) {
        gridPtrs[i] = grid[i];
    }
    
    int result = solution(gridPtrs, gridSizes, gridRowSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m*n²)

For each of n columns, we scan m rows of average length n/2 to find maximums

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, modifying input grid in-place

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 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

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler