Find Each Island's Maximum Height

Question

The question asks the candidate to find the maximum height of each island represented in a 2D grid, where islands are formed by connected '1's and the rest of the grid is filled with '0's.

Codemia · Accepted Answer

To solve the problem, we will use a depth-first search (DFS) algorithm to traverse the grid. We will iterate through each cell in the grid, and upon encountering a '1', we will initiate a DFS to explore the entire island, marking cells as visited. During the traversal, we will keep track of the maximum height of the island. Here is the Python code implementing the DFS algorithm: ```python def maxIslandHeight(grid): if not grid: return [] max_heights = [] rows, cols = len(grid), len(grid[0]) visited = [[False] * cols for _ in range(rows)] def dfs(r, c): if r < 0 or c < 0 or r >= rows or c >= cols or visited[r][c] or grid[r][c] == 0: return 0 visited[r][c] = True height = 1 # Current cell contributes height height += dfs(r + 1, c) # Down height += dfs(r - 1, c) # Up height += dfs(r, c + 1) # Right height += dfs(r, c - 1) # Left return height for r in range(rows): for c in range(cols): if grid[r][c] == 1 and not visited[r][c]: max_height = dfs(r, c) max_heights.append(max_height) return max_heights ``` This code initializes a visited matrix to track cells that have already been explored and iterates through the grid to find islands. The time complexity of this solution is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because, in the worst case, we may visit every cell in the grid. The space complexity is O(M * N) as well, due to the visited matrix used to track the cells. We need to consider edge cases such as an empty grid or a grid with no islands. In these cases, the function should return an empty list. Additionally, we should ensure that the algorithm handles grids with varying heights correctly, although in this specific problem, we are only focused on the presence of '1's. Interviewers will be looking for clarity in your explanation, the ability to write clean and efficient code, and a thorough understanding of the algorithm's performance. They may also assess your problem-solving approach and how you handle edge cases.

Find Each Island's Maximum Height

Oracle

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Oracle Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string