DSA Patterns in Python – DSA

      Ankush More

      Table of Contents

      1. Introduction to Patterns
      2. Two Pointers
      3. Sliding Window
      4. Fast & Slow Pointers (Floyd’s Cycle)
      5. Binary Search
      6. Prefix Sum
      7. Merge Intervals
      8. Linked List In-Place Reversal
      9. Tree BFS (Level Order)
      10. Tree DFS
      11. Backtracking
      12. Dynamic Programming
      13. Monotonic Stack
      14. Top K Elements
      15. K-Way Merge
      16. Graph BFS / DFS
      17. Union Find (Disjoint Set)
      18. Trie (Prefix Tree)
      19. Bit Manipulation
      20. Pattern Selection Guide

      Introduction to Patterns

      A DSA Pattern is a reusable problem-solving template that applies to a family of similar problems. Instead of solving each problem from scratch, recognizing the right pattern lets you immediately know the approach, data structures, and complexity.

      Why Learn Patterns?

      • Interview Readiness: Most coding interviews test 10–15 core patterns
      • Speed: Recognize problem type in seconds instead of minutes
      • Confidence: Systematic approach instead of guessing
      • Transferability: One pattern solves dozens of problems

      Pattern Categories

      INPUT SHAPE           PATTERNS
────────────────────────────────────────────────────────
Array / String   →  Two Pointers, Sliding Window, Prefix Sum,
                    Binary Search, Monotonic Stack
Linked List      →  Fast & Slow, In-Place Reversal
Tree             →  BFS, DFS (pre/in/post order)
Graph            →  BFS, DFS, Union Find
Intervals        →  Merge Intervals, Sweep Line
Subsets/Combos   →  Backtracking
Optimization     →  Dynamic Programming
Frequency/Top-K  →  Heap, Hash Map
      Python

      How to Identify a Pattern

      1. Is the input sorted? → Binary Search or Two Pointers
2. Do you need a subarray/substring? → Sliding Window
3. Detect a cycle? → Fast & Slow Pointers
4. Overlapping intervals? → Merge Intervals
5. Top/bottom K elements? → Heap
6. All combinations/permutations? → Backtracking
7. "Min/Max of a subproblem"? → Dynamic Programming
8. Next greater/smaller? → Monotonic Stack
9. Connected components or union? → Union Find
10. Prefix matching? → Trie
      Python

      Two Pointers

      Core Idea

      Use two indices (pointers) that move toward each other or in the same direction to reduce a brute-force O(n²) solution to O(n).

      When to Use

      • Sorted array or string
      • Finding a pair (or triplet) with a given sum
      • Removing duplicates in-place
      • Squaring a sorted array
      • Palindrome check

      Template

      def two_pointers(arr):
    left, right = 0, len(arr) - 1

    while left < right:
        if condition_met(arr[left], arr[right]):
            # process answer
            left += 1
            right -= 1
        elif need_larger_sum(arr[left], arr[right]):
            left += 1
        else:
            right -= 1
      Python

      Pattern Variants

      Variant 1: Opposite ends → move left up, right down
Variant 2: Same direction → slow and fast pointer (like remove duplicates)
Variant 3: Two arrays → one pointer each, advance the smaller
      Python

      Problem 1: Two Sum II (Sorted Array)

      def two_sum_sorted(nums, target):
    """
    Find indices of two numbers that add up to target.
    Input: sorted array     Time: O(n)    Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left + 1, right + 1]   # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

print(two_sum_sorted([2, 7, 11, 15], 9))    # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]
      Python

      Problem 2: Three Sum

      def three_sum(nums):
    """
    Find all unique triplets that sum to zero.
    Time: O(n²)    Space: O(1) excluding output
    """
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # Skip duplicates for first element

        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1   # Skip duplicates
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1  # Skip duplicates
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
      Python

      Problem 3: Remove Duplicates from Sorted Array

      def remove_duplicates(nums):
    """
    Remove duplicates in-place. Return new length.
    Same-direction two pointers.
    Time: O(n)    Space: O(1)
    """
    if not nums:
        return 0

    slow = 0   # Boundary of unique section
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1  # Length of unique section

nums = [1, 1, 2, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k])   # [1, 2, 3, 4]
      Python

      Problem 4: Container with Most Water

      def max_area(height):
    """
    Find two lines that form a container holding the most water.
    Time: O(n)    Space: O(1)

    Key insight: area = min(h[left], h[right]) * (right - left)
    Always move the pointer with the shorter height inward.
    """
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        water = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, water)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
      Python

      Problem 5: Valid Palindrome

      def is_palindrome(s):
    """
    Check if string is palindrome (alphanumeric only, ignore case).
    Time: O(n)    Space: O(1)
    """
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1

    return True

print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                      # False
      Python

      Sliding Window

      Core Idea

      Maintain a window (subarray/substring) over the input that expands and shrinks to find the optimal subarray matching a condition. Avoids re-computing from scratch by sliding one element at a time.

      When to Use

      • Maximum/minimum subarray of size k
      • Longest/shortest subarray satisfying a condition
      • All substrings with exactly k distinct characters
      • Anagram / permutation detection in string

      Template: Fixed Window

      def fixed_window(arr, k):
    """Sliding window of fixed size k"""
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # Add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum
      Python

      Template: Variable Window

      def variable_window(arr, condition):
    """Sliding window with variable size"""
    left = 0
    result = 0
    window_state = {}  # Track window contents

    for right in range(len(arr)):
        # Expand: add arr[right] to window
        window_state[arr[right]] = window_state.get(arr[right], 0) + 1

        # Shrink: move left until window is valid
        while not is_valid(window_state):
            window_state[arr[left]] -= 1
            if window_state[arr[left]] == 0:
                del window_state[arr[left]]
            left += 1

        # Update result with current valid window
        result = max(result, right - left + 1)

    return result
      Python

      Problem 1: Maximum Subarray Sum of Size K

      def max_subarray_sum_k(nums, k):
    """
    Fixed window: maximum sum of any subarray of size k.
    Time: O(n)    Space: O(1)
    """
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_subarray_sum_k([2, 1, 5, 1, 3, 2], 3))  # 9  (5+1+3)
print(max_subarray_sum_k([2, 3, 4, 1, 5], 2))      # 7  (3+4)
      Python

      Problem 2: Longest Substring Without Repeating Characters

      def length_of_longest_substring(s):
    """
    Variable window: longest substring with all unique characters.
    Time: O(n)    Space: O(min(n, charset))
    """
    char_index = {}  # char → most recent index
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        # If char is already in window, move left past it
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

print(length_of_longest_substring("abcabcbb"))  # 3  ("abc")
print(length_of_longest_substring("bbbbb"))     # 1  ("b")
print(length_of_longest_substring("pwwkew"))    # 3  ("wke")
      Python

      Problem 3: Minimum Window Substring

      from collections import Counter

def min_window(s, t):
    """
    Find shortest substring of s containing all characters of t.
    Time: O(|s| + |t|)    Space: O(|t|)
    """
    if not t or not s:
        return ""

    need = Counter(t)
    have = {}
    formed = 0                        # Number of unique chars with required frequency
    required = len(need)
    left = 0
    min_len = float('inf')
    result = ""

    for right, char in enumerate(s):
        have[char] = have.get(char, 0) + 1
        if char in need and have[char] == need[char]:
            formed += 1

        # Shrink window from left if all characters are covered
        while formed == required:
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                result = s[left:right + 1]

            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1

    return result

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "a"))               # "a"
print(min_window("a", "aa"))              # ""
      Python

      Problem 4: Longest Substring with At Most K Distinct Characters

      def longest_k_distinct(s, k):
    """
    Variable window: longest substring with at most k distinct characters.
    Time: O(n)    Space: O(k)
    """
    char_count = {}
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        char_count[char] = char_count.get(char, 0) + 1

        # Shrink window if more than k distinct chars
        while len(char_count) > k:
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1

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

    return max_len

print(longest_k_distinct("araaci", 2))   # 4  ("araa")
print(longest_k_distinct("cbbebi", 3))   # 5  ("cbbeb")
      Python

      Problem 5: Permutation in String

      from collections import Counter

def check_inclusion(s1, s2):
    """
    Check if any permutation of s1 exists as a substring of s2.
    Fixed window of size len(s1).
    Time: O(|s2|)    Space: O(1) — at most 26 letters
    """
    if len(s1) > len(s2):
        return False

    need = Counter(s1)
    window = Counter(s2[:len(s1)])

    if window == need:
        return True

    for i in range(len(s1), len(s2)):
        new_char = s2[i]
        old_char = s2[i - len(s1)]

        window[new_char] += 1
        window[old_char] -= 1
        if window[old_char] == 0:
            del window[old_char]

        if window == need:
            return True

    return False

print(check_inclusion("ab", "eidbaooo"))   # True ("ba")
print(check_inclusion("ab", "eidboaoo"))   # False
      Python

      Fast & Slow Pointers (Floyd’s Cycle)

      Core Idea

      Use two pointers moving at different speeds (1x and 2x) through a sequence. The fast pointer eventually “laps” the slow pointer if a cycle exists.

      When to Use

      • Detect a cycle in linked list or array
      • Find the start of a cycle
      • Find middle of a linked list
      • Determine if a number is a “happy number”
      • Find duplicate in array (cycle detection)

      Template

      def fast_slow(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next          # Move 1 step
        fast = fast.next.next     # Move 2 steps

        if slow == fast:
            return True   # Cycle detected

    return False
      Python

      Problem 1: Linked List Cycle Detection

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

def has_cycle(head):
    """
    Detect if linked list has a cycle.
    Time: O(n)    Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False
      Python

      Problem 2: Find Cycle Start

      def detect_cycle_start(head):
    """
    Find the node where cycle begins.
    Time: O(n)    Space: O(1)

    Key insight: after slow and fast meet inside the cycle,
    reset one pointer to head. Now both advance 1 step at a time.
    They meet at the cycle start.
    """
    slow = fast = head

    # Phase 1: detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle

    # Phase 2: find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # Cycle start node
      Python

      Problem 3: Middle of Linked List

      def find_middle(head):
    """
    Find middle node. If two middles, return second.
    Time: O(n)    Space: O(1)

    When fast reaches end, slow is at middle.
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow
      Python

      Problem 4: Happy Number

      def is_happy(n):
    """
    A happy number eventually reaches 1 when you repeatedly sum
    the squares of its digits. Otherwise it loops forever.
    Detect the loop with fast & slow pointers.
    Time: O(log n)    Space: O(1)
    """
    def next_num(n):
        total = 0
        while n > 0:
            digit = n % 10
            total += digit * digit
            n //= 10
        return total

    slow = n
    fast = next_num(n)

    while fast != 1 and slow != fast:
        slow = next_num(slow)
        fast = next_num(next_num(fast))

    return fast == 1

print(is_happy(19))   # True  (1² + 9² = 82 → 68 → 100 → 1)
print(is_happy(2))    # False
      Python

      Problem 5: Find Duplicate Number (Floyd’s Cycle)

      def find_duplicate(nums):
    """
    Find the one duplicate in nums[1..n] where n = len(nums)-1.
    Treat values as "next pointers" — this creates a cycle.
    Time: O(n)    Space: O(1)  (no set or sort allowed)
    """
    slow = fast = nums[0]

    # Phase 1: find intersection point
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: find cycle entry (= duplicate number)
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

print(find_duplicate([1, 3, 4, 2, 2]))  # 2
print(find_duplicate([3, 1, 3, 4, 2]))  # 3
      Python

      Core Idea

      Repeatedly halve the search space by comparing the middle element to the target. Requires the search space to be monotone (sorted or satisfying a predicate that transitions once).

      When to Use

      • Search in sorted array
      • Find boundary / first-true in monotone predicate
      • Answer binary search (minimize/maximize with feasibility check)
      • Rotated sorted array
      • Square root / peak element

      Templates

      # Template 1: Classic — find exact target
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # Avoids integer overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Template 2: Left boundary — first position where arr[i] >= target
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left   # Index of first element >= target

# Template 3: Answer binary search — minimize/maximize answer
def binary_search_answer(lo, hi, feasible):
    """
    Find smallest value in [lo, hi] for which feasible() is True.
    Assumes: feasible is False for small values, True for large (monotone).
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid       # mid could be answer, search left half
        else:
            lo = mid + 1   # mid too small, search right half
    return lo
      Python
      def search(nums, target):
    """Time: O(log n)    Space: O(1)"""
    left, right = 0, len(nums) - 1

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

    return -1

print(search([-1, 0, 3, 5, 9, 12], 9))   # 4
print(search([-1, 0, 3, 5, 9, 12], 2))   # -1
      Python

      Problem 2: Search in Rotated Sorted Array

      def search_rotated(nums, target):
    """
    Search in a sorted array that was rotated at an unknown pivot.
    Key: one half is always sorted — decide which half to search.
    Time: O(log n)    Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1
      Python

      Problem 3: Find First and Last Position

      def search_range(nums, target):
    """
    Find [first_pos, last_pos] of target. Return [-1,-1] if not found.
    Time: O(log n)    Space: O(1)
    """
    def find_left():
        left, right = 0, len(nums) - 1
        idx = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                right = mid - 1    # Keep searching left
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    def find_right():
        left, right = 0, len(nums) - 1
        idx = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                left = mid + 1     # Keep searching right
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    return [find_left(), find_right()]

print(search_range([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
print(search_range([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]
      Python

      Problem 4: Minimum in Rotated Sorted Array

      def find_min(nums):
    """
    Find minimum in a rotated sorted array.
    Time: O(log n)    Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1    # Min is in the right half
        else:
            right = mid       # Mid could be the min

    return nums[left]

print(find_min([3, 4, 5, 1, 2]))    # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
      Python
      import math

def min_eating_speed(piles, h):
    """
    Find minimum eating speed k such that Koko finishes all piles within h hours.
    Classic "binary search on answer" pattern.
    Time: O(n log max_pile)    Space: O(1)
    """
    def can_finish(speed):
        hours = sum(math.ceil(pile / speed) for pile in piles)
        return hours <= h

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid        # mid is feasible, try smaller
        else:
            left = mid + 1     # mid too slow, try larger

    return left

print(min_eating_speed([3, 6, 7, 11], 8))     # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30
      Python

      Prefix Sum

      Core Idea

      Pre-compute cumulative sums so any subarray sum sum(arr[i..j]) can be answered in O(1) as prefix[j+1] - prefix[i]. Combine with a hash map to find subarrays satisfying a condition.

      When to Use

      • Subarray sum equals K
      • Count subarrays with specific sum/product
      • Range sum queries (static array)
      • 2D submatrix sum queries

      Template

      def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, num in enumerate(nums):
        prefix[i + 1] = prefix[i] + num
    return prefix

# Sum of nums[i..j] (inclusive, 0-indexed)
def range_sum(prefix, i, j):
    return prefix[j + 1] - prefix[i]
      Python

      Problem 1: Subarray Sum Equals K

      def subarray_sum(nums, k):
    """
    Count subarrays with sum exactly equal to k.
    Time: O(n)    Space: O(n)

    Key: prefix_sum[j] - prefix_sum[i] = k
         → prefix_sum[i] = prefix_sum[j] - k
    Count how many previous prefix sums equal (current - k).
    """
    count = 0
    prefix_sum = 0
    seen = {0: 1}    # prefix_sum → frequency

    for num in nums:
        prefix_sum += num
        count += seen.get(prefix_sum - k, 0)
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1

    return count

print(subarray_sum([1, 1, 1], 2))      # 2
print(subarray_sum([1, 2, 3], 3))      # 2  ([1,2] and [3])
print(subarray_sum([-1, -1, 1], 0))    # 1
      Python

      Problem 2: Longest Subarray with Sum K

      def longest_subarray_sum_k(nums, k):
    """
    Find length of longest subarray with sum equal to k (may have negatives).
    Time: O(n)    Space: O(n)
    """
    prefix_sum = 0
    max_len = 0
    first_seen = {0: -1}   # prefix_sum → earliest index

    for i, num in enumerate(nums):
        prefix_sum += num
        if prefix_sum - k in first_seen:
            max_len = max(max_len, i - first_seen[prefix_sum - k])
        if prefix_sum not in first_seen:
            first_seen[prefix_sum] = i   # Only store first occurrence

    return max_len

print(longest_subarray_sum_k([1, -1, 5, -2, 3], 3))   # 4  ([1,-1,5,-2])
print(longest_subarray_sum_k([-2, -1, 2, 1], 1))       # 2  ([2,-1] or [-1,2])
      Python

      Problem 3: Range Sum Query (Immutable)

      class NumArray:
    """
    Answer multiple range sum queries efficiently.
    Build: O(n)    Query: O(1)    Space: O(n)
    """
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + num

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

# Usage
na = NumArray([-2, 0, 3, -5, 2, -1])
print(na.sum_range(0, 2))   # 1   (-2 + 0 + 3)
print(na.sum_range(2, 5))   # -1  (3 + -5 + 2 + -1)
print(na.sum_range(0, 5))   # -3
      Python

      Problem 4: Continuous Subarray Sum (Multiple of K)

      def check_subarray_sum(nums, k):
    """
    Check if any subarray of length >= 2 has a sum that is a multiple of k.
    Time: O(n)    Space: O(n)

    Key: (prefix[j] - prefix[i]) % k == 0  →  prefix[j] % k == prefix[i] % k
    """
    # {remainder: earliest index where this remainder was seen}
    seen = {0: -1}   # Remainder 0 seen before index 0
    prefix_sum = 0

    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k

        if remainder in seen:
            if i - seen[remainder] >= 2:   # Subarray length at least 2
                return True
        else:
            seen[remainder] = i   # Only record first occurrence

    return False

print(check_subarray_sum([23, 2, 4, 6, 7], 6))   # True  ([2,4])
print(check_subarray_sum([23, 2, 6, 4, 7], 6))   # True  ([23,2,6,4,7])
print(check_subarray_sum([23, 2, 6, 4, 7], 13))  # False
      Python

      Merge Intervals

      Core Idea

      Sort intervals by start time. Then sweep through and merge overlapping ones. An interval [a,b] overlaps [c,d] if c <= b (i.e., the next interval starts before or when the current one ends).

      When to Use

      • Merge overlapping intervals
      • Insert an interval into sorted list
      • Find gaps / free time slots
      • Calendar problems
      • Meeting rooms scheduling

      Template

      def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])   # Sort by start
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:        # Overlaps
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged
      Python

      Problem 1: Merge Overlapping Intervals

      def merge(intervals):
    """
    Time: O(n log n)    Space: O(n)
    """
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0][:]]   # Copy first interval

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

print(merge([[1,3],[2,6],[8,10],[15,18]]))  # [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))                 # [[1,5]]
      Python

      Problem 2: Insert Interval

      def insert(intervals, new_interval):
    """
    Insert new_interval into sorted non-overlapping intervals.
    Time: O(n)    Space: O(n)
    """
    result = []
    i = 0
    n = len(intervals)

    # Add all intervals that end before new_interval starts
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # Merge all overlapping intervals
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    # Add remaining intervals
    result.extend(intervals[i:])
    return result

print(insert([[1,3],[6,9]], [2,5]))          # [[1,5],[6,9]]
print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]
      Python

      Problem 3: Minimum Meeting Rooms

      import heapq

def min_meeting_rooms(intervals):
    """
    Find minimum number of meeting rooms required.
    Time: O(n log n)    Space: O(n)

    Strategy: sort by start; use min-heap to track room end times.
    If earliest-ending room is free, reuse it; else open new room.
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])
    end_times = []  # Min-heap of end times

    for start, end in intervals:
        if end_times and end_times[0] <= start:
            heapq.heapreplace(end_times, end)   # Reuse room
        else:
            heapq.heappush(end_times, end)       # New room needed

    return len(end_times)

print(min_meeting_rooms([[0,30],[5,10],[15,20]]))   # 2
print(min_meeting_rooms([[7,10],[2,4]]))            # 1
      Python

      Problem 4: Non-Overlapping Intervals (Minimum Removals)

      def erase_overlap_intervals(intervals):
    """
    Find minimum number of intervals to remove to make rest non-overlapping.
    Time: O(n log n)    Space: O(1)

    Greedy: sort by end time, keep interval with earliest end.
    Count how many we skip (overlap with previous kept interval).
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])   # Sort by end time
    removals = 0
    prev_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start < prev_end:       # Overlaps: remove current
            removals += 1
        else:
            prev_end = end         # No overlap: keep current

    return removals

print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2
      Python

      Linked List In-Place Reversal

      Core Idea

      Reverse a linked list (or a portion) using three pointers: prev, curr, and next. No extra space — modify .next pointers in-place.

      When to Use

      • Reverse entire linked list
      • Reverse a sublist [left, right]
      • Reverse in k-group chunks
      • Detect/remove palindrome sublist
      • Reorder list (merge halves)

      Template

      def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next   # Save next
        curr.next = prev        # Reverse pointer
        prev = curr             # Advance prev
        curr = next_node        # Advance curr

    return prev   # New head
      Python

      Problem 1: Reverse Linked List

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

def reverse_list(head):
    """Time: O(n)    Space: O(1)"""
    prev = None
    curr = head

    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    return prev

def reverse_list_recursive(head):
    """Recursive version. Time: O(n)    Space: O(n) call stack"""
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head
      Python

      Problem 2: Reverse Sublist [Left, Right]

      def reverse_between(head, left, right):
    """
    Reverse nodes from position left to right (1-indexed).
    Time: O(n)    Space: O(1)
    """
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    # Move prev to node just before position left
    for _ in range(left - 1):
        prev = prev.next

    curr = prev.next
    for _ in range(right - left):
        next_node = curr.next
        curr.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node

    return dummy.next
      Python

      Problem 3: Reverse in K-Group

      def reverse_k_group(head, k):
    """
    Reverse nodes in groups of k. Leave remainder as-is.
    Time: O(n)    Space: O(1)
    """
    def has_k_nodes(node, k):
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        return count == k

    if not has_k_nodes(head, k):
        return head

    curr = head
    prev = None
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    head.next = reverse_k_group(curr, k)   # Recurse on remainder
    return prev
      Python

      Problem 4: Reorder List (L0→Ln→L1→Ln-1→…)

      def reorder_list(head):
    """
    Reorder: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
    Time: O(n)    Space: O(1)

    Steps:
    1. Find middle (fast & slow)
    2. Reverse second half
    3. Merge two halves
    """
    # Step 1: Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse second half
    prev, curr = None, slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    second = prev

    # Step 3: Merge
    first = head
    while second.next:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2
      Python

      Tree BFS (Level Order)

      Core Idea

      Traverse a tree level by level using a queue. Process all nodes at depth d before processing any node at depth d+1.

      When to Use

      • Level order traversal
      • Minimum depth / shortest path in unweighted tree
      • Right-side view of tree
      • Zigzag level order
      • Connect next right pointers

      Template

      from collections import deque

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

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

    while queue:
        level_size = len(queue)   # Snapshot of current level
        level = []

        for _ in range(level_size):
            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
      Python

      Problem 1: Level Order Traversal

      from collections import deque

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

def level_order(root):
    """Time: O(n)    Space: O(n)"""
    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
      Python

      Problem 2: Right Side View

      def right_side_view(root):
    """
    Return values visible from the right side (rightmost node per level).
    Time: O(n)    Space: O(n)
    """
    if not root:
        return []

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

    while queue:
        for i in range(len(queue)):
            node = queue.popleft()
            if i == 0:
                result.append(node.val)   # First dequeued is rightmost (added last)
            if node.right: queue.append(node.right)
            if node.left:  queue.append(node.left)

    return result
      Python

      Problem 3: Minimum Depth

      def min_depth(root):
    """
    Find minimum depth (root to nearest leaf).
    BFS finds the FIRST leaf — that's the minimum depth.
    Time: O(n)    Space: O(n)
    """
    if not root:
        return 0

    queue = deque([(root, 1)])   # (node, depth)

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

        # First leaf encountered is at minimum depth
        if not node.left and not node.right:
            return depth

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

    return 0
      Python

      Problem 4: Zigzag Level Order

      from collections import deque

def zigzag_level_order(root):
    """
    Alternate left-to-right and right-to-left per level.
    Time: O(n)    Space: O(n)
    """
    if not root:
        return []

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

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.insert(0, node.val)  # Prepend for reverse order
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
        left_to_right = not left_to_right

    return result
      Python

      Tree DFS

      Core Idea

      Traverse a tree depth-first: go as deep as possible before backtracking. Three orderings based on when you process the current node: before left+right (preorder), between them (inorder), or after (postorder).

      When to Use

      • Path sum problems
      • Serialize/deserialize tree
      • Validate BST
      • Lowest common ancestor
      • Diameter / max path sum

      Template

      def dfs_template(node, state):
    # Base case
    if not node:
        return base_value

    # Pre-order work (before children)
    # ...

    left_result = dfs_template(node.left, updated_state)
    right_result = dfs_template(node.right, updated_state)

    # Post-order work (after children)
    return combine(left_result, right_result)
      Python

      Problem 1: Path Sum (Root to Leaf)

      def has_path_sum(root, target):
    """
    Check if any root-to-leaf path sums to target.
    Time: O(n)    Space: O(h) where h = height
    """
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    target -= root.val
    return has_path_sum(root.left, target) or has_path_sum(root.right, target)
      Python

      Problem 2: Maximum Path Sum

      def max_path_sum(root):
    """
    Find maximum sum of any path (not necessarily root-to-leaf).
    Time: O(n)    Space: O(h)

    Key: each node contributes max(left_gain, 0) + max(right_gain, 0) + node.val
    Return only max(left, right) gain upward (can't go both ways up the tree).
    """
    max_sum = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left_gain  = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)

        # Best path through this node (could be the answer)
        max_sum[0] = max(max_sum[0], node.val + left_gain + right_gain)

        # Return best single-branch gain upward
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return max_sum[0]
      Python

      Problem 3: Validate BST

      def is_valid_bst(root):
    """
    Time: O(n)    Space: O(h)
    Pass valid range (min, max) down; every node must be in range.
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        if not (min_val < node.val < max_val):
            return False
        return (validate(node.left,  min_val,   node.val) and
                validate(node.right, node.val,  max_val))

    return validate(root, float('-inf'), float('inf'))
      Python

      Problem 4: Lowest Common Ancestor

      def lowest_common_ancestor(root, p, q):
    """
    Find LCA of nodes p and q.
    Time: O(n)    Space: O(h)

    If both targets are in right subtree → recurse right
    If both in left → recurse left
    Otherwise current node is LCA
    """
    if not root or root == p or root == q:
        return root

    left  = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root    # p and q are on opposite sides
    return left or right
      Python

      Problem 5: Diameter of Binary Tree

      def diameter_of_binary_tree(root):
    """
    Find longest path between any two nodes (in number of edges).
    The diameter at any node = left_depth + right_depth.
    Time: O(n)    Space: O(h)
    """
    diameter = [0]

    def depth(node):
        if not node:
            return 0
        left  = depth(node.left)
        right = depth(node.right)
        diameter[0] = max(diameter[0], left + right)
        return 1 + max(left, right)

    depth(root)
    return diameter[0]
      Python

      Backtracking

      Core Idea

      Explore all possibilities by making a choice, recursing, and then undoing the choice (backtracking). Prune branches early when a partial solution can’t lead to a valid answer.

      When to Use

      • Generate all permutations / combinations / subsets
      • N-Queens, Sudoku solver
      • Word search in grid
      • Letter combinations of phone number
      • Palindrome partitioning

      Template

      def backtrack(result, current, remaining, start=0):
    # Base case: valid complete solution
    if is_complete(current):
        result.append(current[:])   # Snapshot — don't append reference
        return

    for choice in get_choices(remaining, start):
        if not is_valid(choice, current):
            continue                   # Prune

        current.append(choice)         # Make choice
        backtrack(result, current, remaining, next_start)
        current.pop()                  # Undo choice — BACKTRACK
      Python

      Problem 1: All Subsets

      def subsets(nums):
    """
    Generate all 2^n subsets.
    Time: O(n × 2^n)    Space: O(n)
    """
    result = []

    def backtrack(start, current):
        result.append(current[:])   # Every partial state is a valid subset

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
      Python

      Problem 2: All Permutations

      def permutations(nums):
    """
    Generate all n! permutations.
    Time: O(n × n!)    Space: O(n)
    """
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return

        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()

    backtrack([], nums)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
      Python

      Problem 3: Combinations Sum

      def combination_sum(candidates, target):
    """
    Find all combos of candidates summing to target. Can reuse elements.
    Time: O(n^(t/m)) where t=target, m=min candidate
    """
    result = []
    candidates.sort()

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break              # Pruning: sorted, no point continuing

            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # i (not i+1) = reuse allowed
            current.pop()

    backtrack(0, [], target)
    return result

print(combination_sum([2, 3, 6, 7], 7))  # [[2,2,3],[7]]
      Python

      Problem 4: Word Search in Grid

      def exist(board, word):
    """
    Check if word exists as a path in the grid (4-directional).
    Time: O(m × n × 4^L) where L = len(word)
    Space: O(L) recursion stack
    """
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
            return False

        temp = board[r][c]
        board[r][c] = '#'           # Mark visited (in-place)

        found = (backtrack(r+1, c, idx+1) or
                 backtrack(r-1, c, idx+1) or
                 backtrack(r, c+1, idx+1) or
                 backtrack(r, c-1, idx+1))

        board[r][c] = temp          # Restore (backtrack)
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
print(exist(board, "ABCCED"))   # True
print(exist(board, "ABCB"))     # False
      Python

      Problem 5: N-Queens

      def solve_n_queens(n):
    """
    Place n queens on n×n board with no two attacking each other.
    Time: O(n!)    Space: O(n)
    """
    result = []
    cols = set()           # Columns already occupied
    pos_diag = set()       # r + c diagonals occupied
    neg_diag = set()       # r - c diagonals occupied

    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row+col) in pos_diag or (row-col) in neg_diag:
                continue    # Prune: under attack

            # Place queen
            cols.add(col); pos_diag.add(row+col); neg_diag.add(row-col)
            board[row][col] = 'Q'

            backtrack(row + 1)

            # Remove queen (backtrack)
            cols.remove(col); pos_diag.remove(row+col); neg_diag.remove(row-col)
            board[row][col] = '.'

    backtrack(0)
    return result

print(len(solve_n_queens(4)))   # 2 solutions
print(len(solve_n_queens(8)))   # 92 solutions
      Python

      Dynamic Programming

      Core Idea

      Break a problem into overlapping subproblems and store results to avoid recomputation. Two approaches:

      • Top-Down (Memoization): Recursion + cache
      • Bottom-Up (Tabulation): Fill a table from base cases up

      When to Use

      • Count ways to do something
      • Min/max cost/profit
      • Yes/no feasibility → DP if “can we achieve X?”
      • Optimal choices at each step (overlapping subproblems + optimal substructure)
      • Keywords: “minimum”, “maximum”, “number of ways”, “can we”, “is it possible”

      Template

      # Top-Down (Memoization)
from functools import lru_cache

def dp_top_down(n):
    @lru_cache(maxsize=None)
    def solve(state):
        if base_case(state):
            return base_value
        return min/max/sum(solve(next_state) for next_state in transitions(state))
    return solve(initial_state)

# Bottom-Up (Tabulation)
def dp_bottom_up(n):
    dp = [initial_values] * (n + 1)
    dp[0] = base_case_0

    for i in range(1, n + 1):
        dp[i] = transition(dp[i-1], ...)

    return dp[n]
      Python

      DP Problem Families

      1D DP         : Fibonacci, Climb Stairs, House Robber, Jump Game
Interval DP   : Burst Balloons, Matrix Chain Multiplication
Knapsack DP   : 0/1 Knapsack, Subset Sum, Coin Change
String DP     : LCS, Edit Distance, Palindrome Partitioning
Grid DP       : Unique Paths, Min Path Sum, Dungeon Game
      Python

      Problem 1: Climbing Stairs

      def climb_stairs(n):
    """
    Count ways to climb n stairs (1 or 2 steps at a time) = Fibonacci.
    Time: O(n)    Space: O(1)
    """
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

print(climb_stairs(2))   # 2
print(climb_stairs(5))   # 8
      Python

      Problem 2: House Robber

      def rob(nums):
    """
    Rob houses without robbing two adjacent. Maximize amount.
    Time: O(n)    Space: O(1)

    dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    """
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

print(rob([1, 2, 3, 1]))    # 4
print(rob([2, 7, 9, 3, 1])) # 12
      Python

      Problem 3: Coin Change (Unbounded Knapsack)

      def coin_change(coins, amount):
    """
    Minimum number of coins to make amount. Return -1 if impossible.
    Time: O(amount × len(coins))    Space: O(amount)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0    # 0 coins needed for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 11], 15))    # 3 (5+5+5)
print(coin_change([2], 3))            # -1
      Python

      Problem 4: Longest Common Subsequence

      def lcs(text1, text2):
    """
    Find length of longest common subsequence.
    Time: O(m × n)    Space: O(m × n)

    dp[i][j] = LCS of text1[:i] and text2[:j]
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs("abcde", "ace"))    # 3  ("ace")
print(lcs("abc", "abc"))      # 3
print(lcs("abc", "def"))      # 0
      Python

      Problem 5: 0/1 Knapsack

      def knapsack(weights, values, capacity):
    """
    Classic 0/1 Knapsack: each item can be taken at most once.
    Time: O(n × capacity)    Space: O(capacity) with rolling array
    """
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Traverse capacity in REVERSE to avoid reusing same item
        for c in range(capacity, weights[i] - 1, -1):
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i])

    return dp[capacity]

print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))   # 10
      Python

      Problem 6: Longest Increasing Subsequence

      def length_of_lis(nums):
    """
    Find length of longest strictly increasing subsequence.
    Time: O(n log n) with patience sorting    Space: O(n)
    """
    import bisect
    tails = []   # tails[i] = smallest tail of all IS of length i+1

    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)    # Extend longest IS
        else:
            tails[pos] = num     # Replace — maintain smallest tail

    return len(tails)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 ([2,3,7,101])
print(length_of_lis([0, 1, 0, 3, 2, 3]))             # 4
      Python

      Problem 7: Edit Distance

      def min_distance(word1, word2):
    """
    Minimum edit distance (insert, delete, replace) to convert word1 → word2.
    Time: O(m × n)    Space: O(m × n)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1): dp[i][0] = i      # Delete all of word1
    for j in range(n + 1): dp[0][j] = j      # Insert all of word2

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]      # No edit needed
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete from word1
                    dp[i][j-1],    # Insert into word1
                    dp[i-1][j-1]   # Replace
                )

    return dp[m][n]

print(min_distance("horse", "ros"))   # 3
print(min_distance("intention", "execution"))  # 5
      Python

      Monotonic Stack

      Core Idea

      Maintain a stack whose elements are always monotonically increasing or decreasing. When a new element breaks the monotonicity, pop elements from the stack — each pop reveals a “next greater/smaller” relationship.

      When to Use

      • Next Greater Element / Next Smaller Element
      • Largest Rectangle in Histogram
      • Trap Rain Water
      • Daily Temperatures
      • Remove K Digits

      Template

      # Next Greater Element (Monotonic Decreasing Stack)
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []   # Stack of indices (elements are decreasing)

    for i, num in enumerate(nums):
        # Pop elements smaller than current — current is their "next greater"
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result  # Remaining in stack have no next greater → stay -1
      Python

      Problem 1: Daily Temperatures

      def daily_temperatures(temperatures):
    """
    For each day, find how many days until a warmer temperature.
    Time: O(n)    Space: O(n)
    """
    result = [0] * len(temperatures)
    stack = []   # Monotonically decreasing stack of indices

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx     # Days waited
        stack.append(i)

    return result

print(daily_temperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
      Python

      Problem 2: Largest Rectangle in Histogram

      def largest_rectangle_area(heights):
    """
    Find largest rectangle that fits under the histogram.
    Time: O(n)    Space: O(n)

    Use monotonic increasing stack. When height decreases,
    compute area for all taller bars that can no longer extend.
    """
    stack = []      # (index, height) — monotonically increasing
    max_area = 0

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx  # Current bar can extend back to this index
        stack.append((start, h))

    # Process remaining bars (they extend to the end)
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))

    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))   # 10
print(largest_rectangle_area([2, 4]))                # 4
      Python

      Problem 3: Trapping Rain Water

      def trap(height):
    """
    Calculate total rain water trapped between bars.
    Time: O(n)    Space: O(n)

    For each bar, water above it = min(max_left, max_right) - height[i]
    """
    stack = []    # Monotonically decreasing stack of indices
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded_height = min(height[left], h) - height[bottom]
            water += width * bounded_height
        stack.append(i)

    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))   # 6
print(trap([4,2,0,3,2,5]))               # 9
      Python

      Problem 4: Remove K Digits (Smallest Number)

      def remove_k_digits(num, k):
    """
    Remove k digits from num to make the smallest possible number.
    Time: O(n)    Space: O(n)

    Greedy: maintain monotonically increasing stack.
    Remove a digit when a smaller digit comes after it.
    """
    stack = []

    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # If k > 0 still, remove from end (largest digits)
    stack = stack[:-k] if k else stack

    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result or '0'

print(remove_k_digits("1432219", 3))   # "1219"
print(remove_k_digits("10200", 1))     # "200" → "200" → after lstrip → "200"
print(remove_k_digits("10", 2))        # "0"
      Python

      Top K Elements

      Core Idea

      Maintain a heap of size k to efficiently track the top-k elements while scanning through data. A min-heap of size k gives k largest; a max-heap of size k gives k smallest.

      When to Use

      • K largest / K smallest elements
      • Kth largest / Kth smallest
      • Top K frequent elements
      • K closest points

      Template

      import heapq

def top_k_largest(nums, k):
    """Min-heap of size k. Root = kth largest."""
    heap = nums[:k]
    heapq.heapify(heap)   # O(k)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)   # O(log k)

    return heap

def top_k_smallest(nums, k):
    """Max-heap of size k (negation). Root = kth smallest."""
    heap = [-x for x in nums[:k]]
    heapq.heapify(heap)

    for num in nums[k:]:
        if -num > heap[0]:  # num < (-heap[0]) i.e. num is smaller than current kth
            heapq.heapreplace(heap, -num)

    return [-x for x in heap]
      Python

      (Full examples covered in Heap section of 11-Heap.md)

      K-Way Merge

      Core Idea

      Merge K sorted sequences into one using a min-heap seeded with the first element from each sequence. Always pop the minimum and push the next element from that same sequence.

      When to Use

      • Merge K sorted arrays/lists
      • K sorted iterators
      • Find smallest range covering K sorted lists
      • External sort (merge sorted chunks on disk)

      Template

      import heapq

def k_way_merge(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))  # (value, list_idx, elem_idx)

    result = []
    while heap:
        val, li, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][ei+1], li, ei+1))
    return result
      Python

      Problem 1: Merge K Sorted Arrays

      import heapq

def merge_k_sorted(arrays):
    """
    Time: O(n log k) where n = total elements, k = number of arrays
    Space: O(k) for heap
    """
    heap = []
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))

    result = []
    while heap:
        val, arr_i, elem_i = heapq.heappop(heap)
        result.append(val)
        if elem_i + 1 < len(arrays[arr_i]):
            heapq.heappush(heap, (arrays[arr_i][elem_i + 1], arr_i, elem_i + 1))

    return result

arrays = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(arrays))   # [1, 2, 3, 4, 5, 6, 7, 8, 9]
      Python

      Problem 2: Smallest Range Covering K Lists

      import heapq

def smallest_range(nums):
    """
    Find smallest range [a, b] that includes at least one number from each list.
    Time: O(n log k)    Space: O(k)

    Strategy: maintain a window of k elements (one from each list).
    Track current max. Range = [heap_min, current_max].
    Advance the list with the smallest current element.
    """
    heap = []
    current_max = float('-inf')

    for i, lst in enumerate(nums):
        heapq.heappush(heap, (lst[0], i, 0))
        current_max = max(current_max, lst[0])

    best_range = [float('-inf'), float('inf')]

    while len(heap) == len(nums):   # Still have element from each list
        current_min, li, ei = heapq.heappop(heap)

        if current_max - current_min < best_range[1] - best_range[0]:
            best_range = [current_min, current_max]

        if ei + 1 < len(nums[li]):
            next_val = nums[li][ei + 1]
            heapq.heappush(heap, (next_val, li, ei + 1))
            current_max = max(current_max, next_val)

    return best_range

print(smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]))
# [20, 24]
      Python

      Graph BFS / DFS

      Core Idea

      BFS: Use a queue to explore level by level — finds shortest path in unweighted graphs. DFS: Use a stack (or recursion) to explore as deep as possible before backtracking.

      When to Use

      • BFS: Shortest path (unweighted), level-order, minimum steps
      • DFS: Connected components, cycle detection, topological sort, flood fill

      Templates

      from collections import deque

# BFS Template
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

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

    return result

# DFS Template (Iterative)
def dfs(graph, start):
    visited = set()
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

    return result

# DFS Template (Recursive)
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
      Python

      Problem 1: Number of Islands

      def num_islands(grid):
    """
    Count distinct islands (connected group of '1's).
    Time: O(m × n)    Space: O(m × n)
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'   # Mark visited (flood fill)
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1

    return count

grid = [["1","1","0","0","0"],
        ["1","1","0","0","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]]
print(num_islands(grid))   # 3
      Python

      Problem 2: Shortest Path in Binary Matrix

      from collections import deque

def shortest_path_binary_matrix(grid):
    """
    Shortest path from top-left to bottom-right through 0s (8-directional).
    Time: O(n²)    Space: O(n²)
    BFS guarantees shortest path in unweighted grid.
    """
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    queue = deque([(0, 0, 1)])   # (row, col, path_length)
    grid[0][0] = 1               # Mark visited

    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

    while queue:
        r, c, length = queue.popleft()
        if r == n - 1 and c == n - 1:
            return length

        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 1   # Mark visited
                queue.append((nr, nc, length + 1))

    return -1
      Python

      Problem 3: Topological Sort (Kahn’s Algorithm)

      from collections import deque

def topological_sort(n, prerequisites):
    """
    Topological ordering of n nodes with edges as prerequisites.
    Time: O(V + E)    Space: O(V + E)
    Kahn's BFS: repeatedly remove nodes with in-degree 0.
    """
    adj = [[] for _ in range(n)]
    in_degree = [0] * n

    for dest, src in prerequisites:
        adj[src].append(dest)
        in_degree[dest] += 1

    queue = deque(node for node in range(n) if in_degree[node] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []   # Empty = cycle detected

print(topological_sort(4, [[1,0],[2,0],[3,1],[3,2]]))  # [0,1,2,3] or [0,2,1,3]
      Python

      Problem 4: Clone Graph

      from collections import deque

class GraphNode:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def clone_graph(node):
    """
    Deep copy of graph.
    Time: O(V + E)    Space: O(V)
    """
    if not node:
        return None

    clones = {}   # original → clone

    queue = deque([node])
    clones[node] = GraphNode(node.val)

    while queue:
        curr = queue.popleft()
        for neighbor in curr.neighbors:
            if neighbor not in clones:
                clones[neighbor] = GraphNode(neighbor.val)
                queue.append(neighbor)
            clones[curr].neighbors.append(clones[neighbor])

    return clones[node]
      Python

      Union Find (Disjoint Set)

      Core Idea

      Maintain a collection of disjoint sets with two operations: find (which set does element x belong to?) and union (merge two sets). With path compression and union by rank, both operations are nearly O(1).

      When to Use

      • Find connected components
      • Detect cycles in undirected graph
      • Kruskal’s minimum spanning tree
      • Account merging / network connectivity
      • Redundant connections

      Template

      class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n   # Number of connected components

    def find(self, x):
        """Find root with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # Path compression
        return self.parent[x]

    def union(self, x, y):
        """Union by rank"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False   # Already in same set

        # Attach smaller rank tree under larger rank tree
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)
      Python

      Problem 1: Number of Connected Components

      def count_components(n, edges):
    """
    Count connected components in undirected graph.
    Time: O(E × α(n)) ≈ O(E)    Space: O(n)
    """
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

print(count_components(5, [[0,1],[1,2],[3,4]]))   # 2
print(count_components(5, [[0,1],[1,2],[2,3],[3,4]]))  # 1
      Python

      Problem 2: Redundant Connection

      def find_redundant_connection(edges):
    """
    Find the last edge that creates a cycle.
    Time: O(n α(n))    Space: O(n)
    """
    uf = UnionFind(len(edges) + 1)

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]   # Already connected — this edge is redundant

    return []

print(find_redundant_connection([[1,2],[1,3],[2,3]]))   # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]]))  # [1,4]
      Python

      Problem 3: Accounts Merge

      def accounts_merge(accounts):
    """
    Merge accounts sharing at least one email address.
    Time: O(n α(n))    Space: O(n)
    """
    uf = UnionFind(len(accounts))
    email_to_account = {}

    # Union accounts with shared emails
    for i, account in enumerate(accounts):
        for email in account[1:]:
            if email in email_to_account:
                uf.union(i, email_to_account[email])
            else:
                email_to_account[email] = i

    # Group emails by root account
    root_to_emails = {}
    for email, account_id in email_to_account.items():
        root = uf.find(account_id)
        root_to_emails.setdefault(root, set()).add(email)

    return [[accounts[root][0]] + sorted(emails)
            for root, emails in root_to_emails.items()]
      Python

      Trie (Prefix Tree)

      Core Idea

      A tree where each node represents a character. Paths from root to leaf spell out words. Enables O(L) insert/search where L = word length, and efficient prefix operations.

      When to Use

      • Autocomplete / search suggestions
      • Spell checking
      • Word search in dictionary
      • Longest common prefix
      • IP routing tables

      Implementation

      class TrieNode:
    def __init__(self):
        self.children = {}   # char → TrieNode
        self.is_end = False  # Marks end of a valid word


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """Time: O(L) where L = len(word)"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """Check if word exists. Time: O(L)"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        """Check if any word starts with prefix. Time: O(L)"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def delete(self, word):
        """Remove word from trie. Time: O(L)"""
        def _delete(node, word, depth):
            if depth == len(word):
                if node.is_end:
                    node.is_end = False
                return len(node.children) == 0   # Delete if leaf

            char = word[depth]
            if char not in node.children:
                return False

            should_delete = _delete(node.children[char], word, depth + 1)
            if should_delete:
                del node.children[char]
                return not node.is_end and len(node.children) == 0
            return False

        _delete(self.root, word, 0)

    def autocomplete(self, prefix):
        """Return all words with given prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]

        results = []
        def dfs(node, path):
            if node.is_end:
                results.append(prefix + path)
            for char, child in node.children.items():
                dfs(child, path + char)

        dfs(node, "")
        return results


# Usage
trie = Trie()
for word in ["apple", "app", "apply", "apt", "banana"]:
    trie.insert(word)

print(trie.search("app"))        # True
print(trie.search("ap"))         # False
print(trie.starts_with("ap"))    # True
print(trie.autocomplete("app"))  # ['app', 'apple', 'apply']
      Python

      Problem: Word Search II (Trie + Backtracking)

      def find_words(board, words):
    """
    Find all words from a dictionary that exist in the board.
    Time: O(m × n × 4^L × W) but Trie pruning makes it much faster.
    """
    trie = Trie()
    for word in words:
        trie.insert(word)

    rows, cols = len(board), len(board[0])
    found = set()

    def dfs(node, r, c, path):
        if node.is_end:
            found.add(path)

        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] not in node.children:
            return

        char = board[r][c]
        board[r][c] = '#'    # Mark visited

        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(node.children[char], r+dr, c+dc, path+char)

        board[r][c] = char   # Restore

    for r in range(rows):
        for c in range(cols):
            dfs(trie.root, r, c, "")

    return list(found)
      Python

      Bit Manipulation

      Core Idea

      Use bitwise operations to perform computations efficiently without loops or arithmetic. Crucial for low-level optimization and many clever tricks.

      Bit Tricks Reference

      # ─── Basic operators ──────────────────────────────────────────
n & 1             # Check if n is odd (last bit is 1)
n & (n - 1)       # Clear lowest set bit   (5 & 4 = 4: 101 & 100 = 100)
n & -n            # Isolate lowest set bit  (6 & -6 = 2: 110 & 010)
n | (1 << k)      # Set bit k               (n | 0b100 sets bit 2)
n & ~(1 << k)     # Clear bit k
n ^ (1 << k)      # Toggle bit k
(n >> k) & 1      # Get bit k
n ^ n             # = 0 (XOR self)
n ^ 0             # = n (XOR with 0)
a ^ b ^ a         # = b (cancel a)

# ─── Powers of 2 ─────────────────────────────────────────────
n & (n - 1) == 0  # True if n is a power of 2 (and n != 0)
n > 0 and n & (n-1) == 0   # Safe check

# ─── Count set bits ───────────────────────────────────────────
bin(n).count('1')           # Pythonic
n.bit_count()               # Python 3.10+

# ─── XOR properties ──────────────────────────────────────────
# 1. a ^ a = 0            (same values cancel)
# 2. a ^ 0 = a            (XOR with 0 is identity)
# 3. Commutative + Associative
# → XOR of all elements: unique element remains
      Python

      Problem 1: Single Number

      def single_number(nums):
    """
    Find the element that appears once (all others appear twice).
    Time: O(n)    Space: O(1)

    XOR all numbers: pairs cancel out, leaving the single element.
    """
    result = 0
    for num in nums:
        result ^= num
    return result

print(single_number([2, 2, 1]))         # 1
print(single_number([4, 1, 2, 1, 2]))   # 4
      Python

      Problem 2: Count Set Bits (Hamming Weight)

      def hamming_weight(n):
    """Count number of 1 bits. Time: O(number of set bits)"""
    count = 0
    while n:
        n &= n - 1   # Clear lowest set bit
        count += 1
    return count

print(hamming_weight(11))   # 3  (1011 → 3 ones)
print(hamming_weight(128))  # 1  (10000000)
      Python

      Problem 3: Power of Two

      def is_power_of_two(n):
    """Time: O(1)"""
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(1))    # True
print(is_power_of_two(16))   # True
print(is_power_of_two(3))    # False
      Python

      Problem 4: Reverse Bits

      def reverse_bits(n):
    """Reverse 32-bit unsigned integer. Time: O(1)"""
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

print(reverse_bits(0b00000010100101000001111010011100))
# 0b00111001011110000010100101000000 = 964176192
      Python

      Problem 5: Missing Number (XOR)

      def missing_number(nums):
    """
    Find missing number in [0, n]. Time: O(n)    Space: O(1)
    XOR all indices and all values — pairs cancel, leaving missing index.
    """
    xor = len(nums)
    for i, num in enumerate(nums):
        xor ^= i ^ num
    return xor

print(missing_number([3, 0, 1]))   # 2
print(missing_number([9,6,4,2,3,5,7,0,1]))  # 8
      Python

      Problem 6: Sum of Two Integers Without Arithmetic Operators

      def get_sum(a, b):
    """
    Add without + or -. Time: O(1) (32-bit integers)
    XOR gives sum without carry; AND shifted left gives carry.
    Repeat until no carry.
    """
    MASK = 0xFFFFFFFF   # 32-bit mask
    MAX  = 0x7FFFFFFF   # Max positive 32-bit int

    while b & MASK:
        carry = (a & b) << 1
        a = a ^ b
        b = carry

    # Handle negative numbers in Python's arbitrary precision ints
    return a if a <= MAX else ~(a ^ MASK)

print(get_sum(1, 2))    # 3
print(get_sum(-2, 3))   # 1
      Python

      Pattern Selection Guide

      Quick Pattern Lookup by Problem Type

      Problem DescriptionPattern(s)
      Sorted array, find pair with target sumTwo Pointers
      Longest/shortest subarray with property XSliding Window
      Subarray sum = KPrefix Sum + Hash Map
      Detect cycle in linked listFast & Slow Pointers
      Search in sorted arrayBinary Search
      Find minimum satisfying a constraintBinary Search on Answer
      Overlapping intervalsMerge Intervals
      Reverse part of linked listIn-Place Reversal
      Shortest path in unweighted graph/gridBFS
      All paths / connected componentsDFS / Backtracking
      Level-by-level tree processingTree BFS
      Path sum / tree propertiesTree DFS
      All combinations / permutationsBacktracking
      Min/max of subproblem (count ways, feasibility)Dynamic Programming
      Next greater/smaller elementMonotonic Stack
      Histogram / rain waterMonotonic Stack
      Top-K / Kth largest-smallestHeap (Top K Elements)
      Merge K sorted sequencesK-Way Merge (Heap)
      Connected components / union detectionUnion Find
      Prefix matching / autocompleteTrie
      XOR, single element, bit countingBit Manipulation
      Median of streamTwo Heaps

      Decision Flowchart

      Is input sorted?
├── YES → Binary Search or Two Pointers
└── NO  → Is it a subarray/substring problem?
          ├── YES → Sliding Window (or Prefix Sum if sum-based)
          └── NO  → Is it a tree?
                    ├── YES → BFS (levels/shortest) or DFS (paths/properties)
                    └── NO  → Is it a graph?
                              ├── YES → BFS/DFS/Union-Find/Topological Sort
                              └── NO  → Combinations/permutations?
                                        ├── YES → Backtracking
                                        └── NO  → Optimization/counting?
                                                  └── YES → Dynamic Programming
      Python

      Time Complexity Summary by Pattern

      PatternTimeSpaceKey Data Structure
      Two PointersO(n)O(1)Two indices
      Sliding WindowO(n)O(k)HashMap, Deque
      Fast & Slow PointersO(n)O(1)Two pointers
      Binary SearchO(log n)O(1)Indices
      Prefix SumO(n)O(n)Array, HashMap
      Merge IntervalsO(n log n)O(n)Sort + Stack
      In-Place LL ReversalO(n)O(1)Three pointers
      Tree BFSO(n)O(n)Queue
      Tree DFSO(n)O(h)Call stack
      BacktrackingO(b^d)O(d)Call stack
      Dynamic ProgrammingO(n²)–O(nW)O(n)–O(nW)1D/2D array
      Monotonic StackO(n)O(n)Stack
      Top K ElementsO(n log k)O(k)Min/Max Heap
      K-Way MergeO(n log k)O(k)Min Heap
      Graph BFS/DFSO(V+E)O(V)Queue/Stack + Set
      Union FindO(α(n))O(n)Parent array
      TrieO(L)O(ALPHABET×L×N)Tree of hashmaps
      Bit ManipulationO(1)–O(n)O(1)Integer bits

      Practice Problems by Pattern

      Two Pointers

      ProblemDifficultyKey Insight
      Two Sum IIEasySorted → move toward target
      Valid PalindromeEasySkip non-alphanumeric
      Three SumMediumSort + two pointers inner loop
      Container with Most WaterMediumAlways move shorter height
      Trapping Rain WaterHardmin(max_left, max_right) – height

      Sliding Window

      ProblemDifficultyKey Insight
      Max Sum Subarray of Size KEasyFixed window
      Longest Substring No RepeatMediumchar → last index map
      Minimum Window SubstringHardformed count + shrink
      Permutation in StringMediumFixed window, Counter compare

      Binary Search

      ProblemDifficultyKey Insight
      Binary SearchEasyClassic template
      Search in Rotated Sorted ArrayMediumOne half always sorted
      Find Peak ElementMediumMove toward larger neighbor
      Koko Eating BananasMediumBinary search on answer
      Median of Two Sorted ArraysHardBinary search on shorter array

      Dynamic Programming

      ProblemDifficultySubproblem Type
      Climbing StairsEasy1D linear
      House RobberMedium1D linear
      Longest Common SubsequenceMedium2D string
      Coin ChangeMedium1D knapsack
      Edit DistanceHard2D string
      Burst BalloonsHardInterval DP

      Graph

      ProblemDifficultyAlgorithm
      Number of IslandsMediumDFS flood fill
      Clone GraphMediumBFS + HashMap
      Course ScheduleMediumTopo sort (Kahn’s)
      Redundant ConnectionMediumUnion Find
      Word LadderHardBFS (shortest path)
      Alien DictionaryHardTopo sort

      Quick Reference Cheatsheet

      # ─── Two Pointers ─────────────────────────────────────────────
left, right = 0, len(arr) - 1
while left < right: ...

# ─── Sliding Window (Variable) ────────────────────────────────
window = {}; left = 0
for right in range(len(s)):
    window[s[right]] += 1
    while invalid(window): window[s[left]] -= 1; left += 1
    update_result(right - left + 1)

# ─── Binary Search (Answer) ───────────────────────────────────
lo, hi = min_val, max_val
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid
    else:             lo = mid + 1

# ─── Prefix Sum + Map ─────────────────────────────────────────
prefix = 0; seen = {0: 1}
for num in nums:
    prefix += num
    count += seen.get(prefix - k, 0)
    seen[prefix] = seen.get(prefix, 0) + 1

# ─── BFS ──────────────────────────────────────────────────────
from collections import deque
q = deque([start]); visited = {start}
while q:
    node = q.popleft(); ...
    for nb in graph[node]:
        if nb not in visited: visited.add(nb); q.append(nb)

# ─── Backtracking ─────────────────────────────────────────────
def backtrack(start, path):
    result.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)
        path.pop()

# ─── Union Find ───────────────────────────────────────────────
parent = list(range(n))
def find(x): parent[x] = find(parent[x]) if parent[x] != x else x; return parent[x]
def union(x, y): parent[find(x)] = find(y)

# ─── Monotonic Stack (Next Greater) ───────────────────────────
stack = []; result = [-1] * n
for i in range(n):
    while stack and nums[stack[-1]] < nums[i]:
        result[stack.pop()] = nums[i]
    stack.append(i)

# ─── Top-K (Min-Heap of size k) ───────────────────────────────
import heapq
heap = nums[:k]; heapq.heapify(heap)
for num in nums[k:]:
    if num > heap[0]: heapq.heapreplace(heap, num)
      Python

      Discover more from Altgr Blog

      Subscribe to get the latest posts sent to your email.

      Related Posts

      Leave a Reply

      Your email address will not be published. Required fields are marked *