The Find Peak Element problem involves identifying the largest consecutive deltas found in a two-dimensional array of integers. To arrive at a solution, one must clearly understand the constraints of the matrix problem and apply a graph traversal algorithm to generate a linear time complexity solution.
You are given a two-dimensional binary matrix where 1
represents water and 0
represents land. You can assign a height to each element in the matrix using the following rules:
0
.You need to assign a height to each element in the matrix such that the tallest peak is maximized, the peak being the tallest height of an element in the matrix.
Mutate the matrix in place and return the matrix with the highest peak maximized. If there are multiple solutions, return any of them.
Input: [1] Output: [0]
Input: [[0,1],[0,0]] Output: [[1,0],[2,1]]
Input: [[0,0,0,1,0], [0,1,0,0,0], [0,0,0,0,0]]
Output: [[2,1,1,0,1], [1,0,1,1,2], [2,1,2,2,3]]
Constraints
m
and width = n
Below we walk through two different approaches to solving this problem: building outwards from water and storing seen locations in the input matrix.
When tackling an algorithm problem a good place to start is to think about how you would solve the problem by hand. If given a matrix of 1
’s and 0
’s, one approach would be to start at all water locations in the matrix and “build up” the land as you go outwards from the water.
We expand left, right, up and down from all water squares without going diagonally or going out of bounds.
We then expand outward from all the land just built. We take the value of each cell we are expanding outward from (in the above case 1
) and add 1
, as dictated by the “maximum difference of one” restraint.
We expand outwards again from all the just built 2
’s.
And with one more expansion the matrix is filled in and height maximized.
From a code perspective, we can accomplish this approach using a queue, adding adjacent land squares that need to be processed to the queue as we move outwards from the water squares. We also keep track of locations we’ve already visited in order to avoid duplicate work.
One thing to consider when tackling this problem is whether the interviewer would rather have you mutate the matrix in place (more space efficient, but sometimes an anti-pattern to mutate inputs) vs making a copy and mutating that (which is obviously less space efficient). Acknowledging this tradeoff will likely be a positive signal to your interviewer.
from typing import List
import collections
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
rowMax, colMax = len(isWater), len(isWater[0])
seen = [[0 for _ in range(colMax)] for _ in range(rowMax)]
# standard library python data structure that acts as both a queue and a stack
queue = collections.deque()
for row in range(rowMax):
for col in range(colMax):
if isWater[row][col]:
queue.append([row, col])
seen[row][col] = 1
isWater[row][col] = 0
else:
isWater[row][col] = 1
directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
while queue:
row, col = queue.popleft()
for direction in directions:
nextRow = direction[0] + row
nextCol = direction[1] + col
if self.inBounds(nextRow, nextCol, rowMax, colMax) and seen[nextRow][nextCol] == 0:
isWater[nextRow][nextCol] = isWater[row][col] + 1
seen[nextRow][nextCol] = 1
queue.append([nextRow, nextCol])
return isWater
def inBounds(self, row, col, rowMax, colMax):
return not (row < 0 or col < 0 or col >= colMax or row >= rowMax)
1from typing import List
2import collections
3
4class Solution:
5 def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
6 rowMax, colMax = len(isWater), len(isWater[0])
7 seen = [[0 for _ in range(colMax)] for _ in range(rowMax)]
8
9 # standard library python data structure that acts as both a queue and a stack
10 queue = collections.deque()
11
12 for row in range(rowMax):
13 for col in range(colMax):
14 if isWater[row][col]:
15 queue.append([row, col])
16 seen[row][col] = 1
17 isWater[row][col] = 0
18 else:
19 isWater[row][col] = 1
20
21
22 directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
23 while queue:
24 row, col = queue.popleft()
25 for direction in directions:
26 nextRow = direction[0] + row
27 nextCol = direction[1] + col
28 if self.inBounds(nextRow, nextCol, rowMax, colMax) and seen[nextRow][nextCol] == 0:
29 isWater[nextRow][nextCol] = isWater[row][col] + 1
30 seen[nextRow][nextCol] = 1
31 queue.append([nextRow, nextCol])
32
33 return isWater
34
35 def inBounds(self, row, col, rowMax, colMax):
36 return not (row < 0 or col < 0 or col >= colMax or row >= rowMax)
37
Time complexity: O(m*n)
, as we visit every location in the matrix once.
Space complexity: O(m*n)
for the matrix used to store whether we have visited a given location.
Seen
Locations in the Input MatrixThis approach is just a small optimization over Approach 1. Instead of maintaining the locations which we’ve already visited in an additional 2D matrix, we can change the value in the input matrix in place to -1
to denote locations that have already been visited.
Theoretically the matrix could consist of 99%+ water and <= 1% land, meaning 99% of the grid would end up in the queue, so the big-O space complexity is still O(m*n)
worst case but it is much better in the average case.
Seen
Locations in the Input Matrixfrom typing import List
import collections
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
rowMax, colMax = len(isWater), len(isWater[0])
queue = collections.deque()
for row in range(rowMax):
for col in range(colMax):
if isWater[row][col]:
queue.append([row, col])
isWater[row][col] = 0
else:
isWater[row][col] = -1
directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
while queue:
row, col = queue.popleft()
for direction in directions:
nextRow = direction[0] + row
nextCol = direction[1] + col
if self.inBounds(nextRow, nextCol, rowMax, colMax) and isWater[nextRow][nextCol] == -1:
isWater[nextRow][nextCol]= isWater[row][col] + 1
queue.append([nextRow,nextCol])
return isWater
def inBounds(self, row, col, rowMax, colMax):
return not (row<0 or col<0 or col>=colMax or row>=rowMax)
1from typing import List
2import collections
3
4class Solution:
5 def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
6 rowMax, colMax = len(isWater), len(isWater[0])
7 queue = collections.deque()
8
9 for row in range(rowMax):
10 for col in range(colMax):
11 if isWater[row][col]:
12 queue.append([row, col])
13 isWater[row][col] = 0
14 else:
15 isWater[row][col] = -1
16
17 directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
18 while queue:
19 row, col = queue.popleft()
20 for direction in directions:
21 nextRow = direction[0] + row
22 nextCol = direction[1] + col
23 if self.inBounds(nextRow, nextCol, rowMax, colMax) and isWater[nextRow][nextCol] == -1:
24 isWater[nextRow][nextCol]= isWater[row][col] + 1
25 queue.append([nextRow,nextCol])
26
27 return isWater
28
29 def inBounds(self, row, col, rowMax, colMax):
30 return not (row<0 or col<0 or col>=colMax or row>=rowMax)
31
O(m*n)
, as we visit every location in the matrix once.O(m*n)
because the queue length could come within one of the matrix size if ~all of the matrix were water.interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
Interview prep and job hunting are chaos and pain. We can help. Really.