Lucky Numbers in a Matrix

🏠 ⬅️ ➡️

Given an m x n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] Output: [12] Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]] Output: [7] Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 105.
  • All elements in the matrix are distinct.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: m = 3, n = 3
    integer, dimension(m, n) :: matrix
    integer, dimension(:), allocatable :: lucky_numbers

    matrix = reshape([3, 7, 8, &
                       9, 11, 13, &
                       15, 16, 17], shape(matrix))

    call solve(matrix, lucky_numbers)

    write (*, '(A, *(I0, :, A))') 'Lucky numbers: ', lucky_numbers

contains

    subroutine solve(mat, lucky_nums)
        implicit none
        integer, intent(in) :: mat(:, :)
        integer, allocatable, intent(out) :: lucky_nums(:)
        integer :: i, j, min_row, max_col

        allocate (lucky_nums(size(mat)))

        do i = 1, size(mat, 1)
            min_row = mat(i, 1)
            max_col = mat(1, i)
            do j = 2, size(mat, 2)
                if (mat(i, j) < min_row) then
                    min_row = mat(i, j)
                else if (mat(i, j) > max_col) then
                    max_col = mat(i, j)
                end if
            end do
            if (min_row == mat(i, 1) .and. max_col == mat(1, i)) then
                lucky_nums(size(lucky_nums)-i+1) = min_row
            end if
        end do

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
program luckyNumbers
      implicit none

      integer, parameter :: m = 50, n = 50
      integer :: matrix(m, n)
      integer :: luckyNumbers(m)
      integer :: i, j, k

      ! Read the matrix from stdin
      do i = 1, m
          read(*,*) matrix(i, :)
      end do

      ! Find the lucky numbers
      k = 1
      do i = 1, m
          do j = 1, n
              if (matrix(i, j) == minval(matrix(i, :), dim=1) .and. &
                  matrix(i, j) == maxval(matrix(i, :), dim=1)) then
                  luckyNumbers(k) = matrix(i, j)
                  k = k + 1
              end if
          end do
      end do

      ! Print the lucky numbers
      do i = 1, k - 1
          write (*,*) luckyNumbers(i)
      end do

      end program luckyNumbers
🌐 Data from online sources 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(grid, x, y):
    n, m = len(grid), len(grid[0])
    grid[x][y] = 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 0:
            dfs(grid, nx, ny)

def closedIsland(grid):
    n, m = len(grid), len(grid[0])
    for i in range(n):
        for j in range(m):
            if i == 0 or i == n - 1 or j == 0 or j == m - 1:
                if grid[i][j] == 0:
                    dfs(grid, i, j)
    res = 0
    for i in range(1, n - 1):
        for j in range(1, m - 1):
            if grid[i][j] == 0:
                dfs(grid, i, j)
                res += 1
    return res

1. First, create a DFS function that traverses the grid and marks 0s as 1s if they are part of an island.
  1. For each cell in the border of the grid, if it's a 0, use the DFS function to mark all border-connected islands (removing them from consideration).
  2. Traverse the inner cells of the grid (excluding outer border cells) and use DFS to find closed islands by marking connected 0s as 1s. Increment the result counter for each closed island found.
  3. Return the result (number of closed islands).
🌐 Data from online sources 
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(vector<vector<int>>& grid, int x, int y) {
    int n = grid.size(), m = grid[0].size();
    grid[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0) {
            dfs(grid, nx, ny);
        }
    }
}

int closedIsland(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                if (grid[i][j] == 0) {
                    dfs(grid, i, j);
                }
            }
        }
    }
    int res = 0;
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            if (grid[i][j] == 0) {
                dfs(grid, i, j);
                res++;
            }
        }
    }
    return res;
}

1. First, create a DFS function that traverses the grid and marks 0s as 1s if they are part of an island.
  1. For each cell in the border of the grid, if it's a 0, use the DFS function to mark all border-connected islands (removing them from consideration).
  2. Traverse the inner cells of the grid (excluding outer border cells) and use DFS to find closed islands by marking connected 0s as 1s. Increment the result counter for each closed island found.
  3. Return the result (number of closed islands).