python - leetcode

10m read · 2024 words

python - leetcode

This is the easiest gatekeeping round in existence. And it is a blessing for people like me.

Understand that leetcode is all about pattern recognition.

After reading a problem, I should immediately know what pattern it requires.

Easy problems don't really have any pattern required. Medium problems require using 1 pattern. Hard problems require using 2 or more patterns.

Solving medium problems is enough to crack most big tech interviews.

How to get good at this

Learning new patterns

Solve lists only (interview 150, blind 75 etc).

Pick the next problem from the list. Try solving it. If you cannot solve the problem in 45 mins, give up and look at the solution. If the solution has a new patterns that I didn't know, then the entire day is dedicated to that pattern only. Find more problems that have this same pattern and solve them until I know the pattern.

  1. Pick next problem from the list
  2. Try solving the problem. If cannot solve it in 45mins, give up and look at the solution.
  3. If the problem has a new pattern, then the entire day is dedicated to that pattern only.
  4. GOTO (1)

Know and set my limits:

  1. I can learn only one new pattern in a day

Remembering studied patterns

I can revise ALL previously known patterns in under an hour.

For remembering, make a note of all patterns I know - pattern name, what problems look like, sample code. This note will be revised daily. Revision typically takes 20 minutes once I am used to it.

Patterns list

Two Pointers

Core idea - maintain 2 indices that move through the data, usually from opposite ends or in the same direction.

Opposite direction:

def two_sum_sorted(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return [left, right]

        elif total < target:
            left += 1

        else:
            right -= 1

    return [-1, -1]

Same direction (slow/fast pointer):

def remove_duplicates(nums):
    if not nums:
        return 0

    slow = 0

    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

Identify

  1. Input array is sorted
  2. Look for a pair of elements satisfying some relationships
  3. Need to compare elements from both ends
  4. Need to modify/filter array in-place (typically slow+fast pointers)

Problems - 2 pointers

Problems - Fast & Slow Pointers

DFS

Uses stack or recursion

# ITERATIVE
def dfs(node):
    if node is None:
        return

    # process node

    for neighbor in node.neighbors:
        dfs(neighbor)


# RECURSIVE
def dfs(graph, start):
    stack = [start]
    visited = set()

    while stack:
        node = stack.pop()

        if node in visited:
            continue

        visited.add(node)

        for neighbor in graph[node]:
            stack.append(neighbor)

DFS - grid

def dfs(row, col):
    if out_of_bounds(row, col):
        return

    if visited[row][col]:
        return

    visited[row][col] = True

    dfs(row + 1, col)
    dfs(row - 1, col)
    dfs(row, col + 1)
    dfs(row, col - 1)

Identification

  1. Explore all paths (dfs + backtracking)
    1. Generate combinations, permutations, subsets
    2. Word search
  2. Trees where need to explore subtrees
    1. Eg - Find max depth of a binary tree
def maxDepth(root):
    if not root:
        return 0

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

Connected components

def dfs(grid, r, c):
    if (
        r < 0 or r >= len(grid) or
        c < 0 or c >= len(grid[0]) or
        grid[r][c] != "1"
    ):
        return

    grid[r][c] = "0"

    dfs(grid, r + 1, c)
    dfs(grid, r - 1, c)
    dfs(grid, r, c + 1)
    dfs(grid, r, c - 1)

Problems

BFS

Uses a queue

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = {start}

    while queue:
        node = queue.popleft()

        # process node

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Identification

from collections import deque

def level_order(root):
    if not root:
        return []

    queue = deque([root])
    result = []

    while queue:
        level = []

        for _ 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

Prefix Sum

Prefix sum + hashmap is a common combination

BASIC

def prefix_sum(nums):
    prefix = [0] * (len(nums) + 1)

    for i in range(len(nums)):
        prefix[i + 1] = prefix[i] + nums[i]

    return prefix


nums = [2, 4, 1, 5, 3]
prefix = prefix_sum(nums)

# Sum of nums[1:4] → 4 + 1 + 5
left = 1
right = 3

result = prefix[right + 1] - prefix[left]

print(result)  # 10

WITH HASHMAP

`count += seen[prefix - k]`

from collections import defaultdict


def subarray_sum(nums, k):
    prefix = 0
    count = 0

    seen = defaultdict(int)
    seen[0] = 1

    for num in nums:
        prefix += num

        # Have we seen a prefix that makes the
        # current subarray sum equal to k?
        count += seen[prefix - k]

        seen[prefix] += 1

    return count


nums = [1, 2, 3, -2, 2]
k = 3

print(subarray_sum(nums, k))

Identification

Look for problems involving repeated sums over contiguous ranges.

Problem clue Think
Range sum queries Prefix Sum
Sum of l..r|Prefix Sum
Repeated contiguous sums Prefix Sum
Subarray sum = K Prefix Sum + HashMap
Count subarrays with condition Prefix Sum + HashMap
Equal 0s and 1s Prefix Sum
Balance between two values Prefix Sum
2D rectangular sum 2D Prefix Sum
Positive numbers + target window Often Sliding Window

Most important - Subarray Sum = K

Eg - Number of subarrays whose sum equals 3

from collections import defaultdict

def subarray_sum(nums, k):
    count = 0
    prefix = 0

    frequencies = defaultdict(int)
    frequencies[0] = 1

    for num in nums:
        prefix += num

        count += frequencies[prefix - k]

        frequencies[prefix] += 1

    return count

Words like:

Problems

Heap / Priority Queue

Problems

Dynamic Programming

Problems

Problems

Misc

DFS vs BFS

Signal DFS BFS
Explore deeply ✅
Explore level-by-level ✅
Shortest path, unweighted ✅
Connected components ✅ ✅
Number of islands ✅ ✅
Tree traversal ✅ ✅
Generate permutations ✅
Generate subsets ✅
Backtracking ✅
Minimum moves ✅
Nearest/closest node ✅
Level order ✅
Path existence ✅ ✅

These are symptoms of BFS/DFS:

Tree
Graph
Grid
Island
Connected
Path
Reachable
Neighbors

Then choose an algo:

All possibilities?       → DFS / Backtracking
Connected component?     → DFS or BFS
Shortest path?           → BFS
Minimum moves?           → BFS
Level by level?          → BFS
Deep subtree computation → DFS
Colophon 2024 words · 10m read
Written as a markdown note in Obsidian. Built into this page by a Python script on 2026-10-09.

Pages