Created Aug 27, 2026· Updated Sep 29, 2026

Data Structures and Algorithms

This page contains notes on some data structures and algorithms, with some example problems.

See this page for more LeetCode problems.

Binary Search

I came across a really elegant binary search template in this awesome post:

def binary_search(array) -> int:
    def check(index) -> bool:
        pass

    left, right = 0, len(array) - 1
    while left < right:
        mid = left + (right - left) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left

In essence, this template treats a binary search problem as mapping the array to [False, False, ..., False, True, True, ..., True] with a function check, then finding the first element that maps to True (or, in some cases, the last element that maps to False).

left = mid + 1 guarantees the search range keeps shrinking every iteration, even in the right - left == 1 case, where mid equals left, which prevents an infinite loop. When check(mid) is True, right is pulled down to mid; when it’s False, left is pushed up to mid + 1. So when the loop exits (left == right), left has just moved past the last False element and now sits on the first True element.

There’s a small caveat: in some cases, there’s no guarantee that a valid answer exists in the array, so the left value after the loop may need extra validation.

To sum up, there are only three things (highlighted) to consider when using this template:

The initial left and right values: only elements in [left, right) get checked
The return value: left or left - 1, and whether the result needs a validity check
The check function: often the hardest part

Examples

LeetCode: 704. Binary Search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def check(index):
            return nums[index] >= target

        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left if nums[left] == target else -1

Notice that we have to check here in case target isn’t present in nums.

LeetCode: 162. Find Peak Element

This one is a bit tricky.

Let’s consider the case where there’s only one peak. It’s easy to solve by binary search:

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        def check(index):
            if index == len(nums) - 1:
                return True
            return nums[index] > nums[index + 1]

        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

Surprisingly, the exact same algorithm also works for our problem where there can be multiple peaks.

We can assume every array has a peak: if there were no peaks, the second element has to be larger than the first, otherwise the first is the peak; the third has to be larger than the second for the same reason; thus, all elements have to be increasing (because of the constraint nums[i] != nums[i + 1] for all valid i); however, the last element will then be a peak. Thus, there always exists a peak in a given array. (Also, the problem description doesn’t say anything about returning -1.)

The reason this works even with multiple peaks is that check might map the array to something like [False, False, True, True, False, True, False, True], and what matters is that each result tells us which half must contain a peak: if check(mid) is True, then nums[mid] > nums[mid + 1], so a peak exists somewhere in [left, mid]; otherwise, nums[mid] < nums[mid + 1], so a peak exists in [mid + 1, right]. Thus, we can always discard one half while preserving the guarantee that a peak remains.

LeetCode: 153. Find Minimum in Rotated Sorted Array

class Solution:
    def findMin(self, nums: List[int]) -> int:
        def check(index):
            return nums[index] <= nums[-1]

        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return nums[left]

After a rotation, the target (the minimum) splits the array into two halves: the first half strictly larger than the last element, and the second half, starting with the target, smaller than or equal to the last element (equality holds when the target is the last element).

LeetCode: 33. Search in Rotated Sorted Array

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def check(index):
            if target > nums[-1]:
                return nums[index] >= target or nums[index] <= nums[-1]
            else:
                return nums[index] >= target and nums[index] <= nums[-1]

        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left if nums[left] == target else -1

The check function for this problem basically uses the last element as a reference point to determine which sorted half target belongs to.

Sliding Window

The sliding window technique is where we maintain a window [left, right] that expands and shrinks as we scan the array. It fits problems where we need to track everything between the two pointers (a contiguous block of data between left and right), whereas in other two-pointer problems we usually only care about the elements at the two pointers.

Note that the sliding window only works when a window’s validity is monotonic. Expanding the window changes the window state in one predictable direction, and shrinking it does the opposite.

A general template (variable-size window):

def variable_sliding_window(arr):
    window_state = init_window_state()
    ans = init_answer()

    left = 0
    # expand the window
    for right in range(len(arr)):
        window_state.add(arr[right])

        # shrink the window if the window is not valid
        while not window_state.is_valid():
            window_state.remove(arr[left])
            left += 1

        # update the answer once the window is valid
        ans.update(window_state)

    return ans

Some notes on the template:

window_state holds whatever the problem asks us to track for the current window (e.g. a sum, a counter, a set, …)
the window shrink condition depends on the problem:
- for a maximum window we shrink while the window is invalid
- for a minimum window we shrink while it’s still valid (in which case the update statement needs to be inside the while loop before shrinking, so every valid window is recorded)
sometimes it’s easier to check and shrink first, then add the new element arr[right] to window state

Fixed-size window is essentially a special case of variable-size window, where the window shrinks everytime as it expands. The template (k is the fixed window size):

def fix_sliding_window(arr, k):
    window_state = init_window_state(arr[:k])
    ans = init_answer(arr[:k])

    left = 0
    for right in range(k, len(arr)):
        window_state.add(arr[right])
        window_state.remove(arr[left])
        left += 1

        ans.update(window_state)

    return ans

Examples

LeetCode: 3. Longest Substring Without Repeating Characters

We need a variable-size window. Expand until a duplicate appears, then shrink from the left until the window is valid again. In this problem, we can track the window state with a hash set.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        ans = 0

        left = 0
        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])

            ans = max(ans, right - left + 1)

        return ans

seen tracks the characters currently in the window. When a new character is already inside, we shrink from the left until the duplicate is gone. Then, we include the new character into the window, at which point the window [left, right] is valid. So, we update ans with the current window length.

As a side note, expanding the window in this problem can only add new repeating characters, and shrinking can only potentially get rid of repeating characters, which satisfy the monotonicity requirement.

LeetCode: 76. Minimum Window Substring

We need a variable-size window. The window is valid if it contains every character in t. In this problem, we need to shrink when the condition is met, because we are finding the minimum window. We can use a counter to track what characters and how many of them we need to meet the condition.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        missing = Counter(t)  # chars still needed, and how many
        required = len(missing)  # number of distinct chars in t
        covered = 0  # number of distinct chars fully covered so far
        best_l, best_r = 0, len(s)  # initialized with sentinel window

        l = 0
        for r in range(len(s)):
            if s[r] in missing:
                missing[s[r]] -= 1
                if missing[s[r]] == 0:
                    covered += 1
            while covered == required:
                if r - l + 1 < best_r - best_l + 1:
                    best_l, best_r = l, r
                if s[l] in missing:
                    missing[s[l]] += 1
                    if missing[s[l]] > 0:
                        covered -= 1
                l += 1

        return "" if best_r == len(s) else s[best_l : best_r + 1]

missing[s[r]]: how many more copies of s[r] the window still needs
required is the number of distinct characters in t; covered is how many of those characters the current window fully supplies, i.e. has at least the required count of
covered goes up when expanding drops missing[s[r]] to 0, and down when shrinking pushes missing[s[l]] above 0
a window is valid $\iff$ covered == required

LeetCode: 643. Maximum Average Subarray I

We need a fixed-size window. The window state is simply the sum of the k elements.

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        windowSum = sum(nums[:k])
        maxSum = windowSum

        left = 0
        for right in range(k, len(nums)):
            windowSum += nums[right]
            windowSum -= nums[left]
            left += 1

            maxSum = max(maxSum, windowSum)

        return maxSum / k

Dynamic Programming

Key attributes:

optimal substructure: the solution to a given optimization problem can be obtained by combining the optimal solutions to its sub-problems
overlapping sub-problems: the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems

Approaches:

top-down: recursion + caching
- usually more intuitive
- only computes sub-problems that are actually needed
bottom-up: iteration + DP table
- no call stack overhead
- potential space optimization

Examples

LeetCode: 70. Climbing Stairs

A classic DP problem. You can climb to stair n by either taking 1 step from stair n-1 or taking 2 steps from stair n-2. This means the number of ways to climb to stair n equals the number of ways to climb to stair n-1 plus the number of ways to climb to stair n-2. Notice how we are breaking the problem into two sub-problems, and how the solution to the problem can be obtained by combining the solutions to the sub-problems. Also, notice that the sub-problems are overlapping: to get the solution for n-1, we are going to need the solution for n-2, which we already computed for n.

The most intuitive way to implement the algorithm above is through recursion.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

The implementation above is correct, but not efficient enough. This is because we are doing a ton of redundant computation: we are not reusing the computation results for the overlapping sub-problems. In fact, this implementation has $O(2^n)$ time complexity. The trivial optimization now is to use memoization (storing the results of expensive function calls in a cache to return them instantly when the same inputs occur again).

class Solution:
    def climbStairs(self, n: int) -> int:
        from functools import cache

        @cache
        def helper(n):
            if n == 1:
                return 1
            if n == 2:
                return 2
            return helper(n - 1) + helper(n - 2)

        return helper(n)

In older versions of Python, import lru_cache and use @lru_cache() instead. The following implementation essentially does the same thing, without the cache decorator.

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {1: 1, 2: 2}

        def helper(n):
            if n not in memo:
                memo[n] = helper(n - 1) + helper(n - 2)
            return memo[n]

        return helper(n)

The memoization optimization collapses the recursion tree from basically a full binary tree into a degenerate tree (a skewed tree), giving $O(n)$ time complexity.

The above approach is top-down. Now, we show a bottom-up approach with the same time complexity, where we build the answer from the base cases all the way up to n, iteratively.

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

Notice that to compute dp[i], we only need dp[i-1] and dp[i-2], which gives us the following space optimization.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

By replacing the dp array with two variables a and b that get updated every time we compute the next step, we have an $O(1)$ space complexity implementation.

LeetCode: 198. House Robber

To find the maximum money we can get from the first i houses, we only need two values: the best we can do robbing house i, and the best we can do not robbing it, then take the larger of the two.

If we rob house i, we can’t rob house i-1, so the best is nums[i] plus the best for the first i-1 houses without robbing house i-1. If we don’t rob house i, there’s no such restriction, so the best is the larger of the two options for the first i-1 houses (robbing or not robbing house i-1).

Either way, the two values for the first i houses depend only on the two values for the first i-1 houses, so we can compute them bottom-up while keeping just two numbers in memory. The space-optimized implementation below tracks them as rob and norob.

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob, norob = 0, 0
        for num in nums:
            rob, norob = num + norob, max(norob, rob)
        return max(rob, norob)

Linked List

Definition for a singly-linked list on LeetCode:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Reversing

A linked list can be reversed in place by reversing each next pointer while iterating over it.

LeetCode: 206. Reverse Linked List

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur is not None:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

In each iteration, we point the current node’s next pointer to the previous node, and then update pre and cur to get ready for the next iteration. Note that we have to store the current node’s next node in a temporary variable before we update the pointer, because after we point the current node’s next pointer to the previous node, we lose track of the next node. Initially we set the current node to be the head, so its previous node is set to None — the tail of the reversed list is the original head, whose next is None. After the loop, cur is None, and pre is the last node we updated, so pre is the head of the reversed list.

This implementation gives the optimal time and space complexities of $O(n)$ and $O(1)$ .

In my opinion, a more intuitive and elegant implementation is through recursion.

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

To reverse a linked list, we remove its head, reverse the rest, and append the head to the reversed rest as its new tail. To append the head as the tail, notice that the head’s next points to the tail of the reversed list, so we just set the tail’s next to head and make head point to None to make it the new tail.

This implementation runs in $O(n)$ time, but has $O(n)$ space complexity because of the recursive call stack.

We can actually write the recursion in a different way:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def helper(acc, node):
            if node is None:
                return acc
            nxt = node.next
            node.next = acc
            return helper(node, nxt)

        return helper(None, head)

This is a common trick in functional programming that transforms a regular recursion into a tail recursion by introducing an accumulator.

A tail recursion is a special kind of recursion where the recursive call is the function’s last operation along that execution path. The general idea of converting to a tail recursion is to do the work “on the way down” instead of “on the way back up”, by carrying state with an accumulator argument. Note that it’s not always convertible. In this case it is. Each recursive call builds up the answer by appending the current node to acc as the head, so a reversed linked list is built on acc when reaching the end.

The reason to convert to tail recursion is that it becomes possible to apply compiler optimizations that basically reuse the current stack frame for the recursive call instead of allocating a new one for each recursive call. We know for sure that once we start the recursive function call, the current function frame is useless, as we are not doing any more work after the recursive call returns.

Therefore, we can argue the above implementation has $O(1)$ space complexity under TCO (tail call optimization). The caveat, however, is that CPython doesn’t support TCO, so in Python, this is still technically $O(n)$ space. In some other programming languages like OCaml, the equivalent code is tail-call optimized.

let rev list =
  let rec aux acc = function
    | [] -> acc
    | h :: t -> aux (h :: acc) t
  in
  aux [] list

Now, looking back at the iterative implementation, we can see it’s essentially doing the same thing as our tail-recursive implementation, just expressed in a different way.

As a side note, the iterative implementation has a more concise version:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr is not None:
            curr.next, prev, curr = prev, curr, curr.next
        return prev

Note that multiple assignment (or tuple unpacking) in Python works by first evaluating RHS into a tuple (snapshot of old values), then unpacking and assigning LHS from left to right. So on the LHS, curr must appear after curr.next.

Fast & Slow Pointers

The fast and slow pointer pattern can be used to find the middle node of a linked list, or to detect if a linked list contains a loop.

LeetCode: 876. Middle of the Linked List

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        return slow

The fast pointer moves two steps at a time, and the slow pointer one at a time. When the fast pointer reaches the end of a list, the slow pointer rests exactly at the halfway point. Here’s a variant:

def middleNode(self, head: ListNode) -> ListNode:
    slow, fast = head, head
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

They return different middle nodes when there are even number of nodes in the linked list.

initialization	odd # of nodes (e.g. `1->2->3`)	even # of nodes (e.g. `1->2->3->4`)
`fast = head`	slow = middle (`2`)	slow = second middle (`3`)
`fast = head.next`	slow = middle (`2`)	slow = first middle (`2`)

141. Linked List Cycle

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if fast == slow:
                return True
        return False

If there’s no cycle, the fast pointer will hit the end. If there’s a cycle, the fast pointer will lap the slow one: inside the cycle the gap shrinks by exactly 1 per iteration, so the pointers will meet rather than jumping over.

Dummy Node

Sometimes a dummy node makes life easier. It’s a placeholder node placed before the head, so an operation that may modify the head (e.g. deletion, insertion, merging) needs no special care: every node, including the head, is reached through some node’s next pointer, and the head of the resulting list is simply dummy.next.

Examples

LeetCode: 21. Merge Two Sorted Lists

class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next

Without a dummy node, we would have to pick which of the two heads starts the merged list before doing anything.

LeetCode: 234. Palindrome Linked List

We can solve this problem in three steps: find the middle node (breaking the linked list into two halves), reverse the second half, and compare the two halves.

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next

        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        fst, snd = head, prev
        while snd:
            if fst.val != snd.val:
                return False
            fst, snd = fst.next, snd.next
        return True