Summary
Highlights
Sets are collections of unique values, without any particular order. They offer constant time (O(1)) on average for checking existence, making them invaluable for tasks like finding duplicates, checking membership, or managing unique elements in a sliding window. Sets are preferred over lists when uniqueness and fast existence checks are primary concerns, not for key-value storage.
This course covers essential data structures and algorithms for coding interviews and foundational programming skills, taught by Sheldon Chai. It will explain data structures like arrays, strings, sets, hashmaps, and heaps, along with algorithmic patterns such as two pointers, sliding windows, binary search, BFS, DFS, and backtracking, using clear examples and real interview problems.
Arrays are the default data structure for ordered, linear data, providing constant time (O(1)) access by index due to contiguous memory storage. However, insertion or deletion in the middle of an array is an O(N) operation because elements need to be shifted. Arrays are constantly used in problems requiring traversal, specific index access, comparing elements from ends, sliding windows, and prefix sums, offering leverage for clever solutions.
Strings are essentially arrays of characters, but they are often immutable in most languages. Modifying a string typically creates a new one, leading to O(N^2) complexity if concatenated in a loop. A better approach is to build a list of characters and then join them into a string (O(N) complexity). String problems frequently involve patterns like sliding windows or two pointers for efficient traversal and lookups.
Proficiency in basic loops and control flow is fundamental, as most interview problems boil down to iterating, applying conditions, and updating variables. It's crucial to correctly update loop pointers and understand the loop's purpose. A key habit is to mentally walk through code with example inputs to catch bugs and build intuition, especially for complex data structures and algorithms.
Big O notation measures how a program's performance scales with input size. Key complexities include O(1) (constant time, like array index access), O(log N) (logarithmic time, like binary search), O(N) (linear time, like single loops), O(N log N) (common for sorting), and O(N^2) (often from nested loops, usually too slow for large inputs). A general rule: for inputs up to 10^5, aim for O(N log N) or better; for up to 10^4, O(N^2) might be acceptable.
Hashmaps (dictionaries) store data as key-value pairs, providing average O(1) time for lookup and insertion. They use a hash function to map keys to memory locations. While collisions can occur, built-in implementations handle them. Keys must be hashable (e.g., numbers, strings, tuples), while mutable types like lists and dictionaries are not. Hashmaps are crucial for optimizing brute-force solutions by remembering answers, often used to create frequency maps or optimize problems from O(N^2) to O(N).
The Two Sum problem, finding two numbers in an array that add up to a target, is efficiently solved using a hashmap. Initialize an empty hashmap (num_to_index). Iterate through the array; for each number, calculate its complement. If the complement is in the hashmap, return its index and the current index. Otherwise, store the current number and its index in the hashmap. This approach achieves O(N) time complexity and O(N) space complexity.
The Two Pointers pattern uses two indices to traverse linear structures (arrays, strings, linked lists) to avoid nested loops and repeated scanning. There are two main types: both pointers moving in the same direction (e.g., fast and slow pointers for detecting cycles or finding the middle) or pointers moving towards each other from opposite ends (common for sorted arrays, palindromes, or reducing O(N^2) to O(N) by eliminating possibilities).
To check if a string is a valid palindrome (ignoring non-alphanumeric characters and case), use two pointers. Initialize a left pointer at the start and a right pointer at the end. While left < right, move left forward past non-alphanumeric chars, and right backward past non-alphanumeric chars. Compare the lowercase characters at left and right. If they don't match, return false. If they match, move both pointers inward. If the loop completes, return true. This scans each character at most once, with O(1) extra space.
To find the middle node of a linked list, use the fast and slow two-pointer technique. Initialize both pointers to the head. In a loop, move the fast pointer two steps forward and the slow pointer one step forward. When the fast pointer reaches the end of the list (or null), the slow pointer will be at the middle. This works in a single pass, without extra space, and handles both odd and even length lists.
The Sliding Window pattern is an extension of two pointers, managing a contiguous range (window) across a data structure to process segments efficiently. It avoids re-traversing data, enabling O(N) time complexity. It applies to problems involving contiguous substrings, subarrays, or consecutive elements. There are fixed-size and dynamic-size windows.
Fixed-size sliding windows are used when the problem specifies a window length (K). The window size remains constant: one element is added from the right, and one old element is removed from the left. This pattern is ideal for problems like finding the max average of a subarray of size K. The template involves initializing the first window, then looping, updating the sum/value by subtracting the leftmost element and adding the new rightmost element, and updating the result.
Dynamic-size sliding windows are used when the window size isn't fixed, aiming to find optimal ranges satisfying a condition (e.g., longest substring without repeating characters). The window expands from the right until a condition is violated, then shrinks from the left until it becomes valid again. This gives precise control over maintaining desired conditions, such as uniqueness or sum constraints.
To find the largest sum of any subarray of length K, a fixed-size sliding window is used. Calculate the sum of the first K elements as the initial window sum and largest sum. Then, iterate from K to the end of the array. For each step, subtract the element leaving the window (nums[right-k]) and add the new element entering (nums[right]). Update the largest sum if the current window sum is greater. This achieves O(N) time complexity.
To find the length of the longest substring without repeating characters, a dynamic sliding window is ideal. Use a left pointer (L) and a right pointer (R), and a frequency counter (hashmap) for characters in the window. Expand the window by moving R forward, incrementing the character count. If a character count exceeds 1 (duplicate), shrink the window from the left (move L forward, decrement count) until uniqueness is restored. Update the maximum length (R - L + 1) at each valid window. This is also O(N) time complexity.
For graphs, DFS needs a 'visited' set to handle cycles. Define a recursive function taking a node and the 'visited' set. Mark the current node as visited. Process the node. For each neighbor, if it's not in the 'visited' set, recursively call DFS on that neighbor. This ensures each node is visited once and prevents infinite recursion. Useful for graph coloring, state exploration, and puzzles.
Binary search is highly efficient (O(log N) time) for finding an element in a sorted array by repeatedly halving the search space. Its power extends beyond simple numerical lookup to any problem with a 'monotonic condition' – where a condition changes in only one direction (e.g., true/false boundary). The core idea is to find a midpoint, check a condition, and then eliminate half of the remaining search space based on the result. There are two main templates: vanilla (direct search in sorted array) and generalized (finding a boundary in a monotonic condition).
The vanilla binary search template finds a target in a sorted array. It initializes left and right pointers to define the search range. In a loop (while left <= right), it calculates the middle index. If the middle element equals the target, return its index. If mid_val < target, move left = mid + 1. If mid_val > target, move right = mid - 1. If the loop finishes without finding the target, return -1. This process effectively halves the search space in each iteration.
Binary search can be applied to problems with a 'monotonic condition' where a property changes unidirectionally (e.g., false to true). This template involves left/right pointers and a 'best_answer' variable. At each midpoint, a custom feasibility function checks if the index satisfies the condition. If true, it's a potential answer, so store it and search left (right = mid - 1) for an earlier valid point. If false, search right (left = mid + 1). This finds the first index where the condition becomes true in O(log N) time.
Given a sorted array of booleans (all falses then all trues), find the first index that is true. This is a monotonic condition. Apply the generalized binary search: initialize left, right, and best_answer. At the midpoint, if the value is true, store mid as a potential answer and try searching in the left half (right = mid - 1). If false, search in the right half (left = mid + 1). Return the best_answer.
Find the minimum element in a sorted array that has been rotated. The array has a structure: increasing values, a sharp drop (the pivot/minimum), then increasing values again. This presents a monotonic condition: numbers before the minimum are > than the last element, and numbers from the minimum onwards are <= than the last. Use generalized binary search: compare the mid element with the last element. If mid_val <= last_element, it could be the minimum, so store it and search left. Otherwise, search right. This finds the minimum in O(log N).
BFS explores structures level by level using a Queue (FIFO). It finds shortest paths in unweighted graphs or trees, processes structures in level order, and guarantees exploration of everything evenly. BFS has distinct implementations for trees (no cycles, no 'visited' set needed) and graphs (cycles possible, requiring a 'visited' set to prevent infinite loops and redundant work). The 'visited' set marks nodes when they are enqueued, not when processed.
For trees (no cycles), BFS simplifies. Initialize a queue with the root. While the queue is not empty, dequeue a node. Process the node (e.g., check for target, add to result list). Enqueue its children. This template ensures level-order processing and is used for finding shortest paths, understanding depth, or performing level-based logic in tree structures.
For graphs (potential cycles), BFS requires a 'visited' set. Initialize a queue with the source node and add the source to the 'visited' set. While the queue is not empty, dequeue the current node. For each neighbor, if it hasn't been visited, mark it as visited and enqueue it. This prevents infinite loops and ensures each node is processed once. Useful for grid problems, network traversal, and shortest-path problems where all edges have equal cost.
To perform a level order traversal of a binary tree, BFS is the perfect tool. Initialize a queue (e.g., Python's deque) with the root node and a result list. While the queue is not empty, get the current level's size. Create a list for the current level's values. Loop 'size' times: dequeue a node, add its value to the current level's list, and enqueue its left and right children if they exist. Append the current level's list to the result. Return the result. This processes the tree level by level, left to right.
The Flood Fill problem, changing the color of a pixel and all connected same-colored pixels, uses BFS on a grid. Start at the given (r, c) pixel. Initialize a queue and a 'visited' grid. Enqueue (r, c) and mark it visited. Get the original color and immediately change (r, c) to the new color. While the queue is not empty, dequeue a pixel. Find its valid (in-bounds, same-original-color) neighbors. For each unvisited neighbor, change its color, mark visited, and enqueue it. This propagates the color change outward in layers.
DFS explores a tree or graph by going as deep as possible along one path before backtracking. It's often implemented recursively and mimics exploring every possibility, making it suitable for problems involving combinations, permutations, or full structural exploration. Like BFS, it has distinct uses for trees (no 'visited' set needed) and graphs (where a 'visited' set is crucial to avoid cycles and infinite recursion).
For trees, recursive DFS is clean: define a function that takes a node. Base case: if node is None, return. Recursive step: process the current node. Then, recursively call DFS on its left child, then its right child. This explores the entire left subtree before moving to the right. No 'visited' set is needed due to the acyclic nature of trees. Useful for flattening trees, building structures, or searching nodes based on logic rather than distance.
To find the maximum depth of a binary tree, DFS is highly effective. The recursive helper function works as follows: Base case: if the node is None, return 0. Recursive step: calculate the max depth of the left subtree (max_depth(node.left)) and the right subtree (max_depth(node.right)). Return 1 + max(left_depth, right_depth) (1 for the current node). The main function calls this helper on the root. This bubbles up the maximum depth from the leaves to the root.
Given a grid of '1's (land) and '0's (water), count the number of islands (connected land tiles). Iterate through every cell. If a cell is '1' (unvisited land), increment the island count, then call a DFS function on that cell. The DFS function: if cell is water or out of bounds, return. Otherwise, mark the current cell as '0' (visited/sunk land) to avoid recounting. Recursively call DFS for all four adjacent neighbors (up, down, left, right). This fully explores and 'sinks' one island at a time.
Backtracking is a recursive problem-solving technique that explores all possible solutions but prunes (backs up) when a path becomes invalid. It's akin to DFS with the ability to undo choices. Backtracking is used for problems involving combinations, permutations, partitions, or paths, where a partial solution is built step-by-step. The template typically involves a recursive function that makes a choice, explores, and then 'un-makes' the choice (backtracks). Early pruning of invalid paths is crucial for efficiency. Key elements include storing results (a copy of the path), handling base cases (complete solutions), iterating through choices, pruning invalid choices, making selections, recurring deeper, and backtracking state changes.
To determine if a word exists in a 2D grid by tracing adjacent letters, use backtracking. Iterate through each cell on the board, treating it as a potential starting point for DFS. The recursive DFS function: Base cases: If the current letter doesn't match the word's character at its position, return False (pruning). If the entire word is matched, return True. Recursive step: Mark the current cell as 'visited' (e.g., change to '*'). Explore all four neighbors. If any recursive call returns True, propagate True. Backtrack: restore the cell's original character. This explores all paths and intelligently prunes.
Priority Queues, typically implemented as binary heaps, are special queues where elements are extracted based on priority, not insertion order. Min-heaps ensure the smallest element is always at the top; max-heaps ensure the largest. Insertion and removal take O(log N) time. Heaps are crucial for problems requiring repeated extraction of min/max items (e.g., top-K largest/smallest, real-time ranking, Dijkstra's algorithm, on-the-fly sorting without full array sorting). Python's default 'heapq' module implements min-heaps, with max-heap behavior achievable by negating values.
To find the K closest points to the origin (0,0), use a min-heap. For each point (x, y), calculate its squared Euclidean distance (x^2 + y^2) to avoid square roots. Push a tuple (distance, point) into the min-heap. Due to the heap's structure, the smallest distance will always be at the top. After processing all points, repeatedly pop the smallest element from the heap K times to get the K closest points. This is efficient as each heap operation is O(log N).
To find the Kth largest element in an unsorted array efficiently, use a min-heap, transforming it into a max-heap. Negate all numbers in the input array. Then, 'heapify' the modified array (O(N) operation) to form a min-heap (which now behaves like a max-heap due to negation). To find the Kth largest element, pop the largest (smallest negated) element K-1 times. The next element at the top of the heap (after negating it back) will be the Kth largest element. This approach is faster than fully sorting the array.