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
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    implicit none

    integer, parameter :: m = 2, n = 3
    integer, dimension(m, n) :: grid = reshape([1, 2, 4, 3, 3, 1], shape(grid))
    integer :: i, j, max_val, ans

    do while (any(grid /= 0))
        max_val = -huge(max_val)
        do i = 1, m
            if (grid(i, :) > max_val) then
                max_val = grid(i, :)
            end if
        end do
        do i = 1, m
            if (grid(i, :) == max_val) then
                grid(i, :) = 0
                exit
            end if
        end do
        ans = ans + max_val
    end do

    print '(I0)', ans

end program main
āŒ Compiled
āŒ Executed
āŒ Correct 
program max_sum_matrix
      implicit none

      integer, parameter :: m = 50, n = 50
      integer :: grid(m, n)
      integer :: max_val, max_row, max_col
      integer :: i, j
      integer :: answer

      ! Read the grid from the input
      read (*, *) grid

      ! Initialize the answer
      answer = 0

      ! Loop until the grid is empty
      do while (any(grid /= 0))
         ! Find the maximum value in the grid
         max_val = -1
         max_row = -1
         max_col = -1
         do i = 1, m
            do j = 1, n
               if (grid(i, j) > max_val) then
                  max_val = grid(i, j)
                  max_row = i
                  max_col = j
               end if
            end do
         end do

         ! Add the maximum value to the answer
         answer = answer + max_val

         ! Remove the maximum value from the grid
         grid(max_row, max_col) = 0

         ! Decrease the number of columns
         n = n - 1
      end do

      ! Print the answer
      write (*, *) answer

      end program max_sum_matrix
šŸŒ Data from online sources 
def maxValueAfterOperations(grid):
    ans = 0
    while grid:
        maxVal = 0
        maxRow = -1

        for i, row in enumerate(grid):
            rowMax = max(row)
            if rowMax > maxVal:
                maxVal = rowMax
                maxRow = i
            grid[i] = [e for e in row if e != rowMax]

        ans += maxVal
        if not grid[maxRow]:
            grid.pop(maxRow)

    return ans

- Loop until 'grid' becomes empty.
  • Search for the greatest element in each row and delete any of them if there's a tie. Keep track of the maximum of deleted elements and the respective row number.
  • Add the maximum of deleted elements to 'ans'.
  • If the row with initially found maximum becomes empty, remove that row from 'grid'.
  • Finally, return the sum of all maximum deleted elements 'ans'.
šŸŒ Data from online sources 
int maxValueAfterOperations(vector<vector<int>>& grid) {
    int ans = 0;
    while (!grid.empty()) {
        int maxVal = 0, maxRow = -1;

        for(int i = 0; i < grid.size(); ++i) {
            auto it = max_element(grid[i].begin(), grid[i].end());
            if(*it > maxVal) {
                maxVal = *it;
                maxRow = i;
            }
            grid[i].erase(it);
        }

        ans += maxVal;
        if (grid[maxRow].empty()) {
            grid.erase(grid.begin() + maxRow);
        }
    }

    return ans;
}

- Loop until 'grid' becomes empty.
  • Search for the greatest element in each row and delete any of them if there's a tie. Keep track of the maximum of deleted elements and the respective row number.
  • Add the maximum of deleted elements to 'ans'.
  • If the row with initially found maximum becomes empty, remove that row from 'grid'.
  • Finally, return the sum of all maximum deleted elements 'ans'.