Tutorial

setting the stage

Mental Focus
Learn a programming language
Learn Data structures and algorithms
Complete Leetcode / programming practice
Software Engineering Concepts
Behavioural Practice
Best Methods of Applying
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

arrays

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)

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

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

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

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 | easy

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)

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()

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 | easy

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 | medium

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

Code Snippet 1: 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

arrays - two pointers

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

arrays - sliding window

219. Contains Duplicate II | easy

gosh it is nice to be back in emacs haha

yikes, that was kind of embarassing. I couldn’t solve it fast enough.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        """
        # O(n^2)
        N = len(nums)
        for i in range(N):
            for j in range(i+1, N):
                if abs(i - j) <= k and nums[i] == nums[j]:
                    return True
        return False
        """
        """
        l, r = 0, 1
        if k == 0:
            return False

        while l < len(nums):
            while r < len(nums) and abs(l - r) <= k:
                if nums[l] == nums[r]:
                    return True
                r += 1
            l += 1
            r = l + 1
        return False
        """

apparently we can solve it using sets and dictionaries. I’ll spend another 5 minutes thinking about this:

class Solution:
    def containsNearbyDuplicate(self, nums: int) -> bool:
        seen = set()
        for i, num in enumerate(nums):
            if num in seen:
                return True
            seen.add(num)
            if len(seen) > k:
                seen.remove(nums[i-k])
        return False

35 ms with 30.72MB memory

def containsNearbyDuplicate(self, nums, k):
    dic = {}
    for i, v in enumerate(nums):
        if v in dic and i - dic[v] <= k:
            return True
        dic[v] = i
    return False

30ms but with more memory; 36.59MB

1200. Minimum absolute difference | easy

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        mins = []
        arr.sort() # O(n log n)
        l, r = 0, 1
        dif = max(arr) - min(arr)
        while r < len(arr):
            a, b = arr[l], arr[r]
            cur_dif = b - a
            if cur_dif < dif:
                mins = []
                mins.append((a, b))
            elif cur_dif == dif:
                mins.append((a, b))
            dif = min(dif, cur_dif)
            r += 1
            l += 1
        return mins

[4,2,1,3]

sort: [1,2,3,4] #O(n log n)

[(1,2), (2,3), (3,4)]

209. Minimum Size Subarray Sum | medium

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l, r = 0, 0
        N = len(nums)
        minimal_subarray_length = N + 1
        while r <= len(nums):
            sub_arr = nums[l:r]
            if len(sub_arr) >= minimal_subarray_length:
                l += 1
                r = l
                break
            sub_sum = sum(sub_arr)
            if sub_sum >= target:
                minimal_subarray_length = min(minimal_subarray_length, len(sub_arr))
                l += 1
                r = l
            r += 1
            print(sub_arr)

        return minimal_subarray_length if minimal_subarray_length <= N else 0

wrong!

def mindiff(arr, t):
    l = 0
    total = 0
    res = float('inf')

    for r in range(len(nums)):
        total += nums[r]

        while total >= t:
            res = min(res, r-l+1)

            total -= nums[l]

            l+=1
    if res == float('inf'):
        return 0
    else:
        return res

bit manipulation

136. Single Number | easy

naturally this can be done in \(O(n)\) time in a number of ways:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hashMap = defaultdict(int)
        for num in nums:
            hashMap[num] += 1
        return [key for key, value in hashMap.items() if value == 1][0]

still \(O(n)\) space complexity.

we can do it with XOR:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for num in nums:
            xor^=num
        return xor

lowkey bonkers, but it does work. down from 11ms to 3ms.

dynamic programming

322. Coin Change | medium

it is a dynamic programming problem. I do not know how to immediately solve it:

def coinChange(coins, amount):
    dp = [amount +1] * (amount+1)
    dp[0] = 0

    for i in range(1, amount+1):
        for c in coins:
            if (i-c) >= 0:
                dp[i] = min(dp[i], 1 + dp[i-c])
    return dp[amount] if (dp[amount] != amount + 1) else -1

time: O(amount * len(coins)) space: O(amount)

70. Climbing Stairs | easy

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0] * (n+1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

this one was actually quite doable. it is even moreso doable in that the array can be shortened down to just maintaining 2 constants

time: O(n) space: O(n)

53. Maximum Subarray | medium

you should understand the design of this algorithm. especially for an input such as [-2,1,-3,4,-1,2,1,-5,4].

we consider the problem of keeping n if and only if dp[i-1] added to this n is larger than just n. if it is, then it means this previous item is worth keeping, but if not, then we can just take n.

this pattern continues to produce [-2,1,-2,4,3,5,6,1,5] of which whose max is just 6.

def msub(arr):
    dp = [0] * len(arr)
    for i, n in enumerate(arr):
        dp[i] = max(n,dp[i-1]+n)

    return max(dp)

time: O(n) space: O(n)

but once again there is not much reason why we need to keep the n length array. we can just keep 2 variables:

def maxSubArr(arr):
    maxSum = arr[0]
    currentSum = 0

    for n in arr:
        if currentSum = 0:
            currentSum = 0

        currentSum += n
        maxSum = max(maxSum, currentSum)
    return maxSum

338. Counting Bits | easy

I did this naïvely with a string manipulation:

def countBits(self, n: int) -> List[int]:
    ans = []
    for i in range(n+1):
        temp = bin(i)
        ans.append(temp[2:].count('1'))
    return ans

which ran in 15ms with 18.5MB of memory

there is also this dp solution:

def countBits(self, n: int) -> List[int]:
    dp = [0] * (n + 1)
    offset = 1

    for i in range(1, n+1):
        if offset * 2 == i:
            offset = i
        dp[i] = 1 + dp[i-offset]

    return dp

^5ms runtime; 18.55MB memory. not bad at all

303. Range Sum Query - Immutable | easy

this question was cute

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums


    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left:right+1])

I choked on the initialisation, but beyond that, we can also use prefix-sums to pay a cost once and then have quick summing thereafter:

class NumArray:

    def __init__(self, nums: List[int]):
        """
        prefix_sum = [0] * (len(nums) + 1)
        prefix_sum[0] = 0
        for i, num in enumerate(nums):
            prefix_sum[i+1] += prefix_sum[i] + num

        self.prefix_sum = prefix_sum
        """
        self.acc_nums = [0]
        for num in nums:
            self.acc_nums.append(self.acc_nums[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        return self.acc_nums[right+1] - self.acc_nums[left]

and then 7ms thereafter.

technically some leetcode solutions mark this as “dp” on account of the sub-problem repetition.

backtracking

at least this way, I can add some notes at the top of the sections!

permutations and combinations both refer to selecting items from some set of data: permutation refers to the ordering or arranging the data in a different type of way combinations is referring to the different selections of data from that dataset.

order of items is important for permutations but not for combinations

784. Letter Case Permutation | medium

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        output = [""]

        for c in s:
            tmp = []
            if c.isalpha():
                for o in output:
                    tmp.append(o+c.lower())
                    tmp.append(o+c.upper())
            else:
                for o in output:
                    tmp.append(o+c)
            output = tmp
        return output

time: O(2^n) space: O(2^n)

78. Subsets | medium

def subsets(nums):
    def backtrack(start, path):
        result.append(path[:]) # append copy of path snapshot
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i+1, path)
            path.pop()

    result = []
    backtrack(0,[])
    return result

we use shallow copies in backtracking because they efficiently capture the current state of the path when dealing with simple immutable elements like ints could have used deep copy, but that would make this solution less efficient. deep copies are only necessary when dealing with nested or mutable data

time: O(N*2^n) space: O(N*2^n)

77. Combinations | medium

def combine(n, k):
     def backtrack(start, path):
        if len(path) == k:
            result.append(path[:]) # shallow copy
            return
        for i in range(start, n+1):
            path.append(i)
            backtrack(i+1,path)
            path.pop()
    result = []
    backtrack(1, [])
    return result

time: \(O(k \cdot {n\choose k})\) space: \(O(k)\)

46. Permutations | medium

def permute(nums):
    def backtrack(start, end):
        if start == end:
            result.append(nums[:]) # shallow copy
            return
        for i in range(start, end):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start+1, end)
            nums[start], nums[i] = nums[i], nums[start]
    result = []
    backtrack(0, len(nums))
    return result

37. Sudoku Solver | Hard

inspired by lazily copying the above (somewhat) boring backtrackings, I decided to apply what I learned to solve Sudokus:

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        N = len(board)
        visited = set()
        empties = []

        def hashBoard():
            """
            total = 0
            for row in range(N):
                for col in range(N):
                    total += board[row][col]
            visited.add(total)
            """
            # again, a garbage hash.
            hashed_board = "".join("".join(i for i in row) for row in board)

            print("hashed board:", hashed_board)
            return hashed_board

        def fullGroup(group: List[str]) -> bool:
            uniques = list(set(group))
            if len(uniques) != N:
                return False
            return True

        def checkGroup(group: List[str]) -> bool:
            uniques = list(set(group))
            counts = {s: group.count(s) for s in uniques}
            #del counts['.']  # we don't care about how many empties
            counts.pop('.', None)
            if any(value > 1 for value in counts.values()):
                return False
            if any(int(key) > 9 or int(key) < 1 for key in counts.keys()):
                return False
            return True

        def isSolved():
            """
            rowSum = 0
            for row in board:
                if sum(row) != WIN_SUM:
                    return False
            """
            # this is a stupid way to check! you can literally do 9 5's
            ###########################################################
            # check rows:
            for row in board:
                if not (checkGroup(row) and fullGroup(row)):
                    return False

            # check columns:
            for i in range(N):
                col = [row[i] for row in board]
                if not (checkGroup(col) and fullGroup(col)):
                    return False

            # check grids:
            for row_offset in range(0, N, 3):
                for col_offset in range(0, N, 3):
                    subgrid = []
                    for r in range(row_offset, row_offset + 3):
                        for c in range(col_offset, col_offset + 3):
                            subgrid.append(board[r][c])
                    if not (checkGroup(subgrid) and fullGroup(subgrid)):
                        return False
            return True

        def validMove(board_state: List[List[str]], pos: tuple) -> List[int]:
            curr_num = board_state[pos[0]][pos[1]]
            valid_moves = []
            for i in range(1, N+1):  # checking candidates
                board_state[pos[0]][pos[1]] = str(i) # set the candidate in board
                row = board_state[pos[0]] # save row as var, with new candidate
                col = [r[pos[1]] for r in board_state] # set col with candidate
                subgrid = []
                row_offset = (pos[0] // 3) * 3
                col_offset = (pos[1] // 3) * 3
                for r in range(row_offset, row_offset + 3):
                    for c in range(col_offset, col_offset + 3):
                        subgrid.append(board_state[r][c])

                if not checkGroup(row):
                    board_state[pos[0]][pos[1]] = curr_num # reset the board_state
                    continue  # the i value does not work.
                # check col
                if not checkGroup(col):
                    board_state[pos[0]][pos[1]] = curr_num # reset the board_state
                    continue  # the i value does not work.
                # check containing subgrid
                if not checkGroup(subgrid):
                    board_state[pos[0]][pos[1]] = curr_num # reset the board_state
                    continue  # the i value does not work.
                # position is valid
                board_state[pos[0]][pos[1]] = curr_num # reset the board_state
                valid_moves.append(str(i))
            return valid_moves

        def find_empties():
            for i, row in enumerate(board):
                for j, col in enumerate(row):
                    if col == '.':
                        empties.append((i, j))

        def dfs():
            dfs_rec(board, empties.pop(0))

        def dfs_rec(board_state: List[List[str]], pos: tuple):
            print(board)
            if isSolved():
                return True
            hashed_board = hashBoard()
            if hashed_board in visited:
                return False
            visited.add(hashed_board)
            valid_moves = validMove(board_state, pos) # list of strings

            for move in valid_moves:
                original = board_state[pos[0]][pos[1]]
                board_state[pos[0]][pos[1]] = move
                dot = empties.pop(0)
                if dfs_rec(board_state, dot):
                    return True
                else:
                    # undo move
                    empties.append(dot)
                    board_state[pos[0]][pos[1]] = original
            #return True


        find_empties()
        while not isSolved():
            dfs()
            break

if __name__ == "__main__":
    S = Solution()
    board = [["5","3",".",".","7",".",".",".","."],
             ["6",".",".","1","9","5",".",".","."],
             [".","9","8",".",".",".",".","6","."],
             ["8",".",".",".","6",".",".",".","3"],
             ["4",".",".","8",".","3",".",".","1"],
             ["7",".",".",".","2",".",".",".","6"],
             [".","6",".",".",".",".","2","8","."],
             [".",".",".","4","1","9",".",".","5"],
             [".",".",".",".","8",".",".","7","9"]]
    print(board)
    S.solveSudoku(board)

it took me about 4 hours to come up with this, and still the solution is highly unoptimised.

it turns out that my isSolved() calls are very expensive and poor design. also, the empties.pop(0) is a bottle-neck.

so is the checkGroup function.

instead a better solution looks like:

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        N = len(board)
        empties = []

        # ------------------------------------------------------------------
        # (Kept from your code, but no longer used in the main DFS)
        # ------------------------------------------------------------------
        def fullGroup(group: List[str]) -> bool:
            uniques = list(set(group))
            if len(uniques) != N:
                return False
            return True

        def checkGroup(group: List[str]) -> bool:
            seen = set()
            for ch in group:
                if ch == '.':
                    continue
                if ch in seen:
                    return False
                seen.add(ch)
            return True

        def isSolved() -> bool:
            # Full-board validator, not used inside DFS now
            # check rows:
            for row in board:
                if not (checkGroup(row) and fullGroup(row)):
                    return False

            # check columns:
            for i in range(N):
                col = [row[i] for row in board]
                if not (checkGroup(col) and fullGroup(col)):
                    return False

            # check grids:
            for row_offset in range(0, N, 3):
                for col_offset in range(0, N, 3):
                    subgrid = []
                    for r in range(row_offset, row_offset + 3):
                        for c in range(col_offset, col_offset + 3):
                            subgrid.append(board[r][c])
                    if not (checkGroup(subgrid) and fullGroup(subgrid)):
                        return False
            return True

        # ------------------------------------------------------------------
        # NEW: O(1) constraint tracking with minimal changes to structure
        # ------------------------------------------------------------------
        rows  = [set() for _ in range(N)]
        cols  = [set() for _ in range(N)]
        boxes = [set() for _ in range(N)]  # index = (r//3)*3 + c//3

        def find_empties():
            for i, row in enumerate(board):
                for j, val in enumerate(row):
                    if val == '.':
                        empties.append((i, j))
                    else:
                        rows[i].add(val)
                        cols[j].add(val)
                        boxes[(i // 3) * 3 + (j // 3)].add(val)

        # reuse your validMove name/signature, but now use the row/col/box sets
        def validMove(board_state: List[List[str]], pos: tuple) -> List[str]:
            r, c = pos
            b = (r // 3) * 3 + (c // 3)
            valid_moves = []
            for d in "123456789":
                if d not in rows[r] and d not in cols[c] and d not in boxes[b]:
                    valid_moves.append(d)
            return valid_moves

        # ------------------------------------------------------------------
        # DFS using index into `empties` (no pop/append, no full-board checks)
        # ------------------------------------------------------------------
        def dfs_rec(idx: int) -> bool:
            if idx == len(empties):
                return True  # all empties filled legally

            r, c = empties[idx]
            if board[r][c] != '.':
                return dfs_rec(idx + 1)

            b = (r // 3) * 3 + (c // 3)
            for move in validMove(board, (r, c)):
                # place
                board[r][c] = move
                rows[r].add(move)
                cols[c].add(move)
                boxes[b].add(move)

                if dfs_rec(idx + 1):
                    return True

                # undo
                board[r][c] = '.'
                rows[r].remove(move)
                cols[c].remove(move)
                boxes[b].remove(move)

            return False

        find_empties()
        dfs_rec(0)

linked lists

876. Middle of a linked list | easy

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        N = 0
        counter = 0
        curr = head
        while curr:
            N += 1
            curr = curr.next
        curr = head
        stopAt = floor(N/2)
        while counter < stopAt:
            curr = curr.next
            counter += 1
        return curr

pretty chill, took me a couple minutes to remember how to use linked lists, particularly my only bug was accidentally calling curr.next() as a function which blew up with:

Runtime Error
- and therein, TypeError: 'ListNode' object is not callable
- which is fair.

141. Linked List Cycle | easy

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        curr = head
        visited = set()
        while curr:
            if curr not in visited:
                visited.add(curr)
            else:
                return True
            curr = curr.next
        return False

I hicked up for a second because I accidentally wrote the True and False returns in the wrong order; the question is about “finding cycles”!

206. Reverse Linked List | easy

for this one I had to consult the video; I was thinking of temporary variables.

it also turns out that I have previously attempted this problem in C:

struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *new = NULL;
    struct ListNode *curr = head;
    while (curr != NULL) {
        struct ListNode *tmp = curr->next;
        curr->next = new;
        new = curr;
        curr = tmp;
    }
    return new;

}

and it turns out the solution of the video was also using temporary variables:

prev = None
curr = head
while curr:
    next_p = curr.next
    curr.next = prev

    prev = curr
    curr = next_p

return prev

which looks like this in its entirety:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None or head.next == None:
            return head

        new = None
        curr = head
        while curr:
            tmp = curr.next
            curr.next = new
            new = curr
            curr = tmp
        return new

203. Remove Linked List Elements | easy

this one was a huge bother for me. particularly the cases where head =[7,7,7,7] and I was being plagued with AttributeErrors when trying to access .next on Nonetypes

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        curr = head
        dummy = ListNode(-1, head)
        prev = dummy
        while curr:
            if curr.val == val:
                if curr.next == val:
                    curr = curr.next.next
                    continue
                else:
                    prev.next = curr.next
                    curr = curr.next
                    continue
            else:
                prev = curr
                curr = curr.next
        return dummy.next

92. Remove Linked List II | medium

I continue to struggle with the ‘dummy’ pointer pattern. here is my original attempt, which tried to make use of code from problem 206 (reverse linked list):

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    # code to reverse an entire list:

    curr = head
    leftp = head
    leftprev = head
    rightp = head
    while curr.next:
        if curr.next.val == left:
            leftprev = curr
        if curr.val == left:
            leftp = curr
        if curr.val == right:
            rightp = curr
        curr = curr.next
    prev = rightp.next
    print(leftp.val, rightp.val)
    curr = leftprev
    while curr != rightp:
        nextp = curr.next
        curr.next = prev

        prev = curr
        curr = nextp
    return head

there were many logical mistakes in this code:

we treat the positions as values! wrong as hell
the curr.next scan loop will miss the final entry
leftprev is finding the value of the leftprevious, not the index – related to the misunderstanding of the question
reversal should start at leftp not leftprev
we never reconnect the reversed segment back to the list
we stop at curr!=rightp, so the endpoint rightp is never reversed / linked properly

more correctly, we should have done:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head

        dummy = ListNode(0, head)
        leftprev = dummy

        curr = head
        for _ in range(left-1):
            leftprev = curr
            curr = curr.next

        prev = None
        tail = curr
        for _ in range(right-left+1):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        leftprev.next = prev
        tail.next = curr
        return dummy.next

234. Palindrome Linked List | easy

this kind of thinking is really a tricky endeavour:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head.next == None:
            return True

        # find middle node
        N = 0
        counter = 0
        curr = head
        while curr:
            N += 1
            curr = curr.next
        curr = head
        stopAt = floor(N/2)
        while counter < stopAt:
            curr = curr.next
            counter += 1
        removal = curr.val
        print("removal", removal)
        print("N", N)
        if N%2: # is odd
            # remove middle node:
            curr = head
            dummy = ListNode(-1, head)
            prev = dummy
            while curr:
                if curr.val == removal:
                    if curr.next == removal:
                        curr = curr.next.next
                        continue
                    else:
                        prev.next = curr.next
                        curr = curr.next
                        continue
                else:
                    prev = curr
                    curr = curr.next
            head = dummy.next
        curr = head
        hashMap = collections.defaultdict(int)
        while curr:
            hashMap[curr.val] += 1
            curr = curr.next
        print(hashMap)
        return True if all(value == 2 for value in hashMap.values()) else False

obviously this is very wrong. it fails on [1,3,2,4,3,2,1]. as the hashmap solution does not encode the positions.

in some sense I am checking multiset symmetry, not mirror order. more correctly we should have:

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        arr = []
        curr = head
        while curr:
            arr.append(curr.val)
            curr = curr.next

        return arr == arr[::-1]

21. Merge Two Sorted Lists | easy

obviously, I can’t do anything right:

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        headA = list1
        headB = list2

        currA = headA
        currB = headB

        # start on the smaller list:
        start = None
        other = None
        if headB.val < headA.val:
            start = headB
            other = headA
        else:
            start = headA
            other = headB

        curr = start
        while curr:
            if curr.next.val < other.val:
                curr = curr.next
            else:
                curr.next = other
                other = curr.next
        return start

the correct logic improves on my code by:

handling empty lists
checking curr.next before dereferencing it
advancing curr correctly in the while loop

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1

        # start on the smaller list:
        if list2.val < list1.val:
            start, other = list2, list1
        else:
            start, other = list1, list2

        curr = start
        while curr and other:
            if curr.next is None or curr.next.val > other.val:
                other_next = other.next
                other.next = curr.next
                curr.next = other
                other = other_next
                curr = curr.next
            else:
                curr = curr.next
        return start

stacks `[4/4]`

155. Min Stack | easy

class MinStack:

    def __init__(self):
        self.data = []


    def push(self, val: int) -> None:
        self.data.append(val)

    def pop(self) -> None:
        self.data.pop()


    def top(self) -> int:
        return self.data[-1]


    def getMin(self) -> int:
        return min(self.data)

20. Valid Parenthesis | easy

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        hashMap = {
            ')': '(',
            '}': '{',
            ']': '['
        }
        for element in s:
            if stack and (element in hashMap and stack[-1] == hashMap[element]):
                stack.pop()
            else:
                stack.append(element)
        return not stack

150. Evaluate Reverse Polish Notation

I’ve been stuck with this for some time now:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = [] # the stack should never get too large
        for token in tokens:
            print("stack:", stack)
            if token not in {'+','-','*','/'}:
                stack.append(int(token))
            else: # we don't really need to check this, but it will guard
                op1 = stack.pop(-1)
                op2 = stack.pop(-1)
                if token == '+':
                    stack.append(op2 + op1)
                elif token == '*':
                    stack.append(op2 * op1)
                elif token == '/':
                    stack.append((int(op2 / op1)))
                elif token == '-':
                    stack.append(op2 - op1)
        return stack.pop()

and I think the offender is the stack.pop(-1) line which might have a larger time complexity than stack.pop()

nope, it didn’t matter. I was just printing to stdout like a dumbass.

bonus q: stack sorting

input = [34,3,31,98,92,23]

stack = []

while input:
    num = input.pop()

    while stack and (stack[-1] > num):

        input.append(stack[-1])
        stack.pop()
    stack.append(num)
print(stack)

time complexity: \(O(n^2)\) space: \(O(n)\)

queues

225. Implement Stack using Queues | easy

class MyStack:

    def __init__(self):
        self.stack = deque()


    def push(self, x: int) -> None:
        self.stack.append(x)


    def pop(self) -> int:
        return self.stack.pop()


    def top(self) -> int:
        return self.stack[-1]

    def empty(self) -> bool:
        return True if len(self.stack) == 0 else False

I think the requirements for the question were more strict, however a pass is a pass.

2073. Time Needed to Buy Tickets | easy

I should consult the “minimum time to visit all points” problem from the arrays section

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        i = k
        counter = 0
        while tickets[i] > 0:
            print(counter)
            print(i)
            if i == 0:
                tickets[i] -= 1
            i = (i-1) % 3
            counter+= 1
        return counter

I came up with this partial solution in about 10 minutes, but decided to check out the solutions to see what to expend thinking on next.

I know that manipulating a data-structure that you are editing over is a bad idea.

time = 0

while True:
    for i in range(len(tickets)):
        if tickets[k]==0:
            return time
        if tickets[i]==0:
            continue
        if tickets[i]>=1:
            tickets[i]-=1
            time+= 1

this is \(O(n\times m)\) n people, m tickets for position k.

result = 0
for i in range(len(tickets)):
    if i <= k:
        result += min(tickets[i], tickets[k])

    else:
        result += min(tickets[i], tickets[k]-1)
return result

reverse first k elements (not leetcode)

def reverse_first_k_elements(k, q):
    stack = []

    # put first k elements in stack
    for i in range(k):
        stack.append(q.popleft())

    # push the contents of the stack to the back of the queue
    # will be added in reverse due to stack LIFO
    while stack:
        q.append(stack.pop())

    # pop and push elements in queue
    # that should come after first k elements in queue
    for i in range(len(q)-k):
        q.append(q.popleft())

    return q

from collections import deque
reverse_first_k_elements(3, deque([1,2,3,4,5]))

binary trees

each node has max of 2 children.

not to be confused with BST.

BFS, and DFS.

when to use stack and queue for which traversal.

full tree - when each node has 0 or 2 children complete tree - when every level is full, except potentially the last level which is filled from left degenerate - where every parent has exactly one child – aka a linked list! perfect - full and complete balanced - for each node, the height of the child subtree does not differ by more than \(k\), where \(k\) is usually 1.

it has been a long hiatus since I last worked on these problems. this is not the place to really document my thoughts, so let’s begin:

637. Average of Levels in Binary Tree | easy

we use a breadth first search pattern here.

from collections import deque

class Solution:
    def averageOfLevels(self, root):
         queue = deque([root])
         result = []

         while queue:
             level = []
             for i in range(len(queue)):
                 node = queue.popleft()
                 level.append(node.val)
                 if node.left: queue.append(node.left)
                 if node.right: queue.append(node.right)

             result.append(sum(level)/len(level))
         return result

mysol = Solution()

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

mysol.averageOfLevels(
    TreeNode(3,
             TreeNode(9,None,None),
             TreeNode(20,
                      TreeNode(15,None,None),
                      TreeNode(7, left=None, right=None))))
#mysol.averageOfLevels(TreeNode(3, TreeNode(val= 9, left= None, right= None), right= TreeNode(val= 20, left= TreeNode(val= 15, left= None, right= None), TreeNode(val= 7, left= None, right= None))))
#mysol.averageOfLevels([3,9,20,None,None,15,7])

111. Minimum Depth of Binary Tree | easy

definitely a little more of a naïve implementation, but it does pass. I recycled the traversal code from above:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        queue = deque([root])
        result = 10000
        depth = 0

        while queue:
            depth += 1
            level = [] # add children here
            for i in range(len(queue)):
                leaf = 0
                node = queue.popleft()
                if node is None:
                    return 0
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                else:
                    leaf += 1
                if node.right:
                    queue.append(node.right)
                else:
                    leaf += 1
                if leaf == 2:
                    result = min(depth, result)
        return result

be careful not to accidentally use depth first search just because the question says the word depth

time complexity: \(O(n)\)

stoney sol

def minDepth(self, root):
    if not root:
        return 0

    queue = deque([(root, 1)])

    while queue:
        node, level = queue.popleft()

        if not node.left and not node.right:
            return level

        if node.left:
            queue.append((node.left, level+1))

        if node.right:
            queue.append((node.right, level+1))

    return 0

it’s okay. I think mine is also not so bad – less tuple unpacking

104. Maximum Depth of Binary Tree | easy

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # bfs with queue
        if not root: return 0
        queue = deque([root])
        result = 0
        depth = 0

        while queue:
            depth += 1
            level = [] # holds the siblings at each level. is reset
            for i in range(len(queue)):
                composite = 0
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    composite += 1
                    queue.append(node.left)
                if node.right:
                    composite += 1
                    queue.append(node.right)
                if not composite:
                    result = max(depth, result)
        return result

there were a couple of things to be careful of here. firstly the composite logic was inverted.

be careful about making logical errors – that is basically the training that you are here for!

nextly, it seemed like I forgot that 0 is false in Python. I should know that VERY well.

not bad overall – you still managed to solve the problem on your own accord.

time complexity: \(O(n)\)

stoney sol

this time, I do believe the iterative and recursive solutions given by the tutorial video really are very clean:

def maxDepth(self, root):
    if not root:
        return 0

    queue = deque([(root, 1)])

    while queue:
        node, level = queue.popleft()

        #if not node.left and not node.right:
        #    return level

        if node.left:
            queue.append((node.left, level+1))

        if node.right:
            queue.append((node.right, level+1))

    return level

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0

    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

max/min value binary tree | not leet

this is not as straight-forward as finding the max/min of a binary search tree

from collections import deque

def largest_node_binary_tree(root):
    queue = deque([root])

    max_node = 0

    while queue:

        curr_node = queue.popleft()

        if curr_node.left:
            queue.append(curr_node.left)

        if curr_node.right:
            queue.append(curr_node.right)

        if curr_node.val > max_node:
            max_node = curr_node.val

    return max_node

another bug I noticed myself creating, is returning out of the while loop at the wrong level of indentation.

102. Binary Tree Level Order Traversal | medium

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = deque([root])
        result = [] # array of arrays to return

        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

I was able to create a passing solution, but I’m not quite sure why we need the for loop.

it somewhat feels like wasted computation. perhaps an individual trace might be a good idea.

I also don’t understand why we use .

space: O(n) time: O(n)

100. Same Tree | easy

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        stack = [(p, q)]

        while stack:
            node1, node2 = stack.pop()

            if not node1 and not node2: # if both are None
                continue

            # if only one are None, or they are not equal
            elif None in [node1, node2] or node1.val != node2.val:
                return False

            stack.append((node1.left, node2.left)) # the order of these don't matter.
            stack.append((node1.right, node2.right)) # as long as you push both the children onto the stack.

        return True

space: O(n) time: O(n)

112. Path Sum | easy

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        stack = [(root,root.val)]

        while stack:
            node, val = stack.pop()

            if not node:
                continue

            if not node.left and not node.right and val == targetSum:
                return True

            if node.right:
                stack.append((node.right, val + node.right.val))
            if node.left:
                stack.append((node.left, val + node.left.val))


        return False

this one felt more okay. I was able to get through it by peeking at the answers. notably the pressure points were adding to the stack list of tuples.

additionally, a better way to structure the “check if leaf logic” is to leverage the type of the children with .

finally, I also needed to be careful with appending the correct summed values of the children to the stack, and therein, also appending a tuple.

Time: O(n) Space: O(n)

543. Diameter of Binary Tree | easy

i actually have no idea how to solve this one:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        stack = [(root, False)] # visited list
        max_height_dict = {}
        diameter = 0

        while stack:
            node, visited = stack.pop()

            if not visited:
                # let's visit:
                stack.append((node, True))
                # intend to visit children:
                if node.left:
                    stack.append((node.left, False))
                if node.right:
                    stack.append((node.right, False))
            else: # already visited
                if node.left is None:
                    left_height = 0
                else:
                    left_height = max_height_dict.pop(node.left)

                if node.right is None:
                    right_height = 0
                else:
                    right_height = max_height_dict.pop(node.right)

                diameter = max(diameter, left_height + right_height)
                max_height_dict[node] = max(left_height, right_height) + 1
        return diameter

recursive solution

def diameterOfBinaryTree(root):
    self.diameter = 0

    def depth(root):
        if not root:
            return 0

        left_depth = depth(root.left)
        right_depth = depth(root.right)

        self.diameter = max(self.diameter, left_depth + right_depth)
        return 1 + max(left_depth, right_depth)

    depth(root)
    return self.diameter

226. Invert Binary Tree | easy

def invertBinaryTree(root):
    stack = [root]

    while stack:
        curr = stack.pop()

        if curr:
            curr.left, curr.right = curr.right, curr.left
            stack.extend([curr.right, curr.left])
    return root

236. Lowest Common Ancestor of a Binary Tree | medium

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root == None or root == p or root == q: return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left != None and right != None: return root
    if left != None: return left
    return right

this solution uses a depth first search approach. space: O(h) = O(n), time: O(n)

binary search trees

700. Search in a Binary Search Tree | easy

def searchBST(root, val):
    while root:
        if root.val == val:
            return root
        elif root.val < val:
            root = root.right
        else:
            root = root.left
    return None

time complexity: O(h) where h is the height of the tree. In the worst case (skewed tree), this is O(n). In a balanced tree, this is O(log n). space complexity: O(1) - constant space as we only use a few variables regardless of input size.

apparently, there is another solution:

def searchBST(root, val):
    current_node = root
    while current_node:

        if current_node.val == val:
            return current_node

        elif current_node.val < val:
            current_node = current_node.right

        else:
            current_node = current_node.left

    return None

eh. I suppose at a memory level it is worth understanding that modifications to root inside the function just modify the reference, not the original itself.

701. Insert into a Binary Search Tree | medium

first find the position
then insert the node

def insertIntoBST(root, val):
    new_node = TreeNode(val)

    if not root:
        return new_node

    current = root
    while True:
        if val < current.val:
            if current.left:
                current = current.left
            else:
                current.left = new_node
                break

        else:
            if current.right:
                current = current.right
            else:
                current.right = new_node
                break
    return root

a little complicated – perhaps a recursive solution will work better.

realise that the difference between recursive and iterative is usually a data structure and / or a while loop.

it’s quite an intelligent solution really. i do wonder if rotating the tree ever becomes necessary.

108. Convert Sorted Array to Binary Search Tree | easy

def sortedArrayToBST(self, nums):
    if not nums:
        return None

    n = len(nums)
    mid = n // 2
    root = TreeNode(nums[mid])

    #queue to keep track of (parent, left, right) tuples
    q = deque()
    q.append((root, 0, mid - 1))
    q.append((root, mid + 1, n - 1))

    while q:
        parent, left, right = q.popleft()
        if left <= right:
            mid = (left + right) // 2
            child = TreeNode(nums[mid])
            if nums[mid] < parent.val:
                parent.left = child
            else:
                parent.right = child
            q.append((child, left, mid - 1))
            q.append((child, mid + 1, right))

    return root

profiling: 3ms (beats 50.35%) (time); 20.75MB (beats 5.34%) space.

Problem: given an array nums (sorted) convert it into a height-balanced BST

Solution: Time - O(N) – all solutions process all elements in the input array. Space for iterative is O(N).

Recursively find midpoint of array, turn into Node, and repeat for that Node’s left and right children:

[1,2,3,4,5,6,7] -> left: [1,2,3], root: [4], right: [5,6,7] [1,2,3] -> left: [1], root: [2], right: [3] [5,6,7] -> left: [5], root: [6], right: [7]

def sortedArrayToBST(self, nums):
    # Time: O(n)
    # Space: O(n) in the case of skewed binary tree
    def convert(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = convert(left, mid - 1)
        node.right = convert(mid + 1, right)
        return node
    return convert(0, len(nums) - 1)

Code Snippet 2: Indices - Recursive

profiling: 3ms (beats 50.35%) (time); 20.47MB (beats 29.17%) space.

Note

Using indexes instead of passing slices of the array saves time and space

def sortedArrayToBST(self, num):
    if not num:
        return None

    mid = len(num) // 2
    root = TreeNode(num[mid])
    root.left = self.sortedArrayToBST(num[:mid])
    root.right = self.sortedArrayToBST(num[mid+1:])
    return root

profiling: 3ms (beats 50.35%) (time); 20.26MB (beats 90.89%) space.

653. Two Sum IV - Input is a BST | easy

def findTarget(root, k):

    queue = deque([root])
    num_set = set()

    while queue:

        node = queue.popleft()

        if (k-node.val) in num_set:
            return True
        else:
            num_set.add(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return False

seemed straight forward enough. O(n) for time, and O(n) for space.

235. Lowest Common Ancestor of a Binary Search Tree | easy

def lowestCommonAncestor(root, p, q):
    small = min(p.val, q.val)
    large = max(p.val, q.val)

    while root:
        if root.val > large: # p, q belong to the left subtree
            root = root.left
        elif root.val < small: # p, q belong to the right subtree
            root = root.right
        else: # now, small <= root.val <= large -> this is the LCA between p and q
            return root

    return None

530. Minimum Absolute Difference in BST | easy

i spent about a minute thinking, and was not very correct about the code that I was drafting in my head.

since I plan to invest further time doing anki on these cards, I am being somewhat more forgiving in terms of following the solutions that exist for these problems. lazy, I know.

def getMinimumDifference(root):
    min_diff = float('inf')
    prev_val = float('-inf')

    stack = []
    while root or stack:
        if root:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            min_diff = min(min_diff, root.val - prev_val)
            prev_val = root.val
            root = root.right

    return min_diff

1382. Balance a Binary Search Tree | medium

we can use two functions that we have previously written to solve this:

def inorder_traversal(root):
    nodes = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        nodes.append(current.val)
        current = current.right

    return nodes

along with:

def sortedArrayToBST(self, nums):
    if not nums:
        return None

    n = len(nums)
    mid = n // 2
    root = TreeNode(nums[mid])

    #queue to keep track of (parent, left, right) tuples
    q = deque()
    q.append((root, 0, mid - 1))
    q.append((root, mid + 1, n - 1))

    while q:
        parent, left, right = q.popleft()
        if left <= right:
            mid = (left + right) // 2
            child = TreeNode(nums[mid])
            if nums[mid] < parent.val:
                parent.left = child
            else:
                parent.right = child
            q.append((child, left, mid - 1))
            q.append((child, mid + 1, right))

    return root

the way this works, is that we first iterate over the (unbalanced) BST to create an ascending list array.

then we apply the sortedArrayToBST function on the list, which works by iteratively segmenting the array to develop a BST.

naturally this is an \(\mathcal{O}(n)\) algorithm still since both sub-algorithms are called once and are each themselves \(\mathcal{O}(n)\).

in its entirety:

class Solution:

    def inorder_traversal(self, root):
        nodes = []
        stack = []
        current = root

        while current or stack:
            while current:
                stack.append(current)
                current = current.left

            current = stack.pop()
            nodes.append(current.val)
            current = current.right

        return nodes

    def sortedArrayToBST(self, nums):
        if not nums:
            return None

        n = len(nums)
        mid = n // 2
        root = TreeNode(nums[mid])

        #queue to keep track of (parent, left, right) tuples
        q = deque()
        q.append((root, 0, mid - 1))
        q.append((root, mid + 1, n - 1))

        while q:
            parent, left, right = q.popleft()
            if left <= right:
                mid = (left + right) // 2
                child = TreeNode(nums[mid])
                if nums[mid] < parent.val:
                    parent.left = child
                else:
                    parent.right = child
                q.append((child, left, mid - 1))
                q.append((child, mid + 1, right))

        return root

    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        return self.sortedArrayToBST(self.inorder_traversal(root))

450. Delete Node in a BST | medium

# 3 cases: delete leaf; delete with 1 child; delete with 2 children
def delete_iterative(self, data):
    if not root:
        return None

    parent = None
    current = root

    # find the node to delete and its parent
    while current and current.val != key:
        parent = current
        if key < current.val:
            current = current.left
        else:
            current = current.right

    # node to be deleted not found
    if not current:
        return root

    # case 1: node with no children
    if not current.left and not current.right:
        if not parent:
            return None # deleting the root node
        if parent.left == current:
            parent.left = None
        else:
            parent.right = None

    # case 2: node with one child
    elif not current.left or not current.right:
        child = current.left if current.left else current.right
        if not parent:
            return child # deleting the root node
        if parent.left == current:
            parent.left = child
        else:
            parent.right = child

    # case 3: node with two children
    else:
        # find the inorder successor (smallest in the right subtree)
        successor_parent = current
        successor = current.right
        while successor.left:
            successor_parent = successor
            successor = successor.left

        # copy the inorder successor's content to the current node
        current.val = successor.val

        # delete the inorder successor
        if successor_parent.left == successor:
            successor_parent.left = successor.right
        else:
            successor_parent.right = successor.right
    return root

recursive solution/s:

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        return self._delete_recursive(root, key)

    def _delete_recursive(self, current, key):
        if current is None:
            return None

        if key < current.val:
            current.left = self._delete_recursive(current.left, key)

        elif key > current.val:
            current.right = self._delete_recursive(current.right, key)

        else:  # node found
            # case 1: no children
            if not current.left and not current.right:
                return None

            # case 2: one child
            if not current.left:
                return current.right
            if not current.right:
                return current.left

            # case 3: two children
            successor = self._find_min_node(current.right)
            current.val = successor.val
            current.right = self._delete_recursive(current.right, successor.val)

        return current

    def _find_min_node(self, node):
        while node.left:
            node = node.left
        return node

canonical interview version:

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None

        if key < root.val:
            root.left = self.deleteNode(root.left, key)

        elif key > root.val:
            root.right = self.deleteNode(root.right, key)

        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left

            successor = root.right
            while successor.left:
                successor = successor.left

            root.val = successor.val
            root.right = self.deleteNode(root.right, successor.val)

        return root

230. Kth Smallest Element in a BST | medium

basically the same as the min absolute difference question:

def kthSmallest(root, k):

    stack = []

    while root or stack:

        if root:
            stack.append(root)
            root = root.left

        else:
            root = stack.pop()
            k -= 1

            if k == 0:
                return root

        root = root.right

heaps

operation	time complexity
insert	\(\mathcal{O}(\log{n})\)
extract min/max	\(\mathcal{O}(\log{n})\)
peek min/max	\(\mathcal{O}(1)\)
delete	\(\mathcal{O}(\log{n})\)
heapify	\(\mathcal{O}(n)\)

215. Kth Largest Element in an Array | medium

we could solve this using an array. sorting it and then returning kth, but we do not wish to sort

return heapq.nlargest(k,nums)[-1]

\begin{aligned} \text{Time Complexity:} &\quad O(k) + (n-k)\,O(\log k) = O(n \log k) \\ \text{Space Complexity:} &\quad O(k) \end{aligned}

another solution with

\begin{aligned} \text{Time Complexity:} &\quad O(n\log n) + O((n-k)\log n)\, + O(\log n) = O(n \log n) \\ \text{Space Complexity:} &\quad O(n) \end{aligned}

heap = []
for i in nums:
    heapq.heappush(heap, i)

for i in range(len(nums)-k):
    heapq.heappop(heap)

return heapq.heappop(heap)

we need to be careful here with the laziness of it all — because consider you wrote the first solution, it is likely the interviewer will encourage you to write:

# create a min-heap with the first k elements
heap = nums[:k]

heapq.heapify(heap) # time complexity: O(k)

# iterate through the remaining elements
for num in nums[k:]:
    if num > heap[0]:
        heapq.heapreplace(heap,num) # time complexity: O((n-k)*2logk)
        # 2logk because of heappop followed by heappush
# the root of the heap is the k largest element

return heap[0]

973. K Closest Points to Origin | medium

points is a list of lists. integral k.

return a list of closest points.

given: the solutions are unique

heap = []

# built in heap module creates a min heap by default. to create a max-heap, negate the values
for (x, y) in points:
    dist = -(x*x + y*y)
    if len(heap) == k:
        heapq.heappushpop(heap, (dist, x, y))
    else:
        heapq.heappush(heap, (dist, x, y))

return [(x,y) for (dist, x, y) in heap]

note: be careful to flip the sign at the end if you manually create this max-heap as above.

pushes an item onto the heap, then pops and returns the smallest item from the heap. the combined action runs more efficiently than followed by a separate call to !

do not confuse with , which first pops the smallest element and then pushes the new element.

Time Complexity: O(n * log k). log k = inserting into heap. worst-case we insert for all elements Space: O(k) for the heap

347. Top K Frequent Elements | medium

# Step 1: count the frequency of each element in the array
count = Counter(nums)

# step 2: use a min heap to find the k most frequent elements
heap = []
for num, freq in count.items():
    if len(heap) < k:
        heapq.heappush(heap, (freq, num)) # O(logk), k times
    elif freq > heap[0][0]:
        heapq.heapreplace(heap, (freq, num)) # O(logk), up to (n-k) times

# step 3: extract the elements from the heap
top_k = [num for freq, num in heap] # O(k)

return top_k

Time Complexity: O(N log k) Space: O(N)

621. Task Scheduler | medium

consider:

AAA BB CC n=1
random order: B->C->B->A->idle->A->C->A
most frequent order: A->B->A->C->A->B->C

Max heap:
-3, -2, -2, -
Interval = 0
wait_queue = []

Max heap:
-2, -2, -, -
        -3+1=-2
interval = 1
wait_queue = [(-2,2)]

...?
Max heap:
-2, -, -
        -3+1=-2
interval = 2
wait_queue = [(-2,2)]

# max-heap, where root node will
# step 1: count the frequency of each task
task_counts = Counter(tasks) # O(N)

# step 2: create a max-heap using the task counts
max_heap = []
for count in task_counts.values():
    max_heap.append(-count)

heapq.heapify(max_heap) # O(N) to build the heap

# Step 3: initialise variables
time = 0
wait_queue = deque() # (task, time_available)

# step 4: process the tasks
while max_heap or wait_queue: # O(N)
    time += 1

    if max_heap:
        current_task = heapq.heappop(max_heap) # O(log N)
        current_task += 1 # decrease the count (since it's negative)

        # if there are still more of this task to execute, add to the wait_queue
        if current_task != 0:
            wait_queue.append((current_task, time + n)) # O(1)

    # check if any tasks in the wait queue can be pushed back to the heap
    if wait_queue and wait_queue[0][1] == time:
        heapq.heappush(max_heap, wait_queue.popleft()[0]) # O(log N)

return time

Time: O(N log N), because each task can be pushed and popped from the heap (multiple times)
Space: O(N)

graphs

creating a graph:

class Graph():
    def __init__(self):
        self.graph = {}

    def addEdge(self, from_vertex, to_vertex):
        # add edge
        if from_vertex in self.graph:
            self.graph[from_vertex].append(to_vertex)

        # add vertex
        else:
            self.graph[from_vertex] = [to_vertex]

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)

bfs traversal:

def bfs(self, start_vertex):
    # check if the start_vertex exists in the graph
    if start_vertex not in self.graph:
        return [] # if not, return an empty list

    queue = [start_vertex] # initialise a queue with the start_vartex
    traversal = [] # initialise an empty list to store the bfs traversal result

    while queue: # continue until the queue is empty
        vertex = queue.pop(0) # remove and retrive the first vertex from the queue (FIFO)
        if vertex not in traversal: # check if the vertex has not been visited
            traversal.append(vertex) # add the vertex to the traversal result
            if vertex in self.graph: # check if the vertex exists in the graph
                queue.extend(self.graph[vertex]) # add all adjacent vertices of the current vertex to the queue

    return traversal # return the BFS traversal result

dfs traversal

def dfs(self, start_vertex):
    # check if the start_vertex exists in the graph
    if start_vertex not in self.graph:
        return [] # if not, return an empty list

    stack = [start_vertex] # initialise a stack with the start_vertex
    traversal = [] # initialise an empty list to store the DFS traversal result

    while stack: # continue until the stack is empty
        vertex = stack.pop() # remove and retrieve the last vertex from the stack (LIFO)
        if vertex not in traversal: # check if the vertex has not been visited
            traversal.append(vertex) # add the vertex to the traversal result
            if vertex in self.graph: # check if the vertex exists in the graph
                stack.extend(reversed(self.graph[vertex])) # add all adjacent vertices of the current vertex to the stack

    return traversal

133. Clone Graph | medium

class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

from collections import deque


class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        queue = deque([node])
        clones = {node.val: Node(node.val)}

        while queue:
            curr = queue.popleft()
            curr_clone = clones[curr.val]

            for neighbor in curr.neighbors:
                if neighbor.val not in clones:
                    clones[neighbor.val] = Node(neighbor.val)
                    queue.append(neighbor)
                curr_clone.neighbors.append(clones[neighbor.val])
        return clones[node.val]

Time: O(V+E)
Space: O(V)

Core Graph Operations | concept

def findLargestNode(self, start_vertex):
    if start_vertex not in self.graph:
        return None

    queue = [start_vertex]
    traversal = []
    largest_node = start_vertex

    while queue:
        vertex = queue.pop(0)

        if vertex not in traversal:
            traversal.append(vertex)

            if vertex > largest_node:
                largest_node = vertex

            if vertex in self.graph:
                queue.extend(self.graph[vertex])

    return largest_node

iterative BFS – traverses entire graph, keeping track of the largest node and making comparisons at each node
starting at a node in directed graphs with no edges to traverse returns None - which is expected. can easily change this with isolated nodes check in first if block, also not a problem for non-directed graphs.

def find_cycle(self, start_vertex):
    if start_vertex not in self.garph:
        return False # no cycle if the start vertex is not in the graph

    stack = [(start_vertex, -1)] # stack of (vertex, parent)
    visited = set() # set to store visited vertices

    while stack:
        vertex, parent = stack.pop()
        if vertex in visited:
            return True # a cycle is found if the vertex is already visited

        visited.add(vertex)

        # get neighbors or an empty list if the vertex is not explicitly listed
        for neighbor in self.graph.get(vertex, []):
            if neighbor != parent:
                stack.append((neighbor, vertex))

    return False

iterative DFS - stack to traverse graph and visited set to identify a cycle
parent check necessary for undirected graphs otherwise can omit

def count_edges(self):
    edge_count = 0 # initialise the edge count to zero
    for vertex in self.graph: # iterative over each vertex in the graph
        edge_count += len(self.graph[vertex]) # add the number of edges from this vertex
    return edge_count

count the total number of edges in the graph by iterating through each vertex and summing up the lengths of their adjacency lists

787. Cheapest Flights Within K Stops | medium

Dijkstra is not a bad idea here, but Bellman Ford will use the \(k\) condition better:

def findCheapestPrice(n, flights, src, dst, k):
    # initialise prices array with infinity for all nodes
    prices = [float('inf')] * n
    # set the price to reach the source node to 0
    prices[src] = 0

    # perform up to k+1 iterations (0 to k stops)
    for i in range(k+1):
        # make a copy of the current prices to update in this iteration
        tmpPrices = prices.copy()

        # iterate through all flights
        for from_node, to_node, cost in flights:
            # if the source node has not been reached, skip this flight
            if prices[from_node] == float('inf'):
                continue
            # if a cheaper price to destination is found, update temporary prices
            if prices[from_node] + cost < tmpPrices[to_node]:
                tmpPrices[to_node] = prices[from_node] + cost

        # update prices with the temporary prices after processing all flights
        prices = tmpPrices

    # if the destination price is sitll infinity, it means it is unreachabl
    if prices[dst] == float('inf'):
        return -1
    else:
        return prices[dst]

Time: O(K*E) – check every edge in k loops.
Space: O(N) – all the n cities stored in prices tables

207. Course Schedule | medium

# make adjacency list with courses as keys and pre-requisites as values
adj = {course: [] for course in range(numCourses)}
for course, pre in prerequisites:
    adj[course].append(pre)

# run iterative DFS and check for any cycles
for course in range(numCourses):
    stack = [(course, set())]
    while stack:
        cur_course, visited = stack.pop()
        if cur_course in visited:
            return False # cycle detected
        visited.add(cur_course)
        for pre in adj[cur_course]:
            stack.append((pre, visited.copy()))
    adj[course] = [] # remove course
return True

Time: O(V+E)
Space: O(V+E)

Leetcode Stoney Tute

setting the stage#

process for problem solving#

problems#

arrays#

217. duplicate values | easy#

268. missing number | easy#

448. find all numbers disappeared in an array | easy#

1. two sum | easy#

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

1266. Minimum Time Visiting All Points | easy#

54. Spiral Matrix | medium#

200. Number of Islands | medium#

arrays - two pointers#

121. Best time to buy and sell stock | easy#

977. Squares of a sorted array | easy#

15. 3Sum | medium#

167. 2Sum Part II | medium#

845. Longest Mountain in Array | medium#

arrays - sliding window#

219. Contains Duplicate II | easy#

1200. Minimum absolute difference | easy#

209. Minimum Size Subarray Sum | medium#

bit manipulation#

136. Single Number | easy#

dynamic programming#

322. Coin Change | medium#

70. Climbing Stairs | easy#

53. Maximum Subarray | medium#

338. Counting Bits | easy#

303. Range Sum Query - Immutable | easy#

backtracking#

784. Letter Case Permutation | medium#

78. Subsets | medium#

77. Combinations | medium#

46. Permutations | medium#

37. Sudoku Solver | Hard#

linked lists#

876. Middle of a linked list | easy#

141. Linked List Cycle | easy#

206. Reverse Linked List | easy#

203. Remove Linked List Elements | easy#

92. Remove Linked List II | medium#

234. Palindrome Linked List | easy#

21. Merge Two Sorted Lists | easy#

stacks [4/4]#

155. Min Stack | easy#

20. Valid Parenthesis | easy#

150. Evaluate Reverse Polish Notation#

bonus q: stack sorting#

queues#

225. Implement Stack using Queues | easy#

2073. Time Needed to Buy Tickets | easy#

reverse first k elements (not leetcode)#

binary trees#

637. Average of Levels in Binary Tree | easy#

111. Minimum Depth of Binary Tree | easy#

104. Maximum Depth of Binary Tree | easy#

max/min value binary tree | not leet#

102. Binary Tree Level Order Traversal | medium#

100. Same Tree | easy#

112. Path Sum | easy#

543. Diameter of Binary Tree | easy#

226. Invert Binary Tree | easy#

236. Lowest Common Ancestor of a Binary Tree | medium#

binary search trees#

700. Search in a Binary Search Tree | easy#

701. Insert into a Binary Search Tree | medium#

108. Convert Sorted Array to Binary Search Tree | easy#

653. Two Sum IV - Input is a BST | easy#

235. Lowest Common Ancestor of a Binary Search Tree | easy#

530. Minimum Absolute Difference in BST | easy#

1382. Balance a Binary Search Tree | medium#

450. Delete Node in a BST | medium#

230. Kth Smallest Element in a BST | medium#

heaps#

215. Kth Largest Element in an Array | medium#

973. K Closest Points to Origin | medium#

347. Top K Frequent Elements | medium#

621. Task Scheduler | medium#