Leetcode problem 116 - Delete Greatest Value in Each Row

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 that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

Example 1:

Input: grid = [[1,2,4],[3,3,1]] Output: 8 Explanation: The diagram above shows the removed values in each step.

• In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
• In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
• In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer. The final answer = 4 + 3 + 1 = 8. Example 2:

Input: grid = [[10]] Output: 10 Explanation: The diagram above shows the removed values in each step.

• In the first operation, we remove 10 from the first row. We add 10 to the answer. The final answer = 10.

Constraints:

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

/**
 * @param {number[][]} grid
 * @return {number}
 */
var deleteGreatestValue = function (grid) {
  // Sort each row of the grid in ascending order
  grid.forEach((row) => row.sort((a, b) => a - b));

  // Initialize the sum variable to store the total sum of maximum numbers
  let sum = 0;

  // Continue the loop until the length of the first row becomes zero
  while (grid[0].length) {
    // Create an array to store the maximum numbers from each row
    let maxNum = [];

    // Iterate through each row of the grid
    for (let row of grid) {
      // Pop the last element from each row and push it into the maxNum array
      maxNum.push(row.pop());
    }

    // Add the maximum number from the current iteration to the sum
    sum += Math.max(...maxNum);
  }

  // Return the total sum of maximum numbers
  return sum;
};

The time complexity is the sorting operation, so the total time complexity of the code is O(n * m log m), where n is the number of rows and m is the number of elements in each row.

The total space complexity of the code is O(n), where n is the number of rows in the grid. This is because the code uses a single array to store the maximum value of each row.