Big O Notation: From Zero to Interview-Ready #

Prerequisite knowledge: None. If you can count and write Ruby, you're good. Time to study: 2 days. Read Parts 1-3 today, Parts 4-7 tomorrow, then review the cheat sheet before your next interview.

Table of Contents #

1. What Is Big O? (The Concept)
2. The Common Big O Types (With Ruby Code)
3. How to Analyze Your Own Code
4. Space Complexity (Brief)
5. Big O Patterns for Common Ruby Operations
6. Interview Cheat Sheet
7. Practice Problems (Ranked by Difficulty)

Part 1: What Is Big O? (The Concept) #

Why Should You Care? #

Two reasons:

Interview reason: In a coding interview, after you write working code, the interviewer will ask: "What's the time complexity of your solution?" or "Can you optimize this?" If you can't answer, it's a red flag. If you can, it shows you think about code quality beyond "does it work."

Real-world reason: If you've worked with Rails, you already feel Big O, even if you don't know the terminology. When you say "this N+1 query is killing us" or "let's cache this instead of hitting the database every time" -- that's Big O thinking. You're already doing it. We're just putting names to things you already know.

The Core Idea #

Big O answers one question:

"As my input gets bigger, how much slower does my code get?"

That's it. That's the whole thing.

Think about it this way. You have a method that works great with 10 items. What happens when you throw 10,000 items at it? Does it: - Stay the same speed? (Great) - Get 1,000x slower? (Okay, that's proportional) - Get 1,000,000x slower? (Your server is on fire)

Big O gives us a way to talk about this without measuring actual milliseconds.

The Phone Book Analogy #

Imagine you need to find "Johnson" in a phone book with 1,000 pages.

Approach 1: Start from page 1, read every name. You might have to read all 1,000 pages. If the phone book doubles to 2,000 pages, your work doubles. Your work grows in proportion to the size of the book. That's O(n) -- "linear time."

Approach 2: Open the book to the middle. Is "Johnson" before or after? You open to page 500. "M" -- Johnson is before M. Now you're looking at pages 1-500. Open to page 250. "F" -- Johnson is after F. Now pages 250-500. Open to 375. "I" -- after I. Pages 375-500. Each time, you cut the problem in half. For 1,000 pages, this takes about 10 steps. For 2,000 pages? Just 11 steps. That's O(log n) -- "logarithmic time."

Approach 3: You have an index at the back that says "Johnson: page 847". You flip to page 847. Done. Doesn't matter if the book has 1,000 pages or 1,000,000 pages. One lookup. That's O(1) -- "constant time."

You already know this intuitively. A hash lookup (like users[email]) is the index. A database query with a proper index is the binary search. A query that table-scans is reading every page.

The Two Rules That Simplify Everything #

Rule 1: We care about the worst case. If your code usually finishes fast but sometimes takes forever, Big O describes the "sometimes takes forever" scenario. Why? Because in production, Murphy's Law applies.

Rule 2: We drop constants and smaller terms. - O(2n) is just O(n). Whether you loop through the array once or twice, it still grows linearly. - O(n + 100) is just O(n). That "+100" stops mattering when n is a million. - O(n² + n) is just O(n^2). When n is 10,000, n² is 100,000,000 and n is just 10,000 -- the n² dominates.

Why? Because Big O isn't about exact speed. It's about the shape of growth. Two straight lines (O(n) and O(2n)) have the same shape. A straight line and a curve (O(n) and O(n²⁾⁾ do not.

The Formal Notation (30 Seconds) #

When someone writes O(n), the "O" stands for "order of." The "n" is the size of your input. That's all the formality you need. Forget the mathematical definition -- you won't need it in an interview.

When you see O(n^2), read it as "oh of n squared." When you see O(n log n), read it as "oh of n log n." You'll see all the common types in the next section.

Part 2: The Common Big O Types (With Ruby Code) #

There are really only 7 complexities you'll ever need to know. Let's go through each one.

1. O(1) -- Constant Time #

Analogy: Flipping a light switch. Doesn't matter how big your house is -- flipping the switch takes the same amount of effort.

What it means: No matter how large the input, the operation takes the same amount of time.

# Hash lookup — O(1)
user_ages = { "Alice" => 30, "Bob" => 28, "Charlie" => 35 }
age = user_ages["Alice"]  # Instant, regardless of hash size

# Array index access — O(1)
numbers = [10, 20, 30, 40, 50]
first = numbers[0]    # O(1)
last = numbers[-1]    # O(1)
length = numbers.length  # O(1)

# Push/pop from end of array — O(1)
numbers.push(60)   # O(1)
numbers.pop        # O(1)

# Simple arithmetic/comparisons — O(1)
def is_even?(n)
  n % 2 == 0  # O(1) — one operation, done
end

When you see it: Hash lookups, array access by index, push/pop, simple math, variable assignment.

Key insight for interviews: When your brute force is slow, the fix is often "use a hash to get O(1) lookups instead of searching through an array." This is the single most common optimization pattern.

2. O(log n) -- Logarithmic Time #

Analogy: The phone book binary search from Part 1. You keep cutting the problem in half, so even massive inputs are fast. To search 1,000,000 items, you only need about 20 steps.

What it means: Each step eliminates half the remaining data. Grows extremely slowly.

# Binary search — O(log n)
# The array MUST be sorted for this to work
def binary_search(sorted_array, target)
  low = 0
  high = sorted_array.length - 1

  while low <= high
    mid = (low + high) / 2

    if sorted_array[mid] == target
      return mid               # Found it
    elsif sorted_array[mid] < target
      low = mid + 1            # Target is in the right half
    else
      high = mid - 1           # Target is in the left half
    end
  end

  -1  # Not found
end

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
binary_search(numbers, 23)  # => 5 (found at index 5)

Why it's O(log n): Each iteration of the while loop cuts the search space in half. Starting with n elements: - After step 1: n/2 elements remain - After step 2: n/4 elements remain - After step 3: n/8 elements remain - After step k: n/2^k elements remain - Done when n/2^k = 1, so k = log2(n) steps

For n = 1,000,000: log2(1,000,000) is about 20. Twenty steps to search a million items.

When you see it: Binary search, balanced tree operations, "divide the problem in half each step."

In Rails terms: A database index lookup is essentially O(log n) because databases use B-trees.

3. O(n) -- Linear Time #

Analogy: Reading a book. To read a 300-page book, you read 300 pages. A 600-page book takes twice as long. Work grows directly with input size.

What it means: You touch every element once (or a fixed number of times).

# Iterating an array — O(n)
def sum(numbers)
  total = 0
  numbers.each { |num| total += num }
  total
end

# .map, .select, .reject — all O(n)
doubled = [1, 2, 3, 4, 5].map { |n| n * 2 }      # visits each element once
evens = [1, 2, 3, 4, 5].select { |n| n.even? }    # visits each element once

# Finding max — O(n)
def find_max(numbers)
  max = numbers[0]
  numbers.each do |num|
    max = num if num > max
  end
  max
end

# Linear search — O(n)
# (This is what Array#include? does under the hood)
def linear_search(array, target)
  array.each_with_index do |element, index|
    return index if element == target
  end
  -1
end

# Counting occurrences — O(n)
def count_char(string, char)
  count = 0
  string.each_char { |c| count += 1 if c == char }
  count
end

When you see it: Any single loop through the data. .each, .map, .select, .reduce, .any?, .find, .count, .include?, .max, .min -- all O(n).

Key insight: O(n) is usually the best you can do for problems where you need to look at every element. If the answer depends on every element (like "sum all numbers"), you can't do better than O(n).

4. O(n log n) -- Linearithmic Time #

Analogy: Sorting a deck of cards using merge sort. You split the deck in half repeatedly (log n splits), and at each level you do n work to merge things back together.

What it means: Slightly worse than linear. This is the best possible time for comparison-based sorting.

# Sorting — O(n log n)
numbers = [38, 27, 43, 3, 9, 82, 10]
sorted = numbers.sort   # Ruby uses a hybrid sort algorithm — O(n log n)

# Sort by a key — still O(n log n)
users = [
  { name: "Alice", age: 30 },
  { name: "Bob", age: 28 },
  { name: "Charlie", age: 35 }
]
sorted_users = users.sort_by { |u| u[:age] }  # O(n log n)

# Any algorithm that sorts as a step has at least O(n log n)
def find_median(numbers)
  sorted = numbers.sort          # O(n log n) — this dominates
  mid = sorted.length / 2        # O(1)
  sorted[mid]                    # O(1)
end
# Total: O(n log n)

When you see it: Any time you call .sort or .sort_by. Also: merge sort, quicksort (average case), heapsort.

Interview tip: If your solution sorts the data, your time complexity is at least O(n log n), even if the rest of your code is O(n). Sorting is often a bottleneck.

5. O(n²⁾ -- Quadratic Time #

Analogy: A room of 100 people, and everyone needs to shake hands with everyone else. Person 1 shakes 99 hands, person 2 shakes 98, etc. Total handshakes: roughly 100 x 100 = 10,000. Double the people, quadruple the handshakes.

What it means: For every element, you do work proportional to the total number of elements. Usually means nested loops.

# Nested loops — O(n²)
def has_duplicate_pair?(array)
  array.each_with_index do |a, i|          # n iterations
    array.each_with_index do |b, j|        # n iterations for each outer
      next if i == j
      return true if a == b
    end
  end
  false
end
# n * n = n² operations

# Bubble sort — O(n²) (don't use this in practice)
def bubble_sort(array)
  n = array.length
  (n - 1).times do                        # n iterations
    (n - 1).times do |i|                  # n iterations
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
      end
    end
  end
  array
end

# Printing all pairs — O(n²)
def all_pairs(array)
  array.each do |a|           # n
    array.each do |b|         # n
      puts "#{a}, #{b}"
    end
  end
end

When you see it: Nested loops over the same data. Two nested .each calls. Brute force solutions that "check every pair."

Interview tip: O(n²⁾ is often your first working solution (brute force). The interviewer usually then asks: "Can you optimize this?" The answer is almost always: "Use a hash to eliminate the inner loop, bringing it down to O(n)." We'll cover this pattern in Part 6.

6. O(2ⁿ⁾ -- Exponential Time #

Analogy: You're at a fork in the road. Each path leads to two more forks. After 10 forks, there are 1,024 possible paths. After 20 forks, over a million. The paths double at every step.

What it means: The work doubles with each additional input element. Gets brutal fast.

# Naive recursive Fibonacci — O(2^n)
def fib(n)
  return n if n <= 1
  fib(n - 1) + fib(n - 2)   # Two recursive calls per step
end

# fib(5) calls fib(4) and fib(3)
# fib(4) calls fib(3) and fib(2)
# fib(3) calls fib(2) and fib(1)
# ... creates an exponential tree of calls

fib(10)   # 177 calls
fib(20)   # 21,891 calls
fib(30)   # 2,692,537 calls — already slow
fib(40)   # 331,160,281 calls — takes seconds
fib(50)   # Would take minutes to hours

Why it's O(2^n): Each call spawns two more calls. The "tree" of calls has depth n and roughly doubles at each level: 1 + 2 + 4 + 8 + ... + 2ⁿ calls total.

The fix -- memoization, bringing it to O(n):

# Memoized Fibonacci — O(n)
def fib_memo(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)

  memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
  memo[n]
end

fib_memo(50)   # Instant — only 50 calculations

When you see it: Recursive solutions that branch into multiple recursive calls without memoization. Generating all subsets of a set.

Interview tip: If you write a recursive solution and it feels slow, check if you're recomputing the same sub-problems. If yes, add memoization (a hash cache). This is dynamic programming in a nutshell.

7. O(n!) -- Factorial Time #

Analogy: Arranging 10 books on a shelf -- checking every possible order. That's 10! = 3,628,800 arrangements. For 20 books, it's 2,432,902,008,176,640,000 arrangements. Never going to finish.

# Generating all permutations — O(n!)
[1, 2, 3].permutation.to_a
# => [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
# 3! = 6 permutations

# For n = 10, that's 3,628,800 permutations
# For n = 15, that's 1,307,674,368,000 — game over

When you see it: Brute-force solutions to problems like the Traveling Salesman. You'll almost never need this in an interview. Just know it exists and that it's the worst.

Comparison Chart: How They Grow #

Key takeaway from this chart: - O(1) through O(n log n) are "good" -- usable at scale - O(n²⁾ gets painful around n = 10,000 - O(2ⁿ⁾ becomes unusable around n = 30-40 - O(n!) becomes unusable around n = 12-15

In an interview, aim for O(n) or O(n log n). If your first solution is O(n^2), that's fine -- talk through it, then optimize.

Quick Visual Ranking (Best to Worst) #

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
 ⬆️                                                        ⬆️
BEST                                                      WORST

Memorize this order. If someone asks "is O(n log n) better or worse than O(n^2)?" -- O(n log n) is better because it's to the left.

Part 3: How to Analyze Your Own Code #

This is the most important section for interviews. When you write code in a coding interview, you need to be able to look at it and say "this is O(n)" or "this is O(n^2)." Here are the rules.

Rule 1: Count the Loops #

One loop through n items = O(n).

# One loop = O(n)
def find_max(array)
  max = array[0]
  array.each do |num|      # ← one loop through n items
    max = num if num > max
  end
  max
end
# Verdict: O(n)

Rule 2: Nested Loops Multiply #

A loop inside a loop = O(n) x O(n) = O(n^2).

# Nested loops = O(n²)
def all_pairs(array)
  result = []
  array.each do |a|            # ← outer loop: n
    array.each do |b|          # ← inner loop: n (for EACH outer iteration)
      result << [a, b]
    end
  end
  result
end
# n * n = O(n²)

Three nested loops = O(n^3). Four = O(n^4). Each nesting level multiplies.

# Three nested loops = O(n³) — rare but be aware
def all_triples(array)
  array.each do |a|            # n
    array.each do |b|          # n
      array.each do |c|        # n
        puts "#{a}, #{b}, #{c}"
      end
    end
  end
end
# n * n * n = O(n³)

Rule 3: Sequential Code -- Take the Biggest #

When you have code blocks one after another (not nested), the total complexity is the biggest one.

def process(array)
  # Step 1: Find the max — O(n)
  max = array.max

  # Step 2: Sort the array — O(n log n)
  sorted = array.sort

  # Step 3: Print each element — O(n)
  sorted.each { |x| puts x }
end
# O(n) + O(n log n) + O(n) = O(n log n)
# The O(n log n) dominates, so we say O(n log n)

Think of it like: if you walk for 10 minutes and then drive for 3 hours, the total trip time is "about 3 hours." The walking doesn't meaningfully change the total.

Rule 4: Drop Constants and Lower-Order Terms #

# Two sequential loops through the same array
def process(array)
  array.each { |x| puts x }    # O(n)
  array.each { |x| puts x }    # O(n)
end
# O(n) + O(n) = O(2n) → drop the constant → O(n)

# Loop with fixed inner work
def check_all(array)
  array.each do |item|          # O(n)
    5.times { puts item }       # O(5) = O(1) — it's a constant, not based on n
  end
end
# O(n) * O(1) = O(n)

The principle: Constants don't change the shape of growth. O(5n) and O(n) both draw a straight line on a graph. O(100n) is still a straight line. The slope is different, but the shape is the same.

Rule 5: Hash/Set Lookups Are O(1) #

This is the most important optimization tool in your toolbox.

# BAD: Using array .include? — O(n) per lookup
def has_common_element_slow?(arr1, arr2)
  arr1.each do |item|                   # O(n)
    return true if arr2.include?(item)  # O(n) — scans arr2 each time!
  end
  false
end
# O(n) * O(n) = O(n²) — BAD

# GOOD: Convert to a Set first — O(1) per lookup
require 'set'
def has_common_element_fast?(arr1, arr2)
  set = arr2.to_set                     # O(n) — build the set once
  arr1.each do |item|                   # O(n)
    return true if set.include?(item)   # O(1) — set lookup!
  end
  false
end
# O(n) + O(n) * O(1) = O(n) — GOOD

# Equally GOOD: Use a Hash instead of Set
def has_common_element_hash?(arr1, arr2)
  lookup = {}
  arr2.each { |item| lookup[item] = true }  # O(n) — build hash
  arr1.each do |item|                        # O(n)
    return true if lookup[item]              # O(1) — hash lookup
  end
  false
end
# O(n) — same performance as Set version

This is the #1 interview optimization pattern: Replace an O(n) search (like array.include?) with an O(1) hash/set lookup. It's the answer to at least half of all "optimize this" interview questions.

Rule 6: Sorting Is O(n log n) #

If your solution sorts the data, that step alone costs O(n log n). Everything after sorting needs to be at most O(n) for the total to stay O(n log n).

def find_closest_pair(numbers)
  sorted = numbers.sort                    # O(n log n)
  min_diff = Float::INFINITY
  closest = nil

  (0...sorted.length - 1).each do |i|      # O(n)
    diff = (sorted[i + 1] - sorted[i]).abs
    if diff < min_diff
      min_diff = diff
      closest = [sorted[i], sorted[i + 1]]
    end
  end

  closest
end
# O(n log n) + O(n) = O(n log n)

Worked Examples: Analyzing Ruby Code Step by Step #

Let's practice. For each snippet, I'll walk through exactly how to figure out the Big O.

Example 1:

def find_duplicates(array)
  seen = {}
  duplicates = []

  array.each do |item|              # How many times? n times
    if seen[item]                   # Hash lookup: O(1)
      duplicates << item            # Array push: O(1)
    else
      seen[item] = true             # Hash insert: O(1)
    end
  end

  duplicates
end

Analysis: - One loop: n iterations - Inside the loop: only O(1) operations (hash lookup, hash insert, array push) - n * O(1) = O(n) - Verdict: O(n)

Example 2:

def intersection(arr1, arr2)
  result = []
  arr1.each do |a|                  # n iterations (where n = arr1.length)
    arr2.each do |b|                # m iterations (where m = arr2.length)
      result << a if a == b
    end
  end
  result
end

Analysis: - Outer loop: n iterations - Inner loop: m iterations for each outer iteration - n * m operations total - If both arrays are about the same size, n * n = O(n²⁾ - Verdict: O(n * m), or O(n²⁾ if arrays are similar size

Example 3:

def process_and_sort(array)
  # Step 1
  doubled = array.map { |x| x * 2 }          # O(n)

  # Step 2
  sorted = doubled.sort                       # O(n log n)

  # Step 3
  sorted.select { |x| x > 10 }               # O(n)
end

Analysis: - Step 1: O(n) -- one pass through the array - Step 2: O(n log n) -- sorting - Step 3: O(n) -- one pass through the array - Sequential steps, take the biggest: O(n log n) - Verdict: O(n log n)

Example 4:

def nested_with_hash(array)
  counts = {}

  # Pass 1: Count occurrences
  array.each do |item|               # O(n)
    counts[item] = (counts[item] || 0) + 1
  end

  # Pass 2: Find items appearing more than once
  result = []
  counts.each do |item, count|       # O(n) at most (at most n unique items)
    result << item if count > 1
  end

  result
end

Analysis: - Pass 1: n iterations, O(1) work each = O(n) - Pass 2: at most n iterations, O(1) work each = O(n) - Sequential: O(n) + O(n) = O(2n) = O(n) - Verdict: O(n)

Example 5:

def sort_and_binary_search(array, target)
  sorted = array.sort                           # O(n log n)

  low = 0
  high = sorted.length - 1

  while low <= high                             # O(log n)
    mid = (low + high) / 2
    if sorted[mid] == target
      return true
    elsif sorted[mid] < target
      low = mid + 1
    else
      high = mid - 1
    end
  end

  false
end

Analysis: - Sort: O(n log n) - Binary search: O(log n) - Sequential: O(n log n) + O(log n) = O(n log n) - Verdict: O(n log n)

Note: If you only need to search once, using a hash would be O(n) which is better. But if you need to search many times in the same array, sorting once O(n log n) + searching k times O(k log n) can be better than building a hash.

Example 6:

def mystery(n)
  i = 1
  while i < n
    puts i
    i *= 2         # i doubles each iteration: 1, 2, 4, 8, 16, ...
  end
end

Analysis: - How many times does the loop run? i starts at 1 and doubles until it reaches n. - 1, 2, 4, 8, ... 2^k = n, so k = log2(n) iterations - Verdict: O(log n)

Whenever you see a loop variable that doubles (or halves) each iteration, think O(log n).

Part 4: Space Complexity (Brief) #

Space complexity answers: "How much extra memory does my code use as input grows?"

It works the same way as time complexity, but instead of counting operations, we count how much memory we allocate.

The Basics #

# O(1) space — using a fixed number of variables
def find_max(array)
  max = array[0]          # One variable — O(1)
  array.each do |num|
    max = num if num > max
  end
  max
end
# We use the same `max` variable regardless of array size.
# Space: O(1)

# O(n) space — creating a new array proportional to input
def double_all(array)
  result = []                   # New array that will hold n items
  array.each { |x| result << x * 2 }
  result
end
# The `result` array grows with the input.
# Space: O(n)

# O(n) space — creating a hash
def count_chars(string)
  counts = {}                   # Hash with at most n entries
  string.each_char do |char|
    counts[char] = (counts[char] || 0) + 1
  end
  counts
end
# Space: O(n) — or more precisely O(k) where k is unique characters
# But for Big O purposes, k <= n, so O(n)

# O(1) space — modifying array in place
def reverse_in_place!(array)
  left = 0
  right = array.length - 1
  while left < right
    array[left], array[right] = array[right], array[left]
    left += 1
    right -= 1
  end
  array
end
# No new data structures created. Two pointer variables = O(1).
# Space: O(1)

Quick Rules for Space #

Interview Tip #

When the interviewer asks about complexity, mention both:

"The time complexity is O(n) and the space complexity is O(n) because we're using a hash to store the counts."

Or if you're proud of your space efficiency:

"The time complexity is O(n) and the space complexity is O(1) because we're doing this in place with two pointers."

Part 5: Big O Patterns for Common Ruby Operations #

Use this as a quick reference. Bookmark this section.

Array Operations #

Gotcha alert: array.shift and array.unshift are O(n), not O(1). If you need to add/remove from both ends efficiently, use a different data structure.

Hash Operations #

Key insight: Hash operations on keys are O(1). Hash operations on values are O(n). If you need to look up by value, build a reverse hash.

String Operations #

Gotcha: String concatenation with + in a loop is O(n²⁾ total because each + creates a new string. Use an array and .join instead:

# BAD — O(n²) total because of repeated string copying
result = ""
words.each { |word| result += word }  # Each += copies the entire result so far

# GOOD — O(n) total
result = words.join  # One allocation, one pass

Set Operations #

When to use Set vs Hash: Use a Set when you only care about "is this item present?" Use a Hash when you need to associate a key with a value (like counting occurrences).

Enumerable Methods #

Important: Chaining enumerables multiplies by the number of passes:

# This does 3 separate passes — but it's still O(n) total!
array.select { |x| x > 0 }   # O(n)
     .map { |x| x * 2 }      # O(n) — but on filtered array (still at most n)
     .sort                    # O(n log n)
# Total: O(n) + O(n) + O(n log n) = O(n log n)

Each chain is a separate pass, but they're sequential (not nested), so you take the biggest.

Part 6: Interview Cheat Sheet #

How to Talk About Big O (Exact Phrases) #

Use these sentence templates in coding interviews. Practice saying them out loud.

Stating complexity:

"The time complexity of this solution is O(n) because we iterate through the array once."

"This runs in O(n log n) time because we sort the array first, which dominates."

"The space complexity is O(n) because we create a hash that could store up to n entries."

Explaining brute force:

"The brute force approach would be O(n squared) because of the nested loops -- for each element, we'd scan the entire array. Let me optimize using a hash."

Explaining optimization:

"We can bring this down from O(n squared) to O(n) by using a hash for constant-time lookups instead of scanning the array."

"By sorting first, we can use binary search, which brings lookups from O(n) to O(log n)."

Discussing trade-offs:

"We're trading space for time here -- the hash uses O(n) extra space, but it brings our time complexity from O(n squared) down to O(n)."

If you're unsure:

"Let me think about the complexity... we have one loop that does n iterations, and inside the loop the hash lookup is O(1), so the overall time is O(n)."

The Interview Flow #

1. Read the problem. Ask clarifying questions.
2. Talk through brute force first. "The simplest approach would be... this would be O(n^2)."
3. Code the brute force (or skip to optimized if you see it immediately).
4. Optimize. "We can do better by using a hash..."
5. State the final complexity. "This is O(n) time, O(n) space."
6. Test with examples. Walk through your code with a small input.

The 4 Most Common Optimization Patterns #

Pattern 1: Hash Map (O(n²⁾ to O(n)) #

The most common pattern by far. Replace the inner loop with a hash lookup.

# BEFORE: O(n²) — nested loop to find pairs
def two_sum_slow(nums, target)
  nums.each_with_index do |a, i|
    nums.each_with_index do |b, j|
      return [i, j] if i != j && a + b == target
    end
  end
end

# AFTER: O(n) — hash stores what we've seen
def two_sum_fast(nums, target)
  seen = {}  # value => index
  nums.each_with_index do |num, i|
    complement = target - num
    return [seen[complement], i] if seen.key?(complement)
    seen[num] = i
  end
end

When to use: Any problem where you're searching for a match, complement, or duplicate. "Does this element exist in the data?" questions.

Pattern 2: Two Pointers (O(n²⁾ to O(n)) #

Use two pointers that move toward each other (or in the same direction) through sorted data.

# Find two numbers in a SORTED array that sum to target
def two_sum_sorted(sorted_nums, target)
  left = 0
  right = sorted_nums.length - 1

  while left < right
    current_sum = sorted_nums[left] + sorted_nums[right]

    if current_sum == target
      return [left, right]
    elsif current_sum < target
      left += 1       # Need a bigger sum, move left pointer right
    else
      right -= 1      # Need a smaller sum, move right pointer left
    end
  end

  nil  # No pair found
end

When to use: Problems on sorted arrays. Finding pairs. Palindrome checking. Container with most water.

Time: O(n) because each pointer moves at most n steps total. Space: O(1) because we only use two variables.

Pattern 3: Sliding Window (O(n²⁾ to O(n)) #

Maintain a "window" that slides through the data. Expand and contract the window as needed.

# Find the longest substring without repeating characters
def longest_unique_substring(s)
  char_index = {}      # Track last seen index of each character
  max_length = 0
  start = 0            # Left edge of window

  s.each_char.with_index do |char, i|
    # If this char is already in our window, move the start past it
    if char_index.key?(char) && char_index[char] >= start
      start = char_index[char] + 1
    end

    char_index[char] = i
    current_length = i - start + 1
    max_length = current_length if current_length > max_length
  end

  max_length
end

longest_unique_substring("abcabcbb")  # => 3 ("abc")

When to use: "Longest/shortest substring/subarray with condition X." Contiguous sequence problems.

Time: O(n) because we traverse the string once. Space: O(k) where k is the character set size (at most 26 for lowercase letters, or 128 for ASCII).

Pattern 4: Sort First (O(n²⁾ to O(n log n)) #

Sometimes sorting the data first makes the remaining problem much easier.

# Find if any two elements in the array are within distance k of each other
def has_close_pair_slow?(array, k)
  # Brute force: O(n²)
  array.each_with_index do |a, i|
    array.each_with_index do |b, j|
      return true if i != j && (a - b).abs <= k
    end
  end
  false
end

def has_close_pair_fast?(array, k)
  # Sort first: O(n log n) + O(n) = O(n log n)
  sorted = array.sort
  (0...sorted.length - 1).each do |i|
    return true if (sorted[i + 1] - sorted[i]).abs <= k
  end
  false
end

When to use: Finding pairs with a certain relationship. Grouping similar items. Finding medians, ranges, or closest values. Anytime sorted order helps.

5 Mini Problems: "What's the Big O?" #

Test yourself. Cover the answer and try to figure it out before looking.

Problem 1: ruby def mystery1(array) array.each do |x| puts x end array.each do |x| puts x * 2 end end

Problem 2: ruby def mystery2(array) array.sort.first end

Problem 3: ruby def mystery3(array) hash = array.tally hash.max_by { |_k, v| v } end

Problem 4: ruby def mystery4(array) result = [] array.each do |x| result << x unless result.include?(x) end result end

Problem 5: ruby def mystery5(string) chars = string.chars.sort chars.chunk_while { |a, b| a == b }.map(&:first) end

Part 7: Practice Problems (Ranked by Difficulty) #

These are the kinds of problems you'll see in coding interviews. For each one, we show the brute force approach, then the optimized solution, with full Big O analysis.

Problem 1 (Easy): Find Duplicates in an Array #

Problem: Given an array of integers, return an array of all values that appear more than once.

find_duplicates([1, 3, 4, 2, 1, 4, 5])  # => [1, 4]
find_duplicates([1, 2, 3])                # => []
find_duplicates([1, 1, 1, 1])             # => [1]

Brute Force: O(n²⁾ #

def find_duplicates_brute(array)
  duplicates = []

  array.each_with_index do |a, i|            # O(n)
    array.each_with_index do |b, j|          # O(n)
      if i < j && a == b && !duplicates.include?(a)
        duplicates << a
      end
    end
  end

  duplicates
end

Analysis: - Outer loop: n iterations - Inner loop: n iterations for each - Plus duplicates.include? is O(d) where d is duplicates found (small, but still) - Time: O(n^2). Space: O(d) where d is the number of duplicates.

Why it's slow: For every element, we compare it against every other element. With 10,000 items, that's 100,000,000 comparisons.

Optimized: O(n) with Hash #

def find_duplicates(array)
  counts = {}
  duplicates = []

  array.each do |item|                    # O(n) — one pass
    counts[item] = (counts[item] || 0) + 1
  end

  counts.each do |item, count|            # O(n) at most
    duplicates << item if count > 1
  end

  duplicates
end

Analysis: - First loop: n iterations, O(1) work per iteration (hash operations) = O(n) - Second loop: at most n iterations (at most n unique items) = O(n) - Time: O(n). Space: O(n) for the hash.

Even more concise Ruby (same Big O):

def find_duplicates(array)
  array.tally.select { |_item, count| count > 1 }.keys
end

Why this is O(n): .tally is O(n), .select on the resulting hash is O(n), .keys is O(n). Three sequential O(n) operations = O(n).

How to explain in the interview:

"The brute force would compare every pair, which is O(n squared). Instead, I'm using a hash to count occurrences in a single pass, which gives us O(n) time. The trade-off is O(n) space for the hash."

Problem 2 (Easy): Two Sum #

Problem: Given an array of integers and a target sum, return the indices of two numbers that add up to the target. Assume exactly one solution exists.

two_sum([2, 7, 11, 15], 9)   # => [0, 1] because 2 + 7 = 9
two_sum([3, 2, 4], 6)         # => [1, 2] because 2 + 4 = 6

Brute Force: O(n²⁾ #

def two_sum_brute(nums, target)
  nums.each_with_index do |a, i|          # O(n)
    nums.each_with_index do |b, j|        # O(n)
      return [i, j] if i < j && a + b == target
    end
  end
end

Analysis: - Nested loops checking every pair - Time: O(n^2). Space: O(1).

Optimized: O(n) with Hash #

def two_sum(nums, target)
  seen = {}  # Maps value => index

  nums.each_with_index do |num, i|        # O(n) — one pass
    complement = target - num             # O(1) — arithmetic

    if seen.key?(complement)              # O(1) — hash lookup
      return [seen[complement], i]
    end

    seen[num] = i                         # O(1) — hash insert
  end
end

Analysis: - One loop: n iterations - Inside: only O(1) operations (arithmetic, hash lookup, hash insert) - Time: O(n). Space: O(n) for the hash.

Why it works: For each number, we calculate what its "partner" would need to be (target - num). Then we check if we've already seen that partner. If yes, we found our pair. If no, we record the current number for future lookups.

How to explain in the interview:

"Instead of checking every pair with nested loops, which would be O(n squared), I use a hash to remember what I've seen. For each number, I check if its complement (target minus current number) is already in the hash. This gives us O(n) time with O(n) space."

Problem 3 (Medium): First Non-Repeating Character #

Problem: Given a string, find the first character that doesn't repeat. Return nil if all characters repeat.

first_unique("aabccbd")     # => "d"
first_unique("aabbcc")      # => nil
first_unique("abcabc")      # => nil
first_unique("abcdef")      # => "a"

Solution: O(n) with Hash #

def first_unique(string)
  # Pass 1: Count every character
  counts = {}
  string.each_char do |char|              # O(n)
    counts[char] = (counts[char] || 0) + 1
  end

  # Pass 2: Find first character with count 1
  string.each_char do |char|              # O(n)
    return char if counts[char] == 1
  end

  nil
end

Analysis: - Pass 1: O(n) to count all characters - Pass 2: O(n) in worst case (might check all characters before finding unique one) - Time: O(n). Space: O(k) where k is the number of unique characters (at most 26 for lowercase letters).

Concise Ruby version (same Big O):

def first_unique(string)
  counts = string.chars.tally                     # O(n)
  string.each_char.find { |c| counts[c] == 1 }   # O(n)
end

Why we need two passes: We can't know if a character is unique until we've seen the entire string. The character "a" might appear once early on but repeat later. So pass 1 gets the full picture, pass 2 finds the first unique one in the original order.

How to explain in the interview:

"I do two passes. First, I count every character using a hash -- that's O(n). Then I walk through the string again in order and return the first character with a count of 1. Total is O(n) time and O(1) space since the hash is bounded by the alphabet size."

(Notice how you can argue the space is O(1) here because the hash has at most 26 entries for lowercase English letters -- a constant. This is a nice point to make in an interview.)

Problem 4 (Medium): Group Anagrams #

Problem: Given an array of strings, group the anagrams together.

group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
# => [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Solution: O(n * k log k) with Hash #

def group_anagrams(words)
  groups = Hash.new { |h, k| h[k] = [] }

  words.each do |word|                     # O(n) — iterate n words
    key = word.chars.sort.join             # O(k log k) — sort k characters
    groups[key] << word                    # O(1) — hash insert
  end

  groups.values
end

Analysis: - Outer loop: n iterations (one per word) - For each word: sort its characters. If the word has k characters, sorting is O(k log k) - Hash insert: O(1) - Total: n words * (k log k) sort per word = O(n * k log k) - Space: O(n * k) to store all words in the hash

How it works: Two words are anagrams if they contain the same letters in any order. So "eat", "tea", and "ate" all become "aet" when sorted. We use the sorted version as a hash key, and all anagrams end up in the same bucket.

Alternative with O(n * k) time (if you want to impress):

Instead of sorting each word (O(k log k)), you can count the letters to build a key (O(k)):

def group_anagrams(words)
  groups = Hash.new { |h, k| h[k] = [] }

  words.each do |word|
    # Count letters instead of sorting: O(k) instead of O(k log k)
    key = Array.new(26, 0)
    word.each_char { |c| key[c.ord - 'a'.ord] += 1 }
    groups[key] << word
  end

  groups.values
end
# Time: O(n * k) where n is number of words, k is max word length

How to explain in the interview:

"I use the sorted characters of each word as a hash key. Anagrams will sort to the same key, so they'll all group together. Time complexity is O(n times k-log-k) where n is the number of words and k is the average word length, because we sort each word's characters. Space is O(n times k) to store all the groups."

Problem 5 (Medium): Longest Substring Without Repeating Characters #

Problem: Given a string, find the length of the longest substring without repeating characters.

longest_unique_substring("abcabcbb")    # => 3 ("abc")
longest_unique_substring("bbbbb")       # => 1 ("b")
longest_unique_substring("pwwkew")      # => 3 ("wke")
longest_unique_substring("")            # => 0

Brute Force: O(n³⁾ #

def longest_unique_substring_brute(s)
  max_len = 0

  (0...s.length).each do |i|                    # O(n)
    (i...s.length).each do |j|                  # O(n)
      substring = s[i..j]
      if substring.chars.uniq.length == substring.length  # O(n)
        max_len = [max_len, substring.length].max
      end
    end
  end

  max_len
end

Analysis: Three nested levels of work = O(n³⁾. Way too slow.

Optimized: O(n) Sliding Window #

def longest_unique_substring(s)
  return 0 if s.empty?

  char_index = {}      # Stores the last seen index of each character
  max_length = 0
  window_start = 0     # Left edge of our sliding window

  s.each_char.with_index do |char, i|        # O(n) — right edge moves right
    # If we've seen this character before, AND it's inside our current window,
    # move the window start past the previous occurrence
    if char_index.key?(char) && char_index[char] >= window_start
      window_start = char_index[char] + 1
    end

    char_index[char] = i                     # Update last seen position
    current_length = i - window_start + 1    # Current window size
    max_length = [max_length, current_length].max
  end

  max_length
end

Analysis: - One loop through the string: O(n) - Inside the loop: hash lookups and inserts, all O(1) - Time: O(n). Space: O(k) where k is the character set size (at most 128 for ASCII).

How the sliding window works (trace through "abcabcbb"):

Step 0: char='a', window="a",     start=0, max=1, hash={a:0}
Step 1: char='b', window="ab",    start=0, max=2, hash={a:0,b:1}
Step 2: char='c', window="abc",   start=0, max=3, hash={a:0,b:1,c:2}
Step 3: char='a', 'a' seen at 0 (inside window) → start=1
        window="bca",  start=1, max=3, hash={a:3,b:1,c:2}
Step 4: char='b', 'b' seen at 1 (inside window) → start=2
        window="cab",  start=2, max=3, hash={a:3,b:4,c:2}
Step 5: char='c', 'c' seen at 2 (inside window) → start=3
        window="abc",  start=3, max=3, hash={a:3,b:4,c:5}
Step 6: char='b', 'b' seen at 4 (inside window) → start=5
        window="cb",   start=5, max=3, hash={a:3,b:6,c:5}
Step 7: char='b', 'b' seen at 6 (inside window) → start=7
        window="b",    start=7, max=3, hash={a:3,b:7,c:5}

Answer: 3

How to explain in the interview:

"I use a sliding window approach. I maintain a window of unique characters by tracking the start position and each character's last seen index in a hash. When I encounter a repeated character, I move the window start past the previous occurrence. This way, each character is processed exactly once, giving us O(n) time and O(k) space where k is the character set size."

Quick Reference Card (Print This) #

COMPLEXITY RANKING (best to worst):
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

ANALYSIS RULES:
1. One loop = O(n)
2. Nested loops = multiply: O(n²)
3. Sequential blocks = take the biggest
4. Drop constants: O(2n) → O(n)
5. Hash/Set lookup = O(1)
6. Sorting = O(n log n)

TOP OPTIMIZATION PATTERNS:
1. Hash map: O(n²) → O(n) — replace inner loop with hash lookup
2. Two pointers: O(n²) → O(n) — works on sorted data
3. Sliding window: O(n²) → O(n) — for substring/subarray problems
4. Sort first: O(n²) → O(n log n) — when sorted order helps

WHAT TO SAY:
"The time complexity is O(___) because ___."
"The space complexity is O(___) because ___."
"We can optimize from O(n²) to O(n) by using a hash."
"We're trading space for time — O(n) extra space for O(n) time."

RUBY GOTCHAS:
- array.include? is O(n), NOT O(1) — use a Set or Hash
- array.shift / unshift is O(n), NOT O(1)
- string + string in a loop is O(n²) total — use .join
- array.sort.first is O(n log n) — use .min for O(n)

You've got this. The concepts are simpler than they look, and you already think this way when optimizing Rails queries. Now you just have the vocabulary to explain it in an interview.