algoadvance

Leetcode 2500. Delete Greatest Value in Each Row

Problem Statement

You are given an m x n matrix where each row is sorted in non-decreasing order. You need to delete the greatest value in each row. You repeat this process for the remaining part of the matrix until it becomes empty. The result should be the sum of all the deleted values.

Clarifying Questions

1. What is the range of values for m and n?
   • The problem typically does not specify but we can assume reasonable constraints suitable for matrix operations.
2. Is the matrix guaranteed to be non-empty?
   • Generally, yes, but it’s good to handle edge cases.
3. Should the input matrix be modified in place or can we work on a copy?
   • Both approaches are acceptable, but we’ll do in-place deletion for simplicity.

Strategy

1. Identify the last element of each row (since rows are non-decreasing, the last element will be the greatest).
2. Sum the last elements of all rows and delete them.
3. Repeat the process until the matrix becomes empty.
4. Return the accumulated sum of the deleted values.

Code

#include <vector>
#include <iostream>

class Solution {
public:
    int deleteGreatestValue(std::vector<std::vector<int>>& grid) {
        int totalSum = 0;
        
        while (!grid.empty() && !grid[0].empty()) {
            int currentSum = 0;
            for (auto& row : grid) {
                // Add the greatest value (last element) of the current row
                currentSum += row.back();
                // Remove the greatest value
                row.pop_back();
            }
            totalSum += currentSum;
        }
        
        return totalSum;
    }
};

int main() {
    Solution solution;
    std::vector<std::vector<int>> grid = \{\{1, 3, 5}, {2, 4, 6}};
    std::cout << "Sum of deleted values: " << solution.deleteGreatestValue(grid) << std::endl;
    return 0;
}

Time Complexity

The time complexity of the solution can be analyzed as follows:

• Each row originally has n elements.
• In each iteration over the matrix, we perform m deletions (one for each row).
• Thus, there are a total of m * n deletions.

So, the time complexity is:

• O(m * n) where m is the number of rows and n is the number of columns.

This accounts for traversing each element of the matrix exactly once before it is deleted.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?