More patterns for coding interviews ||

4- Multisource BFS

class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
n, level = len(grid), 0
queue = deque([(i, j) for i, j in product(range(n), range(n)) if grid[i][j]])
if len(queue) in (0,n*n): return -1
while queue:
for _ in range(len(queue)):
i,j = queue.popleft()
for x, y in [(1,0), (-1, 0), (0, 1), (0, -1)]:
xi, yj = x+i, y+j
if 0 <= xi < n and 0 <= yj < n and grid[xi][yj] == 0:
queue.append((xi, yj))
grid[xi][yj] = 1
level += 1
return level-1
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
n, m, level, seen = len(matrix),len(matrix[0]), 0, set()
queue = deque([(i, j) for i, j in product(range(n), range(m)) if not matrix[i][j]])

while queue:
for _ in range(len(queue)):
i,j = queue.popleft()
if (i, j) not in seen:
seen.add((i, j))
matrix[i][j] = level
for x, y in [(1,0), (-1, 0), (0, 1), (0, -1)]:
xi, yj = x+i, y+j
if 0 <= xi < n and 0 <= yj < m: queue.append((xi, yj))
level += 1
return matrix

5- Running sum

class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
zeros_to_left, ones_to_right, minflips = [0]*(len(s)+1),[0]*(len(s)+1), float('inf')

for i, x in enumerate(s): zeros_to_left[i+1]=zeros_to_left[i]+(x=='0')
for i, x in enumerate(s[::-1]): ones_to_right[-i-2]=ones_to_right[-i-1]+(x=='1')
for i in range(len(s)+1): minflips = min(minflips, len(s)-zeros_to_left[i]-ones_to_right[i])

return minflips
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
left_prod, right_prod = [1]*len(nums), [1]*len(nums)

for i in range(1,len(nums)): left_prod[i] = left_prod[i-1] * nums[i-1]
for i in range(len(nums)-2,-1,-1): right_prod[i] = right_prod[i+1]* nums[i+1]
for i in range(len(nums)): nums[i]=left_prod[i]*right_prod[i]

return nums

6- Range addition (Amazon)

class Solution:
def RangeSum(self, n, updates):
ans = [0]*n
for update in updates:
ans[update[0]]+=update[2]
if update[1]<n-1: ans[update[1]+1]-=update[2]
for i in range(1, n): ans[i]+=ans[i-1]
return ans

7- Matrix diagonal iteration

class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
memo = {}
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i-j in memo and memo[i-j] != matrix[i][j]: return False
memo[i-j] = matrix[i][j]
return True
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat[0]), len(mat)
table = {}
for i in range(n):
for j in range(m):
table[i-j] = table.get(i-j, []) + [mat[i][j]]

for k,v in table.items(): v.sort(reverse=True)

for i in range(n):
for j in range(m):
mat[i][j] = table[i-j].pop()

return mat

8- Monotonic stack

class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack, ans = [], [-1] * len(nums2)
for i, num in enumerate(nums2):
while stack and nums2[stack[-1]] < num: ans[stack.pop()] = num
stack.append(i)
return [ans[nums2.index(num)] for num in nums1]
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
stack, ans, arr = [], 0, [float('-inf'),*arr,float('-inf')]
for i, num in enumerate(arr):
while stack and arr[stack[-1]]>num:
j = stack.pop()
ans += arr[j] * (i-j) * (j-stack[-1])
stack.append(i)
return ans%(10**9 + 7)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store