LeetCode Patterns & Solutions

Problem 1: Two Sum (Easy)

LeetCode #1

Problem: Given an array of integers nums and an integer target, return indices of the two numbers that add up to target.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

❌ Brute Force (Don't Do This)

def twoSum(nums, target):
    """Time: O(n²), Space: O(1)"""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    # Two nested loops = O(n²) - too slow!

✅ Optimal Solution: Hash Map

def twoSum(nums, target):
    """
    How it works:
    1. Create empty hash map: {value: index}
    2. For each number:
       - Calculate complement = target - current_number
       - If complement exists in map: Found it! Return indices
       - Else: Add current number to map
    3. By the time we see the second number, first is already in map

    Example walkthrough: nums = [2, 7, 11, 15], target = 9

    i=0, num=2: complement=7, map={}, 7 not in map, add 2 → map={2: 0}
    i=1, num=7: complement=2, map={2: 0}, 2 IS in map! Return [0, 1]

    Time: O(n) - single pass
    Space: O(n) - hash map stores up to n elements
    """
    seen = {}  # {value: index}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return []  # No solution found

Problem 2: Contains Duplicate (Easy)

LeetCode #217

Problem: Return true if any value appears at least twice in the array.

✅ Solution: Hash Set

def containsDuplicate(nums):
    """
    Approach 1: Convert to set and compare sizes

    Time: O(n) - iterate once to build set
    Space: O(n) - set stores unique elements
    """
    return len(set(nums)) != len(nums)


def containsDuplicate_early_return(nums):
    """
    Approach 2: Check while iterating (better for early duplicates)

    How it works:
    - Add each element to set
    - If element already in set: duplicate found, return True
    - If we finish loop: no duplicates, return False

    Example: [1, 2, 3, 1]
    seen={}, add 1 → seen={1}
    seen={1}, add 2 → seen={1,2}
    seen={1,2}, add 3 → seen={1,2,3}
    seen={1,2,3}, try add 1 → 1 already in seen! Return True
    """
    seen = set()

    for num in nums:
        if num in seen:
            return True  # Found duplicate!
        seen.add(num)

    return False  # No duplicates

def containsDuplicate_no_extra_space(nums):
    """
    Sort the array, then check adjacent elements

    Why it works: Duplicates will be next to each other after sorting

    Time: O(n log n) - sorting
    Space: O(1) or O(n) depending on sort algorithm
    """
    nums.sort()

    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True

    return False

Problem 3: Valid Palindrome (Easy)

LeetCode #125

Problem: Given a string, return true if it's a palindrome (same forwards and backwards), considering only alphanumeric characters and ignoring cases.

def isPalindrome(s):
    """
    Two-pointer approach

    How it works:
    1. Left pointer starts at beginning, right at end
    2. Skip non-alphanumeric characters
    3. Compare characters (case-insensitive)
    4. If mismatch: not a palindrome
    5. If pointers meet: palindrome!

    Example: "A man, a plan, a canal: Panama"
    Clean: "amanaplanacanalpanama"
    Compare: a==a, m==m, a==a, ... (palindrome!)

    Time: O(n) - single pass with two pointers
    Space: O(1) - no extra data structures
    """
    left, right = 0, len(s) - 1

    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1

        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1

        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

Problem 4: Container With Most Water (Medium)

LeetCode #11

Problem: Given array of heights, find two lines that form container with most water.

def maxArea(height):
    """
    Two-pointer greedy approach

    How it works:
    1. Start with widest container (left=0, right=n-1)
    2. Calculate area = min(height[left], height[right]) × (right - left)
    3. Move pointer with SHORTER height (potential to find taller)
    4. Track maximum area seen

    Why this is optimal:
    - We start with maximum width
    - Moving shorter line is only way to potentially increase area
    - Moving taller line would decrease both height AND width

    Example: height = [1,8,6,2,5,4,8,3,7]
                      L                 R
    Area = min(1,7) × 8 = 8
    Move left (shorter): L at index 1
                         L           R
    Area = min(8,7) × 7 = 49 (better!)
    Move right (shorter): R at index 7
                         L       R
    Area = min(8,8) × 6 = 48
    Move right: R at index 6
                         L     R
    Area = min(8,3) × 5 = 15
    ... continue until pointers meet

    Maximum area = 49

    Time: O(n) - single pass
    Space: O(1) - only two pointers
    """
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # Calculate current area
        width = right - left
        current_area = min(height[left], height[right]) * width
        max_area = max(max_area, current_area)

        # Move pointer with shorter height
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

Problem 5: Best Time to Buy and Sell Stock (Easy)

LeetCode #121

Problem: Find maximum profit from buying and selling stock once. Buy before sell.

def maxProfit(prices):
    """
    Single pass with running minimum

    How it works:
    1. Track minimum price seen so far (best buy price)
    2. For each price:
       - Calculate profit if we sell today (price - min_price)
       - Update maximum profit
       - Update minimum price

    Example: prices = [7, 1, 5, 3, 6, 4]

    Day 0: price=7, min=7, profit=0
    Day 1: price=1, min=1, profit=0 (can't make profit yet)
    Day 2: price=5, min=1, profit=4 (buy at 1, sell at 5)
    Day 3: price=3, min=1, profit=4 (not better)
    Day 4: price=6, min=1, profit=5 (buy at 1, sell at 6) ← best!
    Day 5: price=4, min=1, profit=5 (not better)

    Return 5

    Time: O(n) - single pass
    Space: O(1) - only two variables
    """
    if not prices:
        return 0

    min_price = prices[0]
    max_profit = 0

    for price in prices:
        # Update maximum profit if selling today
        max_profit = max(max_profit, price - min_price)

        # Update minimum price seen
        min_price = min(min_price, price)

    return max_profit

Problem 6: Longest Substring Without Repeating Characters (Medium)

LeetCode #3

Problem: Find length of longest substring without repeating characters.

def lengthOfLongestSubstring(s):
    """
    Sliding window with hash set

    How it works:
    1. Use set to track characters in current window
    2. Expand window by moving right pointer
    3. If duplicate: shrink window from left until no duplicate
    4. Track maximum window size

    Example: s = "abcabcbb"

    Window: "a" → set={a}, len=1
    Window: "ab" → set={a,b}, len=2
    Window: "abc" → set={a,b,c}, len=3
    Duplicate 'a': shrink left
    Window: "bca" → set={b,c,a}, len=3
    Duplicate 'b': shrink left twice
    Window: "cab" → set={c,a,b}, len=3
    ... continue

    Maximum length = 3

    Time: O(n) - each character visited at most twice (once by right, once by left)
    Space: O(min(n, m)) where m is charset size
    """
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Shrink window until no duplicate
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # Add current character
        char_set.add(s[right])

        # Update maximum length
        max_length = max(max_length, right - left + 1)

    return max_length

def lengthOfLongestSubstring_optimized(s):
    """
    Optimized with hash map tracking last seen index

    Improvement: Jump left pointer directly to last seen position + 1
    instead of incrementing one by one
    """
    last_seen = {}  # {char: last_index}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        # If char seen and in current window, jump left
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1

        last_seen[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

Problem 7: Valid Parentheses (Easy)

LeetCode #20

Problem: Given a string containing just characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. Opening brackets must be closed by the same type and in correct order.

def isValid(s):
    """
    Stack-based validation

    How it works:
    1. Push opening brackets onto stack
    2. When closing bracket found:
       - Check if stack empty (no matching open) → invalid
       - Pop from stack and verify it matches → if not, invalid
    3. After processing all chars, stack must be empty

    Example: s = "({[]})"

    char='(': stack=['(']
    char='{': stack=['(', '{']
    char='[': stack=['(', '{', '[']
    char=']': pop '[', matches! stack=['(', '{']
    char='}': pop '{', matches! stack=['(']
    char=')': pop '(', matches! stack=[]

    Stack empty → Valid!

    Counter-example: s = "([)]"
    char='(': stack=['(']
    char='[': stack=['(', '[']
    char=')': pop '[', doesn't match ')' → Invalid!

    Time: O(n) - single pass
    Space: O(n) - stack stores up to n/2 brackets
    """
    # Map closing to opening brackets
    bracket_map = {')': '(', '}': '{', ']': '['}
    stack = []

    for char in s:
        if char in bracket_map:  # Closing bracket
            # Check if stack empty or top doesn't match
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
        else:  # Opening bracket
            stack.append(char)

    # Valid only if all brackets closed
    return len(stack) == 0

Problem 8: Min Stack (Medium)

LeetCode #155

Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

class MinStack:
    """
    Two-stack approach

    How it works:
    - stack: stores actual values
    - min_stack: stores minimum value at each level
    - When pushing: add to both stacks (min_stack gets min of value and current min)
    - When popping: remove from both stacks
    - getMin: return top of min_stack (current minimum)

    Example operations:

    push(-2): stack=[-2], min_stack=[-2]
    push(0):  stack=[-2,0], min_stack=[-2,-2]  (min still -2)
    push(-3): stack=[-2,0,-3], min_stack=[-2,-2,-3]  (new min -3)
    getMin(): return -3
    pop():    stack=[-2,0], min_stack=[-2,-2]  (min back to -2)
    top():    return 0
    getMin(): return -2

    All operations: O(1) time
    Space: O(n) - two stacks
    """

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        # Push minimum value at this level
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

    def getMin(self) -> int:
        return self.min_stack[-1]

class MinStack_Optimized:
    """
    Store (value, min_at_this_level) pairs

    Uses one stack instead of two
    Space: O(n) but half the memory
    """

    def __init__(self):
        self.stack = []  # [(val, min)]

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = min(val, self.stack[-1][1])
            self.stack.append((val, current_min))

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

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

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

Problem 9: Binary Search (Easy)

LeetCode #704

Problem: Given a sorted array, search for a target value. Return index if found, else -1.

def search(nums, target):
    """
    Classic binary search

    How it works:
    1. Keep two pointers: left and right
    2. Calculate middle index
    3. If middle == target: found!
    4. If middle < target: search right half (left = mid + 1)
    5. If middle > target: search left half (right = mid - 1)
    6. Repeat until found or left > right

    Example: nums = [-1,0,3,5,9,12], target = 9

    Iteration 1: left=0, right=5, mid=2
                 nums[2]=3 < 9, search right half

    Iteration 2: left=3, right=5, mid=4
                 nums[4]=9 == 9, found at index 4!

    Why this eliminates half:
    - Sorted array means all elements left of mid are < mid
    - All elements right of mid are > mid
    - Safe to discard half

    Time: O(log n) - halve search space each step
    Space: O(1) - only pointers
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half

    return -1  # Not found

# Use this template for all binary search problems
def binary_search_template(nums, target):
    left, right = 0, len(nums) - 1

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

        if condition_met(nums[mid]):
            return mid  # Or save result and continue
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Problem 10: Search in Rotated Sorted Array (Medium)

LeetCode #33

Problem: Sorted array rotated at unknown pivot point. Find target in O(log n).

def search(nums, target):
    """
    Modified binary search for rotated array

    How it works:
    1. Find middle element
    2. Determine which half is sorted (left or right)
    3. Check if target is in the sorted half
    4. If yes: search that half
    5. If no: search the other half

    Example: nums = [4,5,6,7,0,1,2], target = 0

    Visual: [4,5,6,7 | 0,1,2]
             sorted   sorted
             (but rotated overall)

    Iteration 1: left=0, right=6, mid=3
                 nums[mid]=7
                 Left half [4,5,6,7] is sorted (4 <= 7)
                 Is target 0 in [4,7]? NO
                 Search right half

    Iteration 2: left=4, right=6, mid=5
                 nums[mid]=1
                 Right half [1,2] is sorted (1 <= 2)
                 Is target 0 in [1,2]? NO
                 Search left half

    Iteration 3: left=4, right=4, mid=4
                 nums[mid]=0 == target, found!

    Time: O(log n) - binary search
    Space: O(1)
    """
    left, right = 0, len(nums) - 1

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

        if nums[mid] == target:
            return mid

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

    return -1

Problem 11: Reverse Linked List (Easy)

LeetCode #206

Problem: Reverse a singly linked list.

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

def reverseList(head):
    """
    Iterative reversal with three pointers

    How it works:
    1. Keep three pointers: prev, current, next
    2. For each node:
       - Save next node (so we don't lose it)
       - Reverse current.next to point to prev
       - Move prev and current forward
    3. When current is None, prev is new head

    Visual example: 1 → 2 → 3 → 4 → None

    Step 1: prev=None, curr=1, next=2
            Reverse: None ← 1   2 → 3 → 4 → None

    Step 2: prev=1, curr=2, next=3
            Reverse: None ← 1 ← 2   3 → 4 → None

    Step 3: prev=2, curr=3, next=4
            Reverse: None ← 1 ← 2 ← 3   4 → None

    Step 4: prev=3, curr=4, next=None
            Reverse: None ← 1 ← 2 ← 3 ← 4

    Step 5: curr=None, return prev (which is 4)

    Time: O(n) - visit each node once
    Space: O(1) - only three pointers
    """
    prev = None
    current = head

    while current:
        # Save next node before we change pointer
        next_node = current.next

        # Reverse the pointer
        current.next = prev

        # Move prev and current forward
        prev = current
        current = next_node

    return prev  # New head

def reverseList_recursive(head):
    """
    Recursive reversal

    How it works:
    1. Base case: empty list or single node (already reversed)
    2. Recursively reverse rest of list
    3. Make next node point back to current
    4. Set current.next to None (avoid cycle)

    Visual: 1 → 2 → 3 → None

    Call reverseList(1):
      Call reverseList(2):
        Call reverseList(3):
          Return 3 (base case)
        Set 3.next = 2 (2.next.next = 2)
        Set 2.next = None
        Return 3
      Set 2.next = 1
      Set 1.next = None
      Return 3

    Result: None ← 1 ← 2 ← 3

    Time: O(n) - visit each node
    Space: O(n) - recursion stack
    """
    # Base case
    if not head or not head.next:
        return head

    # Reverse rest of list
    new_head = reverseList_recursive(head.next)

    # Make next node point back to current
    head.next.next = head
    head.next = None

    return new_head

Problem 12: Linked List Cycle (Easy)

LeetCode #141

Problem: Determine if linked list has a cycle.

def hasCycle(head):
    """
    Floyd's Cycle Detection Algorithm (Tortoise and Hare)

    How it works:
    1. Slow pointer moves 1 step at a time
    2. Fast pointer moves 2 steps at a time
    3. If they meet: cycle exists
    4. If fast reaches end (None): no cycle

    Why it works:
    - In a cycle, fast gains on slow by 1 position each step
    - Eventually they must meet (like runners on circular track)
    - If no cycle, fast reaches end in O(n) time

    Example with cycle: 1 → 2 → 3 → 4
                                ↑     ↓
                                └─────┘

    Step 0: slow=1, fast=1
    Step 1: slow=2, fast=3
    Step 2: slow=3, fast=2 (wrapped around)
    Step 3: slow=4, fast=4 (met! cycle detected)

    Time: O(n) - fast traverses at most 2n steps
    Space: O(1) - only two pointers
    """
    if not head or not head.next:
        return False

    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  # Reached end, no cycle

def detectCycle(head):
    """
    Find where cycle begins

    Mathematical proof:
    - When slow and fast meet, slow has traveled distance 'x'
    - Fast has traveled '2x' (moves twice as fast)
    - The difference 'x' is a multiple of cycle length
    - Distance from head to cycle start = distance from meeting point to cycle start

    Algorithm:
    1. Find meeting point with slow/fast
    2. Move one pointer to head
    3. Move both 1 step at a time
    4. Where they meet is cycle start!
    """
    if not head or not head.next:
        return None

    # Find meeting point
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle

    # Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # Cycle start

Problem 13: Maximum Depth of Binary Tree (Easy)

LeetCode #104

Problem: Find maximum depth (height) of binary tree.

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

def maxDepth(root):
    """
    Recursive DFS approach

    How it works:
    1. Base case: empty tree has depth 0
    2. Recursively find depth of left and right subtrees
    3. Return 1 (current level) + max of subtree depths

    Example tree:
            3
           / \
          9  20
            /  \
           15   7

    maxDepth(3):
      maxDepth(9) → 1 (leaf)
      maxDepth(20):
        maxDepth(15) → 1 (leaf)
        maxDepth(7) → 1 (leaf)
        return 1 + max(1, 1) = 2
      return 1 + max(1, 2) = 3

    Time: O(n) - visit each node once
    Space: O(h) - recursion stack depth (h = height)
           Best case: O(log n) for balanced tree
           Worst case: O(n) for skewed tree
    """
    if not root:
        return 0

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

    return 1 + max(left_depth, right_depth)

from collections import deque

def maxDepth_bfs(root):
    """
    BFS (level-order) approach

    Count number of levels in tree

    Time: O(n)
    Space: O(w) where w is maximum width of tree
    """
    if not root:
        return 0

    queue = deque([root])
    depth = 0

    while queue:
        depth += 1
        level_size = len(queue)

        # Process all nodes at current level
        for _ in range(level_size):
            node = queue.popleft()

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

    return depth

Problem 14: Validate Binary Search Tree (Medium)

LeetCode #98

Problem: Determine if a binary tree is a valid BST.

def isValidBST(root):
    """
    Recursive with valid range

    How it works:
    1. Each node has a valid range [min_val, max_val]
    2. Root can be any value: (-∞, +∞)
    3. Left child must be < parent: (min_val, parent.val)
    4. Right child must be > parent: (parent.val, max_val)

    Example: Tree that looks valid but ISN'T:
            5
           / \
          1   6
             / \
            3   7

    Node 3 is in right subtree of 5, so it must be > 5
    But 3 < 5, so this is NOT a valid BST!

    Our algorithm catches this:
    isValidBST(5, -∞, +∞):
      isValidBST(1, -∞, 5): OK
      isValidBST(6, 5, +∞):
        isValidBST(3, 5, 6): FAIL! (3 < 5) ✗

    Time: O(n) - visit each node
    Space: O(h) - recursion stack
    """
    def validate(node, min_val, max_val):
        if not node:
            return True

        # Check if current node violates BST property
        if node.val <= min_val or node.val >= max_val:
            return False

        # Check left subtree: all values must be < node.val
        # Check right subtree: all values must be > node.val
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

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

def isValidBST_inorder(root):
    """
    In-order traversal of BST produces sorted array

    If not sorted → not a BST!

    Time: O(n)
    Space: O(n) - store all values
    """
    values = []

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        values.append(node.val)
        inorder(node.right)

    inorder(root)

    # Check if sorted (no duplicates)
    return values == sorted(values) and len(values) == len(set(values))

Problem 15: Kth Largest Element in an Array (Medium)

LeetCode #215

Problem: Find the kth largest element in an unsorted array.

import heapq

def findKthLargest(nums, k):
    """
    Min-heap approach

    How it works:
    1. Maintain a min-heap of size k
    2. For each number:
       - Add to heap
       - If heap size > k: remove smallest (heap[0])
    3. After processing all nums, heap contains k largest elements
    4. Root (heap[0]) is kth largest!

    Example: nums = [3,2,1,5,6,4], k = 2

    num=3: heap=[3]
    num=2: heap=[2,3]
    num=1: heap=[1,2,3] → pop 1 → heap=[2,3]
    num=5: heap=[2,3,5] → pop 2 → heap=[3,5]
    num=6: heap=[3,5,6] → pop 3 → heap=[5,6]
    num=4: heap=[4,5,6] → pop 4 → heap=[5,6]

    Return heap[0] = 5 (2nd largest)

    Why this works:
    - Heap always has k largest elements seen so far
    - Min-heap ensures smallest of these k is at root
    - When we add larger element, we remove smallest
    - Final root = kth largest

    Time: O(n log k) - n insertions, each log k
    Space: O(k) - heap size
    """
    heap = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # Remove smallest

    return heap[0]  # kth largest

import random

def findKthLargest_quickselect(nums, k):
    """
    QuickSelect algorithm (similar to QuickSort)

    Convert "kth largest" to "nth smallest" where n = len(nums) - k

    Average time: O(n)
    Worst case: O(n²)
    Space: O(1)
    """
    def partition(left, right, pivot_idx):
        pivot = nums[pivot_idx]
        # Move pivot to end
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

        store_idx = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[i], nums[store_idx] = nums[store_idx], nums[i]
                store_idx += 1

        # Move pivot to final position
        nums[store_idx], nums[right] = nums[right], nums[store_idx]
        return store_idx

    def select(left, right, k_smallest):
        if left == right:
            return nums[left]

        # Random pivot for better average performance
        pivot_idx = random.randint(left, right)
        pivot_idx = partition(left, right, pivot_idx)

        if k_smallest == pivot_idx:
            return nums[k_smallest]
        elif k_smallest < pivot_idx:
            return select(left, pivot_idx - 1, k_smallest)
        else:
            return select(pivot_idx + 1, right, k_smallest)

    return select(0, len(nums) - 1, len(nums) - k)

Problem 16: Merge K Sorted Lists (Hard)

LeetCode #23

Problem: Merge k sorted linked lists into one sorted list.

import heapq

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

def mergeKLists(lists):
    """
    Min-heap approach

    How it works:
    1. Push first node from each list into heap (with value as priority)
    2. Pop minimum node from heap
    3. Add to result
    4. Push next node from same list to heap
    5. Repeat until heap empty

    Example: lists = [[1,4,5], [1,3,4], [2,6]]

    Initial heap: [(1,list0), (1,list1), (2,list2)]
    Pop (1,list0), push 4 → heap: [(1,list1), (2,list2), (4,list0)]
    Pop (1,list1), push 3 → heap: [(2,list2), (3,list1), (4,list0)]
    Pop (2,list2), push 6 → heap: [(3,list1), (4,list0), (6,list2)]
    ... continue

    Time: O(N log k) where N = total nodes, k = number of lists
          - N pops/pushes, each O(log k)
    Space: O(k) - heap size
    """
    heap = []
    dummy = ListNode(0)
    current = dummy

    # Add first node from each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    # Counter for unique ordering when values equal
    count = len(lists)

    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = node
        current = current.next

        if node.next:
            heapq.heappush(heap, (node.next.val, count, node.next))
            count += 1

    return dummy.next

Problem 17: Subsets (Medium)

LeetCode #78

Problem: Given an integer array nums of unique elements, return all possible subsets (the power set).

def subsets(nums):
    """
    Backtracking approach

    How it works:
    1. At each step, decide to include or exclude current element
    2. Recurse with remaining elements
    3. Add current combination to result

    Example: nums = [1,2,3]

    Decision tree:
                        []
                      /    \
              include 1    exclude 1
                [1]            []
              /    \          /    \
          [1,2]   [1]      [2]    []
          /  \    / \      / \    / \
      [1,2,3][1,2][1,3][1][2,3][2][3][]

    Result: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

    Time: O(2^n) - 2^n subsets, each takes O(n) to copy
    Space: O(n) - recursion depth
    """
    result = []

    def backtrack(index, current):
        # Base case: processed all elements
        if index == len(nums):
            result.append(current[:])  # Add copy of current subset
            return

        # Choice 1: Include nums[index]
        current.append(nums[index])
        backtrack(index + 1, current)
        current.pop()  # Backtrack

        # Choice 2: Exclude nums[index]
        backtrack(index + 1, current)

    backtrack(0, [])
    return result

def subsets_iterative(nums):
    """
    Iterative: Start with [[]], add each number to existing subsets

    How it works:
    - Start: [[]]
    - Add 1: [[], [1]]
    - Add 2: [[], [1], [2], [1,2]]
    - Add 3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

    Time: O(2^n)
    Space: O(1) excluding output
    """
    result = [[]]

    for num in nums:
        # Add num to all existing subsets
        result += [subset + [num] for subset in result]

    return result

def backtrack(choices, current_state):
    if is_solution(current_state):
        result.append(current_state)
        return

    for choice in choices:
        make_choice(choice)
        backtrack(remaining_choices, new_state)
        undo_choice(choice)  # Backtrack!

Problem 18: Permutations (Medium)

LeetCode #46

Problem: Given an array nums of distinct integers, return all possible permutations.

def permute(nums):
    """
    Backtracking with tracking which elements are used

    How it works:
    1. Try each unused element as next position
    2. Mark as used, recurse
    3. When permutation complete (length == n), add to result
    4. Backtrack: unmark and try next choice

    Example: nums = [1,2,3]

    Build [1, ?, ?]:
      Try [1,2,?]:
        Try [1,2,3] ✓ (complete)
      Try [1,3,?]:
        Try [1,3,2] ✓ (complete)
    Build [2, ?, ?]:
      ... and so on

    Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

    Time: O(n! × n) - n! permutations, each O(n) to build
    Space: O(n) - recursion depth
    """
    result = []

    def backtrack(current):
        # Base case: permutation complete
        if len(current) == len(nums):
            result.append(current[:])
            return

        for num in nums:
            if num in current:  # Already used
                continue

            # Make choice
            current.append(num)
            backtrack(current)
            current.pop()  # Backtrack

    backtrack([])
    return result

def permute_swap(nums):
    """
    In-place swapping approach

    Instead of tracking used elements, swap them to current position

    Time: O(n! × n)
    Space: O(n) - recursion only
    """
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return

        for i in range(start, len(nums)):
            # Swap to current position
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            # Swap back (backtrack)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

Problem 19: Number of Islands (Medium)

LeetCode #200

Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands.

def numIslands(grid):
    """
    DFS approach

    How it works:
    1. Scan grid for '1'
    2. When found: increment island count
    3. DFS to mark entire island as visited ('0')
    4. Continue scanning

    Example: grid = [
      ['1','1','0','0','0'],
      ['1','1','0','0','0'],
      ['0','0','1','0','0'],
      ['0','0','0','1','1']
    ]

    Find '1' at (0,0) → DFS marks (0,0), (0,1), (1,0), (1,1) → count=1
    Find '1' at (2,2) → DFS marks (2,2) → count=2
    Find '1' at (3,3) → DFS marks (3,3), (3,4) → count=3

    Return 3

    Time: O(m × n) - visit each cell once
    Space: O(m × n) - worst case recursion depth (all land)
    """
    if not grid:
        return 0

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

    def dfs(r, c):
        # Base cases: out of bounds or water
        if (r < 0 or r >= rows or
            c < 0 or c >= cols or
            grid[r][c] == '0'):
            return

        # Mark as visited
        grid[r][c] = '0'

        # Explore all 4 directions
        dfs(r + 1, c)  # Down
        dfs(r - 1, c)  # Up
        dfs(r, c + 1)  # Right
        dfs(r, c - 1)  # Left

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1
                dfs(r, c)  # Mark entire island

    return islands

from collections import deque

def numIslands_bfs(grid):
    """
    BFS approach - explores level by level

    Same logic, different traversal order
    """
    if not grid:
        return 0

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

    def bfs(r, c):
        queue = deque([(r, c)])
        grid[r][c] = '0'

        while queue:
            row, col = queue.popleft()
            directions = [(1,0), (-1,0), (0,1), (0,-1)]

            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                    grid[nr][nc] == '1'):
                    grid[nr][nc] = '0'
                    queue.append((nr, nc))

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

    return islands

Problem 20: Course Schedule (Medium)

LeetCode #207

Problem: Given numCourses and prerequisites (pairs [a,b] meaning course a requires course b), determine if you can finish all courses.

def canFinish(numCourses, prerequisites):
    """
    Topological sort with cycle detection (DFS)

    How it works:
    1. Build adjacency list (course → prerequisites)
    2. Use DFS to detect cycles
    3. Track visit states:
       - Not visited (0)
       - Visiting (1) - in current DFS path
       - Visited (2) - completely processed
    4. If we see a "visiting" node again → cycle!

    Example: numCourses=2, prerequisites=[[1,0]]
    Means: course 1 requires course 0
    Graph: 0 → 1
    No cycle → return True

    Example: prerequisites=[[1,0],[0,1]]
    Graph: 0 ⇄ 1 (cycle!)
    Cycle detected → return False

    Time: O(V + E) - visit each node and edge once
    Space: O(V + E) - adjacency list and recursion
    """
    # Build adjacency list
    graph = {i: [] for i in range(numCourses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    # 0 = not visited, 1 = visiting, 2 = visited
    visit_state = [0] * numCourses

    def has_cycle(course):
        if visit_state[course] == 1:
            return True  # Cycle detected!
        if visit_state[course] == 2:
            return False  # Already processed

        # Mark as visiting
        visit_state[course] = 1

        # Check all prerequisites
        for prereq in graph[course]:
            if has_cycle(prereq):
                return True

        # Mark as visited
        visit_state[course] = 2
        return False

    # Check each course
    for course in range(numCourses):
        if has_cycle(course):
            return False

    return True

Problem 21: Climbing Stairs (Easy)

LeetCode #70

Problem: You can climb 1 or 2 steps at a time. How many distinct ways to reach top of n-step staircase?

def climbStairs(n):
    """
    Dynamic Programming (Fibonacci)

    How it works:
    - Base cases: ways(1) = 1, ways(2) = 2
    - For each step, add ways from previous two steps

    Example: n = 5
    Step 1: 1 way (1)
    Step 2: 2 ways (1+1, 2)
    Step 3: 3 ways (1+1+1, 1+2, 2+1)
    Step 4: 5 ways (sum of step 2 and 3)
    Step 5: 8 ways (sum of step 3 and 4)

    Time: O(n)
    Space: O(1) - only store last two values
    """
    if n <= 2:
        return n

    # Only need last two values
    prev2 = 1  # ways(1)
    prev1 = 2  # ways(2)

    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

Problem 22: House Robber (Medium)

LeetCode #198

Problem: You're a robber planning to rob houses along a street. Adjacent houses have security that alerts police if broken into on same night. Given array of money in each house, return maximum amount you can rob.

def rob(nums):
    """
    Dynamic Programming

    How it works:
    For each house, we have 2 choices:
    1. Rob it: get nums[i] + dp[i-2] (can't rob i-1)
    2. Skip it: get dp[i-1] (max from previous)

    Example: nums = [2,7,9,3,1]

    House 0: rob 2, max=2
    House 1: rob 7 (better than 2), max=7
    House 2: rob 9+2=11 (better than 7), max=11
    House 3: rob 3+7=10 (not better than 11), max=11
    House 4: rob 1+11=12 (better than 11), max=12

    Return 12

    Time: O(n)
    Space: O(1) - only need last two values
    """
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    # Only need last two values
    prev2 = nums[0]  # Max from i-2
    prev1 = max(nums[0], nums[1])  # Max from i-1

    for i in range(2, len(nums)):
        # Rob current + prev2 OR skip current + prev1
        current = max(nums[i] + prev2, prev1)
        prev2 = prev1
        prev1 = current

    return prev1

Problem 23: Coin Change (Medium)

LeetCode #322

Problem: Given coins of different denominations and a total amount, return fewest coins needed to make up that amount.

def coinChange(coins, amount):
    """
    Bottom-up DP

    How it works:
    1. dp[i] = minimum coins needed to make amount i
    2. Base case: dp[0] = 0 (0 coins for amount 0)
    3. For each amount from 1 to target:
       - Try each coin
       - If coin <= amount: dp[amount] = min(dp[amount], 1 + dp[amount-coin])

    Example: coins = [1,2,5], amount = 11

    dp[0] = 0
    dp[1] = 1 (use coin 1)
    dp[2] = 1 (use coin 2)
    dp[3] = 2 (coin 2 + coin 1)
    dp[4] = 2 (coin 2 + coin 2)
    dp[5] = 1 (use coin 5)
    dp[6] = 2 (coin 5 + coin 1)
    dp[7] = 2 (coin 5 + coin 2)
    ...
    dp[11] = 3 (coin 5 + coin 5 + coin 1)

    Time: O(amount × coins) - nested loops
    Space: O(amount) - dp array
    """
    # Initialize with amount+1 (impossible value)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

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

    return dp[amount] if dp[amount] != amount + 1 else -1

Problem 24: Longest Increasing Subsequence (Medium)

LeetCode #300

Problem: Find length of longest strictly increasing subsequence.

def lengthOfLIS(nums):
    """
    DP approach

    dp[i] = length of LIS ending at index i

    Time: O(n²)
    Space: O(n)
    """
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Problem 25: Jump Game (Medium)

LeetCode #55

Problem: Given array where nums[i] is max jump length at position i, determine if you can reach last index.

def canJump(nums):
    """
    Greedy approach

    How it works:
    1. Track maximum index we can reach
    2. For each position, update max reachable
    3. If current position > max reachable: stuck!
    4. If max reachable >= last index: success!

    Example: nums = [2,3,1,1,4]

    i=0: max_reach = max(0, 0+2) = 2
    i=1: max_reach = max(2, 1+3) = 4
    i=2: max_reach = max(4, 2+1) = 4
    ... max_reach=4 >= last_index=4 ✓

    Example: nums = [3,2,1,0,4]
    i=0: max_reach = 3
    i=1: max_reach = 3
    i=2: max_reach = 3
    i=3: max_reach = 3
    i=4: current=4 > max_reach=3, stuck! ✗

    Time: O(n)
    Space: O(1)
    """
    max_reach = 0

    for i in range(len(nums)):
        if i > max_reach:
            return False  # Can't reach here

        max_reach = max(max_reach, i + nums[i])

        if max_reach >= len(nums) - 1:
            return True

    return True

Problem 26: Merge Intervals (Medium)

LeetCode #56

Problem: Given array of intervals, merge all overlapping intervals.

def merge(intervals):
    """
    Sort and merge approach

    How it works:
    1. Sort intervals by start time
    2. For each interval:
       - If overlaps with last merged: extend end
       - Else: add as new interval

    Example: intervals = [[1,3],[2,6],[8,10],[15,18]]

    Sort: [[1,3],[2,6],[8,10],[15,18]] (already sorted)

    Process [1,3]: merged = [[1,3]]
    Process [2,6]: 2 <= 3, overlap! Merge to [1,6]
                   merged = [[1,6]]
    Process [8,10]: 8 > 6, no overlap
                    merged = [[1,6],[8,10]]
    Process [15,18]: 15 > 10, no overlap
                     merged = [[1,6],[8,10],[15,18]]

    Time: O(n log n) - sorting
    Space: O(n) - output
    """
    if not intervals:
        return []

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

    merged = [intervals[0]]

    for current in intervals[1:]:
        last = merged[-1]

        # Check if overlaps
        if current[0] <= last[1]:
            # Merge by extending end
            last[1] = max(last[1], current[1])
        else:
            # No overlap, add new interval
            merged.append(current)

    return merged

Problem 27: Insert Interval (Medium)

LeetCode #57

Problem: Given sorted non-overlapping intervals and a new interval, insert and merge if necessary.

def insert(intervals, newInterval):
    """
    Three-phase approach

    Phase 1: Add all intervals ending before newInterval starts
    Phase 2: Merge all overlapping intervals with newInterval
    Phase 3: Add all intervals starting after newInterval ends

    Example: intervals = [[1,3],[6,9]], newInterval = [2,5]

    Phase 1: [1,3] ends at 3, 3 >= 2 (newInterval start), overlaps!
    Phase 2: Merge [1,3] and [2,5] → [1,5]
    Phase 3: Add [6,9]

    Result: [[1,5],[6,9]]

    Time: O(n)
    Space: O(n)
    """
    result = []
    i = 0
    n = len(intervals)

    # Phase 1: Add intervals before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

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

    # Phase 3: Add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Problem 28: Implement Trie (Medium)

LeetCode #208

Problem: Implement a trie with insert, search, and startsWith operations.

class TrieNode:
    def __init__(self):
        self.children = {}  # {char: TrieNode}
        self.is_end_of_word = False

class Trie:
    """
    Trie data structure

    Structure example after inserting "cat", "car", "dog":

                root
               /    \
              c      d
              |      |
              a      o
             / \     |
            t   r    g
            *   *    *
    (* marks end of word)

    Time complexities:
    - insert(word): O(len(word))
    - search(word): O(len(word))
    - startsWith(prefix): O(len(prefix))

    Space: O(total characters in all words)
    """

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

    def insert(self, word: str) -> None:
        """Insert word into trie"""
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]

        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Return if word is in trie"""
        node = self.root

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

        return node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        """Return if there's any word with given prefix"""
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]

        return True

Problem 29: Single Number (Easy)

LeetCode #136

Problem: Given array where every element appears twice except one, find the single one. Must be O(n) time and O(1) space.

def singleNumber(nums):
    """
    XOR approach

    How it works:
    XOR properties:
    - x ^ x = 0 (same numbers cancel)
    - x ^ 0 = x (zero is identity)
    - Associative and commutative

    Example: nums = [4,1,2,1,2]

    4 ^ 1 ^ 2 ^ 1 ^ 2
    = 4 ^ (1 ^ 1) ^ (2 ^ 2)
    = 4 ^ 0 ^ 0
    = 4

    All duplicates cancel out, leaving single number!

    Time: O(n)
    Space: O(1)
    """
    result = 0
    for num in nums:
        result ^= num
    return result

# Check if bit i is set
def is_bit_set(num, i):
    return (num & (1 << i)) != 0

# Set bit i
def set_bit(num, i):
    return num | (1 << i)

# Clear bit i
def clear_bit(num, i):
    return num & ~(1 << i)

# Toggle bit i
def toggle_bit(num, i):
    return num ^ (1 << i)

# Check if power of 2
def is_power_of_2(num):
    return num > 0 and (num & (num - 1)) == 0

# Count set bits (Brian Kernighan's algorithm)
def count_bits(num):
    count = 0
    while num:
        num &= (num - 1)  # Remove rightmost 1
        count += 1
    return count

Problem 30: Number of 1 Bits (Easy)

LeetCode #191

Problem: Count the number of 1 bits in binary representation.

def hammingWeight(n):
    """
    Brian Kernighan's algorithm

    How it works:
    n & (n-1) clears rightmost 1 bit

    Example: n = 11 (binary: 1011)

    Iteration 1: 1011 & 1010 = 1010 (removed rightmost 1)
    Iteration 2: 1010 & 1001 = 1000
    Iteration 3: 1000 & 0111 = 0000

    Count = 3 iterations = 3 ones

    Time: O(number of 1 bits)
    Space: O(1)
    """
    count = 0
    while n:
        n &= (n - 1)  # Remove rightmost 1
        count += 1
    return count