DSA Foundations

1. What Even IS a Data Structure?

Imagine you just moved into a new house. You have a bunch of stuff -- books, clothes, food, tools. You could just throw everything into one giant pile in the middle of the room. But that would be a nightmare to find anything in, right?

So instead, you organize your stuff:

• Books go on a bookshelf (easy to browse, sorted by topic)
• Clothes go in a wardrobe (easy to pick an outfit)
• Food goes in the fridge (keeps things fresh, organized by shelf)
• Tools go in a toolbox (everything has its slot)

A data structure is exactly the same thing, but for computer data. It's a way of organizing information so you can find it, add to it, and work with it efficiently.

Just like you wouldn't use a bookshelf to store soup (that's what the fridge is for), different data structures are good for different jobs:

2. What Even IS an Algorithm?

An algorithm is just a set of steps to solve a problem. That's it. You already use algorithms every day without realizing it.

In programming, an algorithm is the same thing -- a step-by-step procedure to solve a problem. For example:

• Finding the biggest number in a list -- look at each number, keep track of the biggest one you've seen so far
• Sorting a deck of cards -- pick up cards one at a time, insert each into the right position
• Finding a word in a dictionary -- open to the middle, decide if your word comes before or after, repeat on the correct half

That last one? That's binary search -- one of the most important algorithms in computer science. You've been doing it since you were a kid looking up words.

3. How Computers Store Data (Memory)

Before you can understand data structures, you need to understand how a computer actually stores data. Don't worry -- it's simpler than you think.

RAM = A Giant Row of Numbered Boxes

Your computer's memory (RAM) is like a massive row of numbered mailboxes. Each mailbox:

• Has a number (called an address) -- like mailbox #0, #1, #2, etc.
• Can hold one piece of data -- a number, a letter, etc.
• Can be accessed instantly if you know its number

When you create a variable in code like x = 42, the computer:

1. Finds an empty mailbox (say, address #0)
2. Puts the value 42 in it
3. Remembers that "x" means "go to address #0"

Why This Matters for Data Structures

The key insight is: going to a specific mailbox by its number is instant. The computer doesn't have to walk past mailbox #0, #1, #2... to get to mailbox #500. It just jumps straight there. This is called random access, and it's why arrays are so fast at looking up items by index.

4. Time Complexity -- The Most Important Concept in DSA

This is it. This is the single most important concept in all of data structures and algorithms. If you understand this deeply, everything else falls into place.

Why We Care About Speed

Imagine you're building an app. When you have 100 users, any code works fine. But what happens when you have 1,000,000 users? Or 1,000,000,000?

Bad code that takes 1 second for 100 users might take 3 hours for 1,000,000 users. Good code takes 1 second for both. That's the difference between a successful app and a broken one.

We Count Steps, Not Seconds

We don't measure speed in seconds because different computers run at different speeds. Instead, we count how many operations the algorithm needs as the input gets bigger.

The Big-O Notation Cheat Sheet

Big-O tells us: "As the input gets really big, how does the number of operations grow?"

Let's See Actual Numbers

This is where it gets real. Look at how many operations each complexity needs for different input sizes:

Understanding Each Complexity

O(1) -- Constant Time

No matter how big the input is, it always takes the same number of steps.

O(log n) -- Logarithmic Time

Each step cuts the problem in half. This is the magic of binary search.

O(n) -- Linear Time

You look at every element once. If the input doubles, the time doubles.

def find_sum(arr):
    total = 0
    for num in arr:   # visits each element once = O(n)
        total += num
    return total

O(n²) -- Quadratic Time

For every element, you look at every OTHER element. It's a nested loop.

# This is O(n²) -- nested loop
for i in range(len(arr)):
    for j in range(len(arr)):   # for EACH i, we loop through ALL j
        if arr[i] + arr[j] == target:
            return [i, j]

O(2ⁿ) -- Exponential Time

The number of operations doubles every time you add one more element. This blows up incredibly fast.

5. The Math Behind Big-O (Why It Works)

Big-O notation describes the upper bound on growth rate. Formally: f(n) = O(g(n)) means there exist constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.

In plain English: we only care about the fastest-growing term, and we drop constants.

Rule 1: Drop Constants

Rule 2: Drop Lower-Order Terms

Rule 3: Different Steps Get Added

The Math Behind log₂(n)

Logarithms answer the question: "How many times do I need to divide n by 2 to get to 1?"

This is why binary search is so powerful. Even for 1 billion elements, you only need ~30 steps. Each step cuts the search space in half.

Why O(n log n) Is the Sorting Sweet Spot

The best comparison-based sorting algorithms (merge sort, quick sort) are O(n log n). Here's the intuition:

6. Space Complexity

Space complexity is the same idea as time complexity, but for memory instead of time.

If your algorithm creates a new array of size n, that's O(n) space. If it only uses a few variables regardless of input size, that's O(1) space.

The Time-Space Trade-Off

Often, you can make code faster by using more memory, or save memory by being slower. This is one of the most fundamental trade-offs in CS.

7. Every Data Structure Explained From Zero

Now that you understand time complexity, let's learn each data structure. For each one, we'll cover: what it is, how it works internally, time complexity for every operation (and WHY), and when to use it.

For deep dives with code implementations, click through to each topic's dedicated page.

Arrays -- The Foundation of Everything

Analogy: A row of numbered lockers in a school hallway.

Elements are stored in consecutive memory locations. Because they're consecutive, the computer can calculate exactly where any element is:

This is why accessing by index is O(1) -- it's just one multiplication and one addition, no matter how big the array is.

Deep dive: Arrays & Strings page

Linked Lists -- The Treasure Hunt

Analogy: A treasure hunt where each clue tells you where the next clue is.

Each element (called a node) stores two things: its value AND a pointer to the next node. Nodes can be scattered anywhere in memory -- they don't need to be consecutive.

Deep dive: Linked Lists page

Stacks -- Last In, First Out (LIFO)

Analogy: A stack of plates. You can only add or remove from the top.

Three operations, ALL O(1):

• Push: Add to the top
• Pop: Remove from the top
• Peek: Look at the top without removing

Why O(1)? You always know exactly where the top is. No searching needed.

Use cases: Undo/redo, browser back button, matching parentheses, function call stack, DFS.

Deep dive: Stacks & Queues page

Queues -- First In, First Out (FIFO)

Analogy: A line at a shop. First person in line gets served first.

Two operations, both O(1):

• Enqueue: Add to the back
• Dequeue: Remove from the front

Use cases: BFS, task scheduling, printer queue, message queues.

Hash Maps -- The Most Important Interview Data Structure

Analogy: A magical librarian who instantly knows exactly which shelf any book is on.

A hash map stores key-value pairs and can find any value by its key in O(1) average time. How?

Deep dive: Hash Maps & Sets page

Trees -- Hierarchical Data

Analogy: A family tree, or an org chart, or your file system (folders inside folders).

A Binary Search Tree (BST) has a special rule: left child < parent < right child. This means searching is like binary search:

Deep dive: Trees & BST page

Heaps -- Tournament Brackets

Analogy: A tournament bracket where the winner always rises to the top.

A min-heap always keeps the smallest element at the root. A max-heap keeps the largest. Both support:

Use cases: Priority queues, finding Kth largest/smallest, Dijkstra's algorithm, merge K sorted lists.

Deep dive: Advanced Topics page

Graphs -- Connections Between Things

Analogy: A social network (people are nodes, friendships are edges) or a road map (cities are nodes, roads are edges).

Graphs are the most general data structure. Trees are actually a special type of graph (connected, no cycles). Linked lists are a special type of tree (each node has at most one child).

Two ways to explore graphs:

• BFS (Breadth-First Search): Explore level by level, like ripples in water. Uses a queue. Good for finding shortest paths.
• DFS (Depth-First Search): Go as deep as possible, then backtrack. Uses a stack (or recursion). Good for exploring all paths.

Deep dive: Graphs page

Tries -- Autocomplete on Your Phone

Analogy: The autocomplete feature that shows suggestions as you type each letter.

Each node represents a letter. Paths from root to leaf form words. Finding all words that start with "ca" means just following c → a and then listing everything below.

Deep dive: Advanced Topics page

8. Essential Algorithms Explained

Binary Search -- Halving Your Way to the Answer

Requirement: The data must be sorted.

How it works: Compare the target with the middle element. If target is smaller, search the left half. If larger, search the right half. Repeat.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1     # target is in right half
        else:
            right = mid - 1    # target is in left half
    return -1  # not found

Recursion -- Functions That Call Themselves

Analogy: Russian nesting dolls. Open a doll, find a smaller doll inside. Keep opening until you reach the smallest doll (the base case).

Every recursive function needs:

1. Base case: When to stop (the smallest doll)
2. Recursive case: Break the problem into a smaller version of itself

# Factorial: 5! = 5 × 4 × 3 × 2 × 1
def factorial(n):
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)  # recursive case

Two Pointers

Analogy: Reading a book from both ends simultaneously, moving inward.

Use two pointers (usually start and end) and move them toward each other based on conditions. Works on sorted arrays or when you need to find pairs.

Deep dive: LeetCode Patterns page

Sliding Window

Analogy: A magnifying glass sliding across a page, looking at a fixed-width section at a time.

Maintain a "window" of elements and slide it across the array, adding/removing one element at a time instead of recalculating everything.

Deep dive: LeetCode Patterns page

Dynamic Programming

Analogy: Instead of recalculating your monthly expenses every time someone asks, you write the total on a sticky note and just read it next time.

DP = solving a problem by breaking it into smaller overlapping subproblems and remembering (memoizing) the results so you never solve the same subproblem twice.

Deep dive: Dynamic Programming page

Sorting

The most common sorting algorithms and when to use them:

Deep dive: Sorting & Searching page

9. Recursion -- Functions That Call Themselves

Analogy: Russian nesting dolls. Open a doll, find a smaller doll inside. Keep opening until you reach the smallest doll (the base case).

Every recursive function needs:

1. Base case: When to stop (the smallest doll) -- returns a value without further recursion
2. Recursive case: Break the problem into a smaller version of itself and call itself

Why Recursion Works

Each recursive call solves a smaller version of the same problem. Eventually you reach the base case, then the results "unwind" back up.

Recursion Patterns (LeetCode Style)

Pattern 1: Linear Recursion

Process elements one at a time, moving forward or backward.

Python - Reverse a String
class Solution:
    def reverse_string(self, s: list[str]) -> None:
        def solve(left: int, right: int):
            if left >= right:
                return
            s[left], s[right] = s[right], s[left]
            solve(left + 1, right - 1)
        solve(0, len(s) - 1)

Pattern 2: Binary Recursion

Split problem into two halves, process each recursively.

Python - Fibonacci
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)

Pattern 3: Recursion with Memoization

Add caching to avoid recalculating the same subproblems.

Python - Fibonacci with Memo
class Solution:
    def fib(self, n: int) -> int:
        cache = {}
        def solve(x: int) -> int:
            if x in cache:
                return cache[x]
            if x <= 1:
                return x
            cache[x] = solve(x - 1) + solve(x - 2)
            return cache[x]
        return solve(n)

Pattern 4: Tree Recursion

Recursively process left and right subtrees.

Python - Binary Tree Inorder Traversal
class Solution:
    def inorder_traversal(self, root) -> list[int]:
        result = []
        def solve(node):
            if not node:
                return
            solve(node.left)
            result.append(node.val)
            solve(node.right)
        solve(root)
        return result

10. Backtracking -- Try All Possibilities

Analogy: Exploring a maze. You try a path, if it hits a dead end, you backtrack to the last junction and try a different path.

Backtracking = Recursion + Choice + Undo Choice. You explore all possibilities by making a choice, recursing, then undoing that choice to try another.

Backtracking Patterns (LeetCode Style)

Pattern 1: Subsets (Include/Exclude)

Python
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = []
        def backtrack(start: int, path: list[int]):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()
        backtrack(0, [])
        return result

Pattern 2: Permutations

Python
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        used = [False] * len(nums)
        def backtrack(path: list[int]):
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(len(nums)):
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    backtrack(path)
                    path.pop()
                    used[i] = False
        backtrack([])
        return result

Pattern 3: Combination Sum

Python
class Solution:
    def combination_sum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
        def backtrack(start: int, path: list[int], remaining: int):
            if remaining == 0:
                result.append(path[:])
                return
            if remaining < 0:
                return
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(i, path, remaining - candidates[i])
                path.pop()
        backtrack(0, [], target)
        return result

Pattern 4: N-Queens

Python
class Solution:
    def solve_n_queens(self, n: int) -> list[list[str]]:
        result = []
        cols = set()
        diag1 = set()
        diag2 = set()
        def backtrack(row: int, path: list[str]):
            if row == n:
                result.append(path[:])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                path.append("." * col + "Q" + "." * (n - col - 1))
                backtrack(row + 1, path)
                path.pop()
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
        backtrack(0, [])
        return result

11. Prefix Sum -- Precompute Cumulative Sums

Analogy: Instead of counting books on each shelf every time someone asks, you precompute cumulative totals and just subtract to get any range.

Precompute a running sum array so you can answer any "sum from index i to j" query in O(1).

Prefix Sum Patterns (LeetCode Style)

Pattern 1: Range Sum Query

Python
class Solution:
    def range_sum(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            prefix[i + 1] = prefix[i] + nums[i]
        
        result = []
        for l, r in queries:
            result.append(prefix[r + 1] - prefix[l])
        return result

Pattern 2: Subarray Sum Equals K

Python
class Solution:
    def subarray_sum(self, nums: list[int], k: int) -> int:
        count = 0
        prefix = 0
        prefix_counts = {0: 1}
        
        for num in nums:
            prefix += num
            count += prefix_counts.get(prefix - k, 0)
            prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1
        
        return count

Pattern 3: Continuous Subarray with Positive Sum

Python
class Solution:
    def max_subarray_len(self, nums: list[int], k: int) -> int:
        prefix = 0
        prefix_index = {0: -1}
        max_len = 0
        
        for i, num in enumerate(nums):
            prefix += num
            if prefix - k in prefix_index:
                max_len = max(max_len, i - prefix_index[prefix - k])
            if prefix not in prefix_index:
                prefix_index[prefix] = i
        
        return max_len

Pattern 4: Difference Array (Range Update)

Python
class Solution:
    def corp_flight_bookings(self, bookings: list[list[int]], n: int) -> list[int]:
        diff = [0] * (n + 1)
        
        for start, end, seats in bookings:
            diff[start - 1] += seats
            diff[end] -= seats
        
        result = [0] * n
        for i in range(n):
            result[i] = result[i - 1] + diff[i] if i > 0 else diff[i]
        
        return result

12. Suffix Sum -- Precompute from Right

Analogy: Similar to prefix sum, but instead of "how much from the start," you want "how much from the end."

Useful when you need to quickly answer queries like "sum from index i to end" or when processing from right to left.

Suffix Sum Patterns (LeetCode Style)

Pattern 1: Suffix Sum Array

Python
class Solution:
    def suffix_sum(self, nums: list[int]) -> list[int]:
        n = len(nums)
        suffix = [0] * n
        suffix[n - 1] = nums[n - 1]
        
        for i in range(n - 2, -1, -1):
            suffix[i] = nums[i] + suffix[i + 1]
        
        return suffix

Pattern 2: Right-side Processing

Python - Product of Array Except Self
class Solution:
    def product_except_self(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [1] * n
        
        prefix = 1
        for i in range(n):
            result[i] = prefix
            prefix *= nums[i]
        
        suffix = 1
        for i in range(n - 1, -1, -1):
            result[i] *= suffix
            suffix *= nums[i]
        
        return result

Pattern 3: Minimum Path Sum from Right

Python
class Solution:
    def min_path_sum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        for j in range(n - 1, -1, -1):
            for i in range(m - 1, -1, -1):
                if i == m - 1 and j == n - 1:
                    continue
                if i == m - 1:
                    grid[i][j] += grid[i][j + 1]
                elif j == n - 1:
                    grid[i][j] += grid[i + 1][j]
                else:
                    grid[i][j] += min(grid[i + 1][j], grid[i][j + 1])
        
        return grid[0][0]

Pattern 4: Longest Happy Prefix (Suffix-based)

Python
class Solution:
    def longest_prefix(self, s: str) -> str:
        n = len(s)
        for length in range(n - 1, 0, -1):
            if s[:length] == s[n - length:]:
                return s[:length]
        return ""

13. Sweep Line -- Event-Based Processing

Analogy: A security guard walking along a street, counting how many people are on the street at each moment. When someone enters, count goes up; when someone leaves, count goes down.

Convert 2D/interval problems into sorted 1D events. Sweep left to right, maintaining state.

Sweep Line Patterns (LeetCode Style)

Pattern 1: Meeting Rooms II

Python
class Solution:
    def min_meeting_rooms(self, intervals: list[list[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append((start, 1))
            events.append((end, -1))
        
        events.sort()
        
        max_rooms = 0
        current = 0
        for _, delta in events:
            current += delta
            max_rooms = max(max_rooms, current)
        
        return max_rooms

Pattern 2: My Calendar III (Maximum Overlap)

Python
class MyCalendarThree:
    def __init__(self):
        self.events = collections.defaultdict(int)

    def book(self, start: int, end: int) -> int:
        self.events[start] += 1
        self.events[end] -= 1
        
        active = 0
        max_overlap = 0
        for time in sorted(self.events):
            active += self.events[time]
            max_overlap = max(max_overlap, active)
        
        return max_overlap

Pattern 3: Rectangle Overlap

Python
class Solution:
    def is_rectangle_overlap(self, rec1: list[int], rec2: list[int]) -> bool:
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        
        return not (x2 <= x3 or x4 <= x1 or y2 <= y3 or y4 <= y1)

Pattern 4: Car Pooling

Python
class Solution:
    def car_pooling(self, trips: list[list[int]], capacity: int) -> bool:
        events = []
        for num, start, end in trips:
            events.append((start, num))
            events.append((end, -num))
        
        events.sort()
        
        current = 0
        for _, delta in events:
            current += delta
            if current > capacity:
                return False
        
        return True

14. Memoization -- Remember Your Work

Analogy: Instead of recalculating your monthly budget every time someone asks, you write it on a sticky note and just read it next time.

Memoization = Recursion + Cache. Store results of expensive function calls and return cached result when the same inputs occur again.

Memoization Patterns (LeetCode Style)

Pattern 1: Climbing Stairs (1D Memo)

Python
class Solution:
    def climb_stairs(self, n: int) -> int:
        cache = {}
        def solve(i: int) -> int:
            if i in cache:
                return cache[i]
            if i <= 2:
                return i
            cache[i] = solve(i - 1) + solve(i - 2)
            return cache[i]
        return solve(n)

Pattern 2: House Robber (1D Memo)

Python
class Solution:
    def rob(self, nums: list[int]) -> int:
        cache = {}
        def solve(i: int) -> int:
            if i in cache:
                return cache[i]
            if i < 0:
                return 0
            result = max(solve(i - 1), solve(i - 2) + nums[i])
            cache[i] = result
            return result
        return solve(len(nums) - 1)

Pattern 3: Unique Paths (2D Memo)

Python
class Solution:
    def unique_paths(self, m: int, n: int) -> int:
        cache = {}
        def solve(i: int, j: int) -> int:
            if (i, j) in cache:
                return cache[(i, j)]
            if i >= m or j >= n:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            cache[(i, j)] = solve(i + 1, j) + solve(i, j + 1)
            return cache[(i, j)]
        return solve(0, 0)

Pattern 4: Unique Paths with Obstacles

Python
class Solution:
    def unique_paths_with_obstacles(self, grid: list[list[int]]) -> int:
        N = len(grid)
        M = len(grid[0])
        
        if grid[N - 1][M - 1] == 1:
            return 0
        
        cache = {}
        def solve(x: int, y: int) -> int:
            key = str(x) + "," + str(y)
            if key in cache:
                return cache[key]
            if x < 0 or x >= N or y < 0 or y >= M:
                return 0
            if grid[x][y] == 1:
                return 0
            if x == N - 1 and y == M - 1:
                return 1
            cache[key] = solve(x + 1, y) + solve(x, y + 1)
            return cache[key]
        
        solve()
        return cache["0,0"] if "0,0" in cache else 0

Pattern 5: Coin Change (Memo)

Python
class Solution:
    def coin_change(self, coins: list[int], amount: int) -> int:
        cache = {}
        def solve(remaining: int) -> int:
            if remaining in cache:
                return cache[remaining]
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            
            min_coins = float('inf')
            for coin in coins:
                min_coins = min(min_coins, solve(remaining - coin) + 1)
            
            cache[remaining] = min_coins
            return min_coins
        
        result = solve(amount)
        return result if result != float('inf') else -1

Pattern 6: Longest Common Subsequence (String Memo)

Python
class Solution:
    def longest_common_subsequence(self, text1: str, text2: str) -> int:
        cache = {}
        def solve(i: int, j: int) -> int:
            if (i, j) in cache:
                return cache[(i, j)]
            if i == len(text1) or j == len(text2):
                return 0
            
            if text1[i] == text2[j]:
                cache[(i, j)] = solve(i + 1, j + 1) + 1
            else:
                cache[(i, j)] = max(solve(i + 1, j), solve(i, j + 1))
            return cache[(i, j)]
        
        return solve(0, 0)

15. Tabulation -- Build Up Solutions

Analogy: Instead of starting from the top and working down (like memoization), you start from the bottom (base cases) and build up to the final answer iteratively.

Tabulation = Bottom-Up DP. No recursion. Just fill a table from base cases to final answer.

Tabulation Patterns (LeetCode Style)

Pattern 1: Climbing Stairs (1D Tab)

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

Pattern 2: House Robber (1D Tab)

Python
class Solution:
    def rob(self, nums: list[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        
        return dp[-1]

Pattern 3: Unique Paths (2D Tab)

Python
class Solution:
    def unique_paths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        return dp[m - 1][n - 1]

Pattern 4: Longest Common Subsequence (2D Tab)

Python
class Solution:
    def longest_common_subsequence(self, text1: str, text2: str) -> int:
        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]

Pattern 5: Coin Change (1D Tab)

Python
class Solution:
    def coin_change(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 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

Pattern 6: 0/1 Knapsack (2D Tab)

Python
class Solution:
    def knapsack(self, weights: list[int], values: list[int], capacity: int) -> int:
        n = len(weights)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for w in range(capacity + 1):
                if weights[i - 1] <= w:
                    dp[i][w] = max(
                        dp[i - 1][w],
                        dp[i - 1][w - weights[i - 1]] + values[i - 1]
                    )
                else:
                    dp[i][w] = dp[i - 1][w]
        
        return dp[n][capacity]

Pattern 7: Edit Distance (2D Tab)

Python
class Solution:
    def min_distance(self, word1: str, word2: str) -> int:
        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
        for j in range(n + 1):
            dp[0][j] = j
        
        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]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        
        return dp[m][n]

16. Python & Java DSA Quick Reference

Quick syntax reference for the most common DSA operations in both Python and Java.

1. Arrays

Python

# Create array
arr = [1, 2, 3, 4, 5]

# Access - O(1)
arr[0]  # first element
arr[-1]  # last element

# Length - O(1)
len(arr)

# Append - O(1) amortized
arr.append(6)

# Insert at index - O(n)
arr.insert(0, 0)  # insert 0 at beginning

# Remove at index - O(n)
arr.pop()         # remove last
arr.pop(0)      # remove first

# Slicing - O(k)
arr[1:4]     # elements at index 1,2,3
arr[:3]      # first 3 elements
arr[2:]      # from index 2 to end

# Sort - O(n log n)
arr.sort()
arr.sort(reverse=True)
sorted_arr = sorted(arr)

# Search - O(n) for linear, O(log n) for binary
5 in arr              # linear search
# Binary search requires sorted array
import bisect
bisect.bisect_left(arr, 3)  # returns index

# 2D Array
matrix = [[1, 2], [3, 4]]
matrix[0][1]  # row 0, col 1 = 2

Java

// Create array
int[] arr = {1, 2, 3, 4, 5};
int[] arr2 = new int[10];

// Access - O(1)
arr[0];   // first element
arr[arr.length - 1];  // last element

// Length - O(1)
arr.length

// ArrayList - dynamic array
ArrayList<Integer> list = new ArrayList<>();
list.add(1);           // O(1) amortized
list.get(0);            // O(1)
list.remove(0);          // O(n)
list.size();             // O(1)

// Sort - O(n log n)
Arrays.sort(arr);
Arrays.sort(arr, Collections.reverseOrder());

// Binary search - O(log n)
Arrays.binarySearch(arr, 3);

// 2D Array
int[][] matrix = {{1, 2}, {3, 4}};
matrix[0][1];  // row 0, col 1 = 2

2. Lists / ArrayLists

Python

# List is same as array above

# List comprehension
squares = [x*x for x in range(10)]
evens = [x for x in arr if x % 2 == 0]

# List operations
arr.extend([6, 7])  # add multiple
arr.remove(3)           # remove first occurrence
arr.index(5)           # find index
arr.count(5)           # count occurrences

Java

// ArrayList
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(0, 5);  // insert at index 0
list.get(0);
list.set(0, 10);  // update
list.remove(0);    // by index
list.remove(Integer.valueOf(5));  // by value
list.contains(5);
list.indexOf(5);
list.size();

// Iterate
for (int x : list) { ... }
for (int i = 0; i < list.size(); i++) { ... }

3. HashMap / Dict

Python

# Create
hashmap = {"a": 1, "b": 2}
from collections import defaultdict
dd = defaultdict(int)  # default value 0

# Access - O(1)
hashmap["a"]
hashmap.get("c", 0)  # default if not found

# Insert/Update - O(1)
hashmap["c"] = 3

# Delete - O(1)
del hashmap["a"]
hashmap.pop("b")

# Check existence
"a" in hashmap

# Iterate
for key in hashmap:
    print(key, hashmap[key])

for key, val in hashmap.items():
    print(key, val)

# Get all keys/values
hashmap.keys()
hashmap.values()
hashmap.items()

Java

// Create
HashMap<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);

// Access - O(1)
map.get("a");
map.getOrDefault("c", 0);

// Insert/Update - O(1)
map.put("c", 3);
map.putIfAbsent("d", 4);

// Delete - O(1)
map.remove("a");
map.remove("b", 2);  // only if key=value

// Check existence
map.containsKey("a");
map.containsValue(1);

// Iterate
for (String key : map.keySet()) { ... }
for (Integer val : map.values()) { ... }
for (Map.Entry<String, Integer> e : map.entrySet()) {
    e.getKey();
    e.getValue();
}

// Get all
map.keySet();
map.values();
map.entrySet();

4. HashSet

Python

# Create
s = {1, 2, 3}
s = set()  # empty set

# Add - O(1)
s.add(4)
s.update([5, 6])

# Remove - O(1)
s.remove(3)    # throws if not found
s.discard(3)  # no error if not found
s.pop()        # remove and return arbitrary

# Check
5 in s

# Set operations
s1 | s2         # union
s1 & s2         # intersection
s1 - s2         # difference
s1 ^ s2         # symmetric difference

Java

// Create
HashSet<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);

// Add - O(1)
set.add(4);

// Remove - O(1)
set.remove(3);

// Check
set.contains(5);

// Set operations
HashSet<Integer> set1 = new HashSet<>(Arrays.asList(1,2,3));
HashSet<Integer> set2 = new HashSet<>(Arrays.asList(2,3,4));

set1.addAll(set2);           // union
set1.retainAll(set2);       // intersection
set1.removeAll(set2);       // difference

5. Stack & Queue

Python

# Stack (LIFO) - use list
stack = [1, 2, 3]
stack.append(4)    # push - O(1)
stack.pop()           # pop - O(1)
stack[-1]          # peek - O(1)

# Queue (FIFO) - use collections.deque
from collections import deque
queue = deque([1, 2])
queue.append(3)      # enqueue - O(1)
queue.popleft()       # dequeue - O(1)
queue[0]              # peek - O(1)

Java

// Stack (LIFO)
Stack<Integer> stack = new Stack<>();
stack.push(1);        // O(1)
stack.pop();          // O(1)
stack.peek();         // O(1)

// Queue (FIFO)
Queue<Integer> queue = new LinkedList<>();
queue.add(1);         // enqueue - O(1)
queue.remove();       // dequeue - O(1)
queue.peek();         // peek - O(1)

// Priority Queue (Heap)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap.add(5);
minHeap.poll();       // get min - O(log n)
minHeap.peek();

6. String Operations

Python

# Create
s = "hello"

# Access - O(1)
s[0]

# Length - O(1)
len(s)

# Find - O(n)
s.find("ll")     # returns index or -1
s.index("ll")    # throws if not found

# Slice - O(k)
s[1:4]

# Split/Join - O(n)
s.split(",")
",".join(["a", "b"])

# Replace - O(n)
s.replace("l", "x")

# Check
s.startswith("he")
s.endswith("lo")
s.isdigit()
s.isalpha()

# Convert
s.upper()
s.lower()
s.strip()

Java

// Create
String s = "hello";

// Access - O(1)
s.charAt(0);

// Length - O(1)
s.length();

// Find - O(n)
s.indexOf("ll");     // returns index or -1
s.lastIndexOf("l");

// Substring - O(k)
s.substring(1, 4);   // [1, 4)

// Split/Join
s.split(",");
String.join(",", Arrays.asList("a", "b"));

// Replace
s.replace("l", "x");
s.replaceAll("regex", "x");

// Check
s.startsWith("he");
s.endsWith("lo");
Character.isDigit(s.charAt(0));
Character.isLetter(s.charAt(0));

// Convert
s.toUpperCase();
s.toLowerCase();
s.trim();

// StringBuilder (mutable, efficient)
StringBuilder sb = new StringBuilder();
sb.append("hello");
sb.toString();

7. Loops & Iteration

Python

# For loop
for i in range(10):        # 0 to 9
for i in range(1, 10):      # 1 to 9
for i in range(0, 10, 2):  # 0,2,4,6,8

# For each
for x in arr:
    print(x)

# Enumerate (index + value)
for i, val in enumerate(arr):
    print(i, val)

# While
while condition:
    ...

# List comprehension
doubled = [x*2 for x in arr]

Java

// For loop
for (int i = 0; i < 10; i++) { ... }

// Enhanced for
for (int x : arr) { ... }

// While
while (condition) { ... }

// Stream (Java 8+)
Arrays.stream(arr)
    .filter(x -> x % 2 == 0)
    .map(x -> x * 2)
    .toArray();

8. Common Utilities

Python

import heapq
import collections

# Min Heap
heap = [3, 1, 4]
heapq.heapify(heap)      # O(n)
heapq.heappush(heap, 2)  # O(log n)
heapq.heappop(heap)      # O(log n)

# Counter (frequency)
counter = collections.Counter(arr)
counter.most_common(3)  # top 3

# Max/Min
max(arr)
min(arr)
max(arr, key=len)

# Sum/Product
sum(arr)
prod(arr)  # Python 3.8+

# Reversed
reversed(arr)
reversed(range(10))

# Infinite
float('inf')
-float('inf')

Java

import java.util.*;

// Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Counter - use HashMap
HashMap<Integer, Integer> counter = new HashMap<>();
for (int x : arr) {
    counter.put(x, counter.getOrDefault(x, 0) + 1);
}

// Max/Min
Collections.max(list);
Collections.min(list);
Arrays.stream(arr).max().getAsInt();

// Sum
Arrays.stream(arr).sum();

// Reverse
Collections.reverse(list);
// For array: convert to list, reverse, convert back

// Infinity
Integer.MAX_VALUE;
Integer.MIN_VALUE;
Double.POSITIVE_INFINITY;
Double.NEGATIVE_INFINITY;

17. How to Think About Problems

This is where most people get stuck -- not because they don't know data structures, but because they don't have a systematic approach to problem-solving.

1. Read the problem carefully. Read it twice. Highlight constraints (input size, value ranges).
2. Work through examples by hand. Use small inputs. Draw pictures. Trace through the logic on paper.
3. Think about edge cases. Empty input? One element? All duplicates? Negative numbers?
4. Start with brute force. What's the simplest, most obvious solution? Even if it's O(n³), write it down.
5. Identify the bottleneck. What's making it slow? Is there a nested loop that could be replaced with a hash map?
6. Ask yourself these questions:
   • Can I use a hash map to avoid repeated lookups?
   • Can I sort first to enable two pointers or binary search?
   • Is this a sliding window problem (subarray/substring)?
   • Can I use two pointers (sorted array, palindrome)?
   • Is this a tree/graph traversal (BFS/DFS)?
   • Does it have overlapping subproblems (DP)?
   • Can I use a stack (matching, nearest greater/smaller)?
7. Code it up. Write clean code. Use meaningful variable names.
8. Test with examples. Walk through your code with the given examples. Try edge cases.

18. Tips to Become a World-Class Competitive Programmer

• 1
  Practice every single day. Consistency beats intensity. 1 problem per day for a year (365 problems) is better than 20 problems in one weekend then nothing for months. Set a daily alarm.
• 2
  Learn patterns, not solutions. When you solve a problem, ask yourself: "What pattern did this use? Where else could I apply this?" Memorizing solutions is useless. Understanding patterns transfers to new problems.
• 3
  Time yourself. Easy: 15-20 min. Medium: 25-35 min. Hard: 40-50 min. If you can't solve it in time, read the editorial. Then close it and solve it yourself the next day from memory.
• 4
  Always start with brute force. A working O(n²) solution is infinitely better than a broken O(n) solution. Get something working first, then optimize.
• 5
  Study the top solutions after solving. Even if you got it right, look at how others solved it. You'll learn cleaner techniques, new patterns, and language tricks.
• 6
  Implement data structures from scratch at least once. Build a linked list, BST, hash map, heap, and trie yourself. This gives you deep understanding that reading can't provide.
• 7
  Do virtual contests. Codeforces, LeetCode Weekly, AtCoder. The pressure of a time limit forces you to think faster and builds real competition skills.
• 8
  Focus on weak areas. It's comfortable to solve Easy array problems all day. But growth happens when you struggle with graphs, DP, and trees. Track which topics you fail at and target those.
• 9
  Read editorials even for problems you solved. The official editorial often has a more elegant or faster approach you didn't think of.
• 10
  Build a problem-solving journal. After each problem, write: the pattern used, what you got stuck on, the key insight. Review this weekly. Your future self will thank you.

19. Learning Roadmap

Follow this order. Each topic builds on the previous one.

20. Practice Quiz