Sign in

  • Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

  • Given a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'.
  • The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. …

  • Given an m x n grid of characters board and a string word, return true if word exists in the grid.
  • The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. …

  1. Generate permutations
  • DFS + loop with increasing index
def dfs(self, count, nums, s, v):
if count == len(nums):
self.res.append(s[:])
return
for i in range(len(nums)):
if v[i]==1:
continue
v[i]=1
s.append(nums[i])

self.dfs(count+1,nums,s,v)
s.pop()
v[i] = 0
  • DFS + loop with increasing
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def dfs(idx, s, count):
if count == k:
res.append(s[:])
for i in range(idx, n):
s.append(i+1)
dfs(i+1, s, count+1)
s.pop()

dfs(0,[], 0)
return res
  • Sorting + Compare current and the previous index
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = [[]]

def dfs(idx, s):
if idx == len(nums):
return
for i in range(idx, len(nums)):
if i>idx and nums[i] == nums[i-1]:
continue
s.append(nums[i])
res.append(s[:])
dfs(i+1, s)
s.pop()

nums.sort()
dfs(0,[])
return res

  • Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1
Output: ["()"]
  • DFS + Two Pointers (left, right counters)
  • Simply use the pointers to keep track of the count
  • When l>r → we skip and no action because the number of remaining ‘(‘ should always be less than ‘)’ !
  • Else we append the left or right parentheses, and pop after each recursion call
  • Time: O(2^n) with n = the number of each parentheses
  • Space: ?
class Solution:
def generateParenthesis(self, n: int) -> List[str]:

res = []
def dfs(l, r, s):
if l+r==0:
res.append(''.join(s))
if l>r:
return
if l>0:
s.append('(')
dfs(l-1,r,s)
s.pop()

if r>0:
s.append(')')
dfs(l,r-1,s)
s.pop()
dfs(n,n, [])

return res

  • Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
  • By taking consideration of the problem constraint, using iterative solution will not pass the tests
  • Recursive DFS with depth set to the length of…

  1. while left < right
  • sort first
  • move the two pointers from opposite directions
  • until they meet
  • Traverse the longer string, and move the pointer on the shorter one
  • Check the index of the pointer to confirm
  • usually not sort
  • used when we are trying to compare 2 strings
  • until one of them failed the condition

  • Given an array people where people[i] is the weight of the ith person, and an infinite number of boats
  • Each boat carries at most two people at the same time
  • Return the minimum number of boats to carry every given person.
  • Set the left = 0, and right…

Iris S

Data Engineering & Analytics

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