Katkat
Back

Find Each Island's Maximum Height

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to perform graph traversal (BFS/DFS) on a 2D grid while maintaining state across connected components.

Problem Statement

You are given a 2D grid of size m x n representing a landscape. Each cell contains a non-negative integer representing its elevation. An island is defined as a group of cells with elevation greater than 0 that are connected 4-directionally (horizontally or vertically).

Your task is to identify all islands in the grid and, for each island, find the maximum height present within it. You should return a list of these maximum heights, sorted in descending order. If there are multiple islands with the same maximum height, include them as separate entries in your list.

Function Signature

def find_island_max_heights(grid: List[List[int]]) -> List[int]:

Constraints

  • m == grid.length
  • n == grid[0].length
  • 1 <= m, n <= 300
  • 0 <= grid[i][j] <= 10^5

Examples

Example 1: Input:

grid = [
  [0, 5, 0],
  [3, 0, 8],
  [0, 0, 0]
]

Output: [5, 3] Explanation: There are two islands. One has heights {5}, the other has {3}. The maxes are 5 and 3.

Example 2: Input:

grid = [
  [1, 2],
  [0, 0],
  [3, 1]
]

Output: [3, 2] Explanation: The island with heights {1, 2} has a max of 2. The island with heights {3, 1} has a max of 3. Sorted descending: [3, 2].

Hints

Hint 1

Iterate through every cell in the grid and initiate a traversal whenever you encounter a cell with a value greater than 0 that hasn't been visited yet.

Hint 2

During the traversal (DFS or BFS), keep track of the maximum value encountered among the cells belonging to the current connected component.

Hint 3

Use a boolean matrix or modify the input grid in-place (if allowed) to keep track of visited cells to ensure each island is processed exactly once.

Follow-up questions

  • How would your approach change if you needed to return the coordinate of the peak cell for each island?
  • What is the time and space complexity of your solution in terms of total grid cells N?
  • If the grid was extremely large (e.g., too big for memory), how would you modify the approach to handle it using a distributed system?