setting the stage

  1. Mental Focus
  2. Learn a programming language
  3. Learn Data structures and algorithms
  4. Complete Leetcode / programming practice
  5. Software Engineering Concepts
  6. Behavioural Practice
  7. Best Methods of Applying
  8. Interview Process & Internal Guidelines.

process for problem solving

  • always read the problem statement twice.

    • ask clarifying questions
  • try think of different ways to solve the problem
  • think end-to-end of the best solutions based on complexity
  • write the algorithm from patterns in drawing
  • code it out
  • try and improve it once you think you're finished.
  • go through other solutions (even if you answered correctly)

problems

217. duplicate values | easy

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

return len(set(nums)) != len(nums)

268. missing number | easy

Array nums, containing n distinct numbers from [0,n], return the only number in the range missing from the array.

input [3,0,1]
output 2

note that there is room for arbitrage here. the instinctive solution is a nested for loop $O(n^2)$, but using a sum() call, we can complete this in $O(n)$.

the trick is to realise the structure of the problem only asking for the single missing number.

  nums = [3,1,0]
  return sum(range(len(nums)+1)) - sum(nums)
2

profiling: 0ms runtime, 18.5MB

but I think a hashmap solution might be equally possible too.

  from collections import defaultdict
  hashmap = defaultdict(int)
  nums = [3,1,0]
  for item in nums:
      hashmap[item] += 1 
  for i in range(len(nums) + 1):
      if i not in hashmap:
	  return i
2

profiling: 11ms runtime, 18.8MB

448. find all numbers disappeared in an array | easy

seems like a continuation of the previous question

  nums = [4,3,2,7,8,2,3,1]
  missing = []
  uniques = set(nums)
  for i in range(1,len(nums)+1):
      if i not in uniques:
          missing.append(i)

  missing
5 6

profiling: 27ms runtime, 31.2MB space.

    from collections import defaultdict

    missing = []
    hashmap = defaultdict(int)
    for item in nums:
        hashmap[item] += 1
    for i in range(1,len(nums) + 1):
        if i not in hashmap:
            missing.append(i)

    missing
5 6

profiling: 53ms, 31.5MB

a constant space solution:

  for i in range(len(nums)):
    temp = abs(nums[i]) - 1
    if nums[temp] > 0:
      nums[temp] *= -1

    res = []
    for i, n in enumerate(nums):
      if n > 0:
        res.append(i+1)

    return res

1. two sum 

  from collections import defaultdict


  def myfunc(nums, target):
      hashmap = defaultdict(int)
      for item in nums:
          if target - item in hashmap:
              return (item, target - item)
          hashmap[item] += 1
          
  myfunc([2,7,11,15], 9)
7 2

1365. how many numbers are smaller than the current number | easy 

  def myfunc():
      nums = [8,1,2,2,3]

      counts = []
      for a in nums:
          count = 0
          for b in nums:
              if a != b and b<a:
                  count += 1
          counts.append(count)

      return counts
  myfunc()
4 0 1 1 3

this problem took a reasonable amount of time to solve, but I did manage to do it with a runtime of 1ms eventually.

the above solution I could produce within 5 minutes: $O(n^2)$; 111ms runtime with 17.7MB space.

eventually I eeked out this:

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        """
        counts = []
        for a in nums:
            count = 0
            for b in nums:
                if a != b and b < a:
                    count += 1
            counts.append(count)
        return counts
        """

        mynums = sorted(nums)
        iteration = -1
        hashMap = {}
        for item in mynums:
            iteration += 1
            if item in hashMap:
                continue
            hashMap[item] = iteration
        return [hashMap[item] for item in nums]
1266. Minimum Time Visiting All Points

I gave myself a 10 minute hard cap on this problem and managed to come up with the following solution:

  class Solution:
      def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
          N = len(points)
          total = 0
          for i in range(N-1):
              a = points[i]
              b = points[i+1]
              x_dist = abs(a[0] - b[0])
              y_dist = abs(a[1] - b[1])
              total += (x_dist % 2)
              total += (y_dist % 2)
              total += (y_dist // 2)
              total += (x_dist // 2)
          return total

but then I failed the second test which made me refactor the logic slightly into 

  class Solution:
      def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
          N = len(points)
          total = 0
          for i in range(N-1):
              a = points[i]
              b = points[i+1]
              x_dist = abs(a[0] - b[0])
              y_dist = abs(a[1] - b[1])
              if x_dist == 0 or y_dist == 0:
                  total += x_dist + y_dist
              else:
                  total += (x_dist % 2)
                  total += (y_dist % 2)
                  total += (y_dist // 2)
                  total += (x_dist // 2)
          return total

but even this logic was wrong.

it turns out that the correct approach is to realise the minumum number of moves is thresholded by the maximum difference along the axis: max(x_dist, y_dist)

whilst we could just replace my modulo logic with this:

  for i in range(N-1):
      a = points[i]
      b = points[i+1]
      x_dist = abs(a[0] - b[0])
      y_dist = abs(a[1] - b[1])
      total += max(x_dist, y_dist)
  return total

but cleverly, we can also use a for loop to the same effect:

  class Solution:
      def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
          res = 0
          x1, y1 = points.pop() # tuple unpacking
          while points:
              x2, y2 = points.pop()
              x_dist = abs(x1-x2)
              y_dist = abs(y1-y2)
              res += max(x_dist, y_dist)
              x1, y1 = x2, y2

          return res

profiling: the above solution was 1ms, compared to the for loop version which was 0ms.

54. Spiral Matrix

to begin, I gave myself 25 minutes to at least solve the first couple of cases

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        M = len(matrix)
        first_row = matrix[0]
        last_row = matrix[M-1]
        N = len(first_row)

        output = []
        layer = 1
        for item in first_row:
            output.append(item)

        # first right layer
        for i in range(1,M):
            output.append(matrix[i][N-1])
        
        # bottom layer
        for i in reversed(last_row):
            if i == output[-1]:
                continue
            output.append(i)
        
        curr_row = matrix[M-1-layer]
        for i in range(len(curr_row)):
            if i <= N - 1 - layer:
                output.append(curr_row[i])

        return output

after this, I looked at a solution and noticed that they popped off the first row.

I think my own approach with layer subtraction might also work.

after a couple more hours I have produced this:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        first_row = matrix[0]
        last_row = matrix[m-1]
        n = len(first_row)


        output = []
        while len(output) != m*n:
            print(output)
            #print(matrix)
            M = len(matrix)
            first_row = matrix[0]
            last_row = matrix[M-1]
            N = len(first_row)

            # top layer
            for i in range(N):
                output.append(first_row[i])
    
            print("top done")
            print(output)

            # right layer
            for row in matrix[1:]:
                output.append(row[-1])
            
            print("right done")
            print(output)

            # bottom layer
            for i in reversed(last_row[:-1]):
                if last_row != first_row:
                    output.append(i)
            
            print("bottom done")
            print(output)

            # left side
            for row in reversed(matrix[1:-1]):
                if M != 1 and N != 1:
                    output.append(row[0])

            print("left done")
            print(output)
            matrix = [i[1:-1] for i in matrix[1:-1]]
            print("matrix: ", matrix)
            

        return output

which removes the layer logic and strips down the matrix after each layer into a smaller matrix.

this way the top, right, bottom and left logical layers are very easy to implement.

notably I learned about slicing during this question.

  def spiralOrder(matrix):
    ret = []
    while matrix:
      # 1. add first row / list of matrix
      ret += (matrix.pop(0))

      # 2. append last element of all lists in order
      if matrix and matrix[0]:
        for row in matrix:
          ret.append(row.pop())

      # 3. add reverse of last row / list
      if matrix:
        ret+=(matrix.pop()[::-1])

      # 4. append first element of all rows / lists in reverse
      if matrix and matrix[0]:
        for row in matrix[::-1]:
          ret.append(row.pop(0))

    return ret
solution

time complexity: $O(mn)$

200. Number of Islands | medium 
  def NumIslands(grid):
      if not grid:
          return 0

      def bfs(r, c):

          q = deque()
          visit.add((r,c))
          q.append((r,c))

          while q:
              row, col = q.popleft()
              directions = [[1,0],[-1,0],[0,1],[0,-1]]
              for dr, dc in directions:
                  r,c = row+dr, col+dc

                  if (r in range(rows) and c in range(cols) and grid[r][c]=='1' and (r,c) not in visit):
                      q.append((r,c))
                      visit.add((r,c))

      count = 0
      rows = len(grid)
      cols = len(grid[0])
      visit = set()

      for r in range(rows):
          for c in range(cols):
              if grid[r][c] == '1' and (r,c) not in visit:
                  bfs(r,c)
                  count += 1
      return count
  def countIslands(grid):
      if not grid:
          return 0

      rows, cols = len(grid), len(grid[0])
      visited = set()
      islands = 0

      def bfs(r,c):
          q = collections.deque()
          visit.add((r,c))
          q.append((r,c))

          while q:
              row, col = q.popleft()
              directions = [[1,0],[-1,0],[0,1],[0,-1]]
              for dr, dc in directions:
                  r, c = row + dr, col + dc
                  if (r in range(rows) and
                  c in range(cols) and
                  grid[r][c] == '1' and
                  (r, c) not in visited:
                  q.append((r, c))
                  visited.add((r,c))
    
      for r in range(rows):
          for c in range(cols):
              if grid[r][c] == '1' and (r,c) not in visited:
                  bfs(r,c)
                  islands += 1
      return islands

my leetcode submission:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        count = 0
        m = len(grid)
        n = len(grid[0])

        def bfs(r, c):
            q = deque()
            visited.add((r,c))
            q.append((r,c))

            while q:
                row, col = q.popleft()
                directions = [[1,0],[0,1],[-1,0], [0,-1]]
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if (r in range(m) and c in range(n) and grid[r][c] == "1" and (r,c) not in visited):
                        q.append((r,c))
                        visited.add((r,c))
            # manipulate the visited set

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and (i,j) not in visited:
                    count += 1
                    bfs(i,j)

        return count
121. Best time to buy and sell stock | easy 
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total_max = 0
        N = len(prices)
        for i in range(N):
            loop_max = 0
            for j in range(N):
                if i < j:
                    if prices[j] - prices[i] > loop_max:
                        loop_max = prices[j] - prices[i]
            if loop_max > total_max:
                print(i,j)
                total_max = loop_max

        return total_max

managed to pass 198/212 test cases with this O(n^2) bruteforce solution.

I gave myself 10 minutes to solve this (on account of it being an easy problem). but I couldn't figure out how to leverage the two pointers.

should we sort the array? but then we lose dates..

  def maxProfit(prices):
      l, r = 0, 1

      maxP = 0

      while r!=len(prices):
          if prices[l] < prices[r]:
              prof = prices[r] - prices[l]
              maxP = max(maxP, prof)

          else:
              l = r

          r += 1

      return maxP

I also understood from previous pointer questions and the one above, that we can condense some of my if/else logic into leveraging the max function

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total_max = 0
        N = len(prices)
        for i in range(N):
            loop_max = 0
            for j in range(N):
                if i < j:
                    loop_max = max(loop_max, prices[j]-prices[i])
            total_max = max(loop_max, total_max)

        return total_max

unfortunately, I still only pass 198/212 tests with this approach.

977. Squares of a sorted array | easy

Naturally, my solution looked like:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted([x**2 for x in nums])

but stoney codes provided this cool solution, though it does not work :(; it fails on [-5,-4,-3,-2,-1] producing [25,9,4,1] where it should instead make [1,4,9,25].

  def sortedSquares(nums):
      if not nums:
          return nums

      if nums[0] > 0:
          return [num**2 for num in nums]
      # this is good arbitrage; we know the input array is sorted, and squaring is monotonic
      # so the non-decreasing structure will be preserved.
      # also, if the first element is positive, then the rest will be too.

      # find index first positive
      m = 0
      for i, n in enumerate(nums):
          if n>= 0:
              m = i
              break

      #A = positive nums
      #B = reversed negatives
      A, B = nums[m:], [-1*n for n in reversed(nums[:m])]

      def merge(A,B):
          a = b = 0

          ret = []

          while a < len(A) and b < len(B):
              if A[a] < B[b]:
                  ret.append(A[a])
                  a+=1

              else:
                  ret.append(B[b])
                  b+= 1

          if a < len(A):
              ret.extend(A[a:])
          else:
              ret.extend(B[b:])

          return [n**2 for n in ret]

      return merge(A,B)

we also fashioned a while solution:

  class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        answer = collections.deque()
        l, r = 0, len(nums) - 1
    
        while l <= r:#O(n)
            left, right = abs(nums[l]), abs(nums[r])
            if left > right:
                answer.appendleft(left * left)
                l += 1
            else:
                answer.appendleft(right * right)
                r -= 1
        return list(answer)

the absolute squared value of a negative and positive number are the same!

15. 3Sum | medium

"medium questions tend to merge concepts from 2 easy questions"

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        """since the array is sorted, we're better off using two pointers which has a better space complexity
        def twoSum(target: int,nums: List[int]) -> List[List[int]]:
            hashMap = defaultdict(int)
            combos = []

            for num in nums:
                if target - num not in hashMap:
                    hashMap[num] += 1
                else:
                    candidate = [num, target -num]
                    if candidate not in combos:
                        combos.append(candidate)
            return combos
        """
            
        combo3 = []
        uniques = set()
        nums.sort()
        visited = defaultdict(int)
        for i in range(len(nums)):
            if visited[nums[i]] > 0:
                continue
            visited[nums[i]] +=1
            # we will never make 0
            if nums[i] > 0:
                break
            
            nums2 = nums[:i] + nums[i+1:]
            target = -nums[i]
            # recall the array is sorted
            l = 0
            r = len(nums2) -1
            combos = []
            while l < r:
                sum2 = nums2[l] + nums2[r]
                if sum2 > target:
                    # reduce right pointer
                    r -= 1
                elif sum2 < target:
                    # accrue larger sum
                    l += 1
                else: #when equal
                    candidate = [nums2[l], nums2[r]]
                    #if candidate not in combos:
                    # i don't think it's possible to find repeats!
                    r -= 1
                    l += 1
                    combos.append(candidate)
            twoS = combos

            if len(twoS) > 0:
                # success
                for lst in twoS:
                    triplet = sorted([nums[i], lst[0], lst[1]])
                    trip_val = "".join(str(n) for n in sorted([nums[i],lst[0],lst[1]])) 
                    if trip_val not in uniques:
                        combo3.append(triplet)
                        uniques.add(trip_val)

        return combo3

this took me multiple hours to big brain through.

167. 2Sum Part II | Medium

this was piss:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l = 0
        r = len(numbers) - 1
        while l <= r:
            left = numbers[l]
            right = numbers[r]
            if left + right > target:
                # reduce sum
                r -= 1
            elif left + right < target:
                # increase sum (contigent on increasing sort)
                l += 1
            else:
                return [l+1, r+1]
        return [0,0]
845. Longest Mountain in Array | medium

damn, their solution was much better than whatever junk was floating around in my brain.

I was thinking of starting from the left and iterating towards the right, but wasn't sure how to reset the counter or deal with the overlapping tectonic plates :(

  class Solution:
      def longestMountain(self, arr: List[int]) -> int:
          max_length = 0

          for i in range(1, len(arr) - 1):
              if arr[i-1] < arr[i] > arr[i+1]:
                  l = r = i
                  while l > 0 and arr[l] > arr[l-1]:
                      l -= 1
                  while r < len(arr)-1 and arr[r] > arr[r+1]:
                      r += 1 # keep climbing up
                  
                  max_length = max(max_length, r - l + 1)

          return max_length