DEV Community: Shankar L

Sliding Window Technique : Solving Subarray and Substring Problems Efficiently

Shankar L — Sat, 19 Sep 2026 11:09:00 +0000

Why should you care?

Many programming problems involve finding something inside a contiguous portion of an array or string.

For example:

Find the maximum sum of k consecutive elements.
Find the longest substring without repeating characters.
Find the smallest subarray whose sum reaches a target.
Find the number of subarrays satisfying a condition.
Find the longest sequence containing at most k distinct values.

A naive solution often checks every possible subarray.

For an array of size n, there can be:

n(n + 1) / 2

different subarrays.

That's:

O(n²)

The Sliding Window Technique can often reduce these problems to:

O(n)

The core idea is:

Instead of repeatedly calculating overlapping ranges from scratch, maintain a window and slide it across the data.

The Problem

Suppose we have:

[2, 1, 5, 1, 3, 2]

and we want:

Find the maximum sum of 3 consecutive elements.

A brute-force solution examines:

[2, 1, 5] → 8
[1, 5, 1] → 7
[5, 1, 3] → 9
[1, 3, 2] → 6

Answer:

But notice what happens between consecutive windows:

[2, 1, 5]
     ↓
[1, 5, 1]

We don't need to calculate the second sum from scratch.

The old window was:

2 + 1 + 5 = 8

Remove:

Add:

Therefore:

8 - 2 + 1 = 7

This is the fundamental idea behind the Sliding Window Technique.

The Concept

A sliding window represents a range of elements currently being considered.

For example:

Array:
[2, 1, 5, 1, 3, 2]
 ↑        ↑
left     right

The elements between left and right form the current window.

Instead of repeatedly creating new subarrays, we move the boundaries:

Window 1:

[2, 1, 5] 1  3  2
 ↑     ↑
 L     R


Window 2:

 2 [1, 5, 1] 3  2
   ↑     ↑
   L     R


Window 3:

 2  1 [5, 1, 3] 2
      ↑     ↑
      L     R

The window slides from left to right.

Simple Explanation

Imagine looking through a window on a moving train.

You can only see a few objects at a time.

As the train moves:

Old view:
[A B C]

Move:

[B C D]

Move:

[C D E]

You don't completely forget everything you saw.

You:

Remove A
Add D

The Sliding Window Technique works the same way.

Remove something from the left
+
Add something on the right
=
Move the window efficiently

Real-world Analogy

Imagine monitoring website traffic every 5 minutes.

Suppose the data is:

10 20 15 30 25 40

You want the total traffic for every 3-minute window.

First:

10 + 20 + 15 = 45

Move one position:

20 + 15 + 30

Instead of recalculating:

45 - 10 + 30 = 65

Move again:

65 - 20 + 25 = 70

The window continuously moves while maintaining the necessary information.

That's why the technique is so efficient.

Code Example

Let's solve the fixed-size maximum-sum problem.

Given:

[2, 1, 5, 1, 3, 2]

Find the maximum sum of k = 3 consecutive elements.

Brute Force

A straightforward solution is:

public static int maxSumBruteForce(int[] nums, int k) {

    int maxSum = Integer.MIN_VALUE;

    for (int i = 0; i <= nums.length - k; i++) {

        int sum = 0;

        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }

        maxSum = Math.max(maxSum, sum);
    }

    return maxSum;
}

Complexity:

Time: O(n × k)

If k is large, this becomes expensive.

Sliding Window Solution

public static int maxSum(int[] nums, int k) {

    int windowSum = 0;

    // Build the first window
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    int maxSum = windowSum;

    // Slide the window
    for (int right = k; right < nums.length; right++) {

        windowSum += nums[right];
        windowSum -= nums[right - k];

        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

For:

[2, 1, 5, 1, 3, 2]

the windows are:

[2, 1, 5] → 8
[1, 5, 1] → 7
[5, 1, 3] → 9
[1, 3, 2] → 6

Result:

Complexity

Time:  O(n)
Space: O(1)

We process each element only a constant number of times.

Common Mistakes

Mistake 1: Recalculating the entire window

This defeats the purpose of the technique.

Bad:

Window 1 → calculate everything
Window 2 → calculate everything again
Window 3 → calculate everything again

Instead:

New Window = Old Window - Removed Element + Added Element

Reuse what you've already calculated.

Mistake 2: Confusing subarray with subsequence

Sliding Window generally works with contiguous ranges.

For:

[1, 2, 3, 4]

These are subarrays:

[1, 2]
[2, 3]
[3, 4]
[1, 2, 3]

But:

[1, 3]

is not a contiguous subarray.

It is a subsequence.

This distinction matters.

Mistake 3: Moving both pointers incorrectly

In variable-size windows, we often use:

left
right

The right pointer expands the window:

right++

The left pointer shrinks it:

left++

A common pattern is:

while (conditionIsInvalid()) {
    // remove nums[left]
    left++;
}

Incorrect pointer movement can cause:

Missing valid windows
Infinite loops
Incorrect answers

Advanced Notes

1. Fixed-Size Sliding Window

The easiest version has a window of exactly k elements.

Example:

Find maximum sum of k consecutive elements.

The window always has:

size = k

Pattern:

for (int right = k; right < n; right++) {

    window += nums[right];
    window -= nums[right - k];

}

The general idea:

Add right
Remove left

2. Variable-Size Sliding Window

Sometimes the window size is not fixed.

Instead, we expand and shrink based on a condition.

For example:

Find the smallest subarray whose sum is at least 7.

Input:

[2, 3, 1, 2, 4, 3]

We can use:

left = 0
right = 0

Expand:

[2]          sum = 2
[2,3]        sum = 5
[2,3,1]      sum = 6
[2,3,1,2]    sum = 8

Now the condition is satisfied.

Shrink from the left:

[3,1,2]      sum = 6

Too small.

So expand again.

Eventually:

[4,3]

has sum:

Length:

So the answer is 2.

3. Variable Window Code

public static int minSubArrayLen(int target, int[] nums) {

    int left = 0;
    int sum = 0;
    int minLength = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {

        sum += nums[right];

        while (sum >= target) {

            minLength = Math.min(
                minLength,
                right - left + 1
            );

            sum -= nums[left];
            left++;
        }
    }

    return minLength == Integer.MAX_VALUE
            ? 0
            : minLength;
}

For:

target = 7
nums = [2,3,1,2,4,3]

Result:

because:

[4,3]

is the smallest valid window.

4. Two Pointer Relationship

Sliding Window is closely related to the Two Pointer Technique.

Typical structure:

left  → beginning of window
right → end of window

Both move toward the right:

left  →→→
right →→→

This often gives linear complexity.

You can think of Sliding Window as a specialized form of two pointers where the pointers define a contiguous range.

5. Longest Substring Without Repeating Characters

Sliding Window becomes particularly powerful with strings.

Consider:

"abcabcbb"

We want the longest substring without repeating characters.

The answer is:

"abc"

Length:

We can maintain a window:

[a b c]

When another a appears:

[a b c a]

the window becomes invalid.

So we move left forward until the duplicate is removed.

Using a HashSet:

import java.util.*;

public class Main {

    static int longestUniqueSubstring(String s) {

        Set<Character> set = new HashSet<>();

        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {

            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }

            set.add(s.charAt(right));

            maxLength = Math.max(
                maxLength,
                right - left + 1
            );
        }

        return maxLength;
    }

    public static void main(String[] args) {

        System.out.println(
            longestUniqueSubstring("abcabcbb")
        );
    }
}

Output:

Complexity:

Time: O(n)
Space: O(min(n, character-set-size))

The important pattern is:

Expand
 ↓
Constraint violated?
 ↓
Shrink
 ↓
Constraint satisfied
 ↓
Continue

6. Frequency Maps

Many string problems require knowing how frequently characters occur.

For example:

Find the smallest substring containing all characters of a target string.

A frequency map can maintain the window state:

Map<Character, Integer>

As the window expands:

Add character

As it shrinks:

Remove character

This combination is extremely common:

Sliding Window
+
HashMap

7. At Most K Distinct Characters

Consider:

"eceba"

Suppose:

k = 2

Find the longest substring containing at most two distinct characters.

We maintain:

left
right
frequency map

When the number of distinct characters becomes greater than k:

while (distinct > k) {
    remove s[left]
    left++
}

This pattern appears in many interview problems.

8. Maximum/Minimum in a Sliding Window

Some problems ask:

Find the maximum value in every window of size k.

For:

[1, 3, -1, -3, 5, 3, 6, 7]

with:

k = 3

the result is:

[3, 3, 5, 5, 6, 7]

A simple sliding window would repeatedly scan the window, giving:

O(nk)

But we can use a Deque to maintain candidates for the maximum.

Then the solution becomes:

O(n)

This connects the Sliding Window Technique with another data structure you have already learned: the Deque.

9. When Sliding Window Works

Sliding Window is especially useful when:

The problem involves:
    ↓
Contiguous subarray
OR
Contiguous substring

and we can efficiently maintain the information needed for the current window.

Typical clues include:

"subarray"
"substring"
"consecutive"
"contiguous"
"longest"
"shortest"
"maximum"
"minimum"
"at most K"
"exactly K"

These should immediately make you consider Sliding Window.

10. When Sliding Window Doesn't Work

Sliding Window is not a universal technique.

For example, arbitrary subsequences don't naturally form a single contiguous window.

Also, some conditions cannot be maintained efficiently when moving the window.

Always ask:

Can I update the answer when one element enters and another leaves?

If yes, Sliding Window may work.

11. Time Complexity

The most important property of variable-size Sliding Window is that the pointers generally move only forward.

For example:

right → n movements
left  → n movements

Therefore:

Total movements ≤ 2n

So:

Time = O(n)

Even though there is a nested while loop:

for (...) {

    while (...) {
        left++;
    }
}

the complexity is usually still O(n).

Why?

Because left doesn't reset.

It moves forward at most n times.

This is an important example of amortized analysis.

12. A General Sliding Window Template

For variable-size problems, remember this structure:

int left = 0;

for (int right = 0; right < n; right++) {

    // Add nums[right]
    addToWindow(nums[right]);

    while (windowIsInvalid()) {

        // Remove nums[left]
        removeFromWindow(nums[left]);

        left++;
    }

    // Window is valid here
    updateAnswer();
}

Think of it as:

EXPAND
  ↓
CHECK
  ↓
SHRINK if necessary
  ↓
RECORD ANSWER

This template solves a surprisingly large number of problems.

The Bigger Picture

Your algorithmic progression is now moving from individual algorithms toward problem-solving patterns:

Arrays
   ↓
Linked Lists
   ↓
Stacks / Queues
   ↓
Trees / Graphs
   ↓
Searching
   ↓
Sorting
   ↓
DFS / BFS
   ↓
Greedy
   ↓
Dynamic Programming
   ↓
Backtracking
   ↓
Sliding Window

Sliding Window is different from algorithms such as Merge Sort or BFS.

It is better understood as a problem-solving technique.

You recognize a particular structure in a problem:

Contiguous range
      +
Information about the range
      +
Efficient update when range moves
      ↓
Sliding Window

It also connects multiple concepts you've already learned:

Sliding Window
      +
Two Pointers
      +
Hash Tables
      +
Queues / Deques
      ↓
Efficient Range Processing

This is an important transition toward learning common coding interview patterns.

The Most Important Mental Model

Remember:

        RIGHT
          ↓
[A B C D E F G H]
 ↑       ↑
LEFT    WINDOW

Expand →

When the window becomes invalid:

        RIGHT
          ↓
[A B C D E F G H]
 ↑       ↑
LEFT    WINDOW

Shrink ←

The complete mental model is:

Expand the window to explore more elements. When the window violates the condition, shrink it from the left until it becomes valid again.

For fixed-size windows:

ADD RIGHT
REMOVE LEFT

For variable-size windows:

EXPAND RIGHT
SHRINK LEFT WHEN NEEDED

That distinction is enough to recognize many Sliding Window problems.

Summary

The Sliding Window Technique efficiently processes contiguous portions of arrays and strings.

Key ideas:

A window represents a contiguous range.
Instead of recalculating each range, maintain the current window's state.
Fixed-size windows always contain k elements.
Variable-size windows expand and shrink according to a condition.
Two pointers usually represent the left and right boundaries.
HashMaps and HashSets are frequently used with Sliding Window.
Deques can efficiently solve advanced window maximum/minimum problems.
Many variable-size solutions run in O(n) because each pointer moves forward at most n times.
Common applications include maximum sums, minimum subarrays, longest substrings, frequency problems, and constraint-based ranges.
Sliding Window is particularly useful when the problem involves contiguous or consecutive elements.

Backtracking : Exploring Choices and Undoing Wrong Decisions

Shankar L — Fri, 18 Sep 2026 11:08:00 +0000

Why should you care?

Many problems don't have an obvious single correct choice.

Instead, you have multiple possibilities:

Choice A
Choice B
Choice C
...

You need to explore those possibilities and find a valid or optimal solution.

Examples include:

Solving Sudoku
N-Queens
Generating permutations
Generating combinations
Maze solving
Subset problems
Constraint satisfaction
Word search
Puzzle solving

Trying every possibility blindly can be extremely expensive.

Backtracking gives us a structured way to explore possibilities:

Make a choice, explore it, and if it doesn't work, undo it and try another choice.

This simple idea is one of the most powerful patterns in algorithmic problem solving.

The Problem

Suppose you want to generate all permutations of:

[1, 2, 3]

The possible permutations are:

How can we systematically generate them?

We can build the answer one element at a time.

Start:

[]

Choose 1:

[1]

Choose 2:

[1, 2]

Choose 3:

[1, 2, 3]

We found one solution.

Now we undo the last decision:

[1, 2]

Try another choice:

[1, 3]

Then:

[1, 3, 2]

And continue.

This process of making and undoing choices is called backtracking.

The Concept

Backtracking explores a decision tree.

At every step:

Choose
  ↓
Explore
  ↓
Valid?
 ├── Yes → Continue
 └── No  → Undo
             ↓
          Try another choice

The general pattern is:

backtrack(state):

    if solution is complete:
        process solution
        return

    for each possible choice:

        make choice

        if choice is valid:
            backtrack(new state)

        undo choice

The most important operation is:

undo choice

That is where the name backtracking comes from.

Simple Explanation

Imagine trying to find a path through a maze.

You walk:

Start
 ↓
A
 ↓
B
 ↓
C

Suppose C is a dead end.

You don't start from the beginning.

You go backward:

C
↑
B

Then try another path:

B
 ↓
D
 ↓
E

This is exactly what a backtracking algorithm does.

Try
 ↓
Dead end?
 ↓
Go back
 ↓
Try another path

The algorithm explores the search space while abandoning choices that cannot lead to a valid solution.

Real-world Analogy

Imagine you are trying to unlock a combination lock.

Suppose each position can contain:

0–9

You try:

If the combination doesn't work, you go back:

1 → 3 → 7
       ↑
      Undo

Then:

1 → 3 → 8

If that fails:

1 → 4 → ...

You systematically explore possibilities.

That's backtracking.

Code Example

Let's generate all permutations of an array.

Step 1: Start with an empty path

[]

Step 2: Choose an element

[1]

Step 3: Choose another

[1, 2]

Step 4: Complete the permutation

[1, 2, 3]

Then we undo:

[1, 2]

and try:

[1, 3]

Let's implement it.

import java.util.*;

public class Main {

    static void generatePermutations(
            int[] nums,
            boolean[] used,
            List<Integer> current) {

        // Complete permutation
        if (current.size() == nums.length) {
            System.out.println(current);
            return;
        }

        for (int i = 0; i < nums.length; i++) {

            // Already used
            if (used[i]) {
                continue;
            }

            // Make choice
            used[i] = true;
            current.add(nums[i]);

            // Explore
            generatePermutations(nums, used, current);

            // Undo choice
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};

        boolean[] used = new boolean[nums.length];

        generatePermutations(
            nums,
            used,
            new ArrayList<>()
        );
    }
}

Output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

How the Code Works

The key lines are:

used[i] = true;
current.add(nums[i]);

We make a choice.

Then:

generatePermutations(nums, used, current);

We explore the choice.

Finally:

current.remove(current.size() - 1);
used[i] = false;

We undo the choice.

This is the fundamental backtracking pattern:

Make
 ↓
Explore
 ↓
Undo

You should recognize this pattern immediately when reading backtracking code.

Visualizing the Decision Tree

For:

[1, 2, 3]

The search tree looks approximately like:

                    []
              /      |      \
             1       2       3
           /   \    / \     / \
          2     3  1   3   1   2
          |     |  |   |   |   |
          3     2  3   1   2   1

Each root-to-leaf path represents one permutation.

For example:

[] → 1 → 2 → 3

produces:

Backtracking explores this tree using recursion.

Common Mistakes

Mistake 1: Forgetting to undo the choice

Consider:

current.add(nums[i]);

generatePermutations(...);

// Missing undo

If you don't remove the element afterward, the state becomes corrupted.

You need:

current.add(nums[i]);

generatePermutations(...);

current.remove(current.size() - 1);

The undo operation is essential.

Mistake 2: Confusing backtracking with recursion

Backtracking usually uses recursion, but recursion alone does not mean backtracking.

For example:

factorial(n)

uses recursion.

But it doesn't explore multiple choices and undo them.

Backtracking generally looks like:

Choice
 ↓
Recursive exploration
 ↓
Undo
 ↓
Next choice

So:

Backtracking is a problem-solving technique that often uses recursion as its implementation mechanism.

Mistake 3: Exploring invalid paths unnecessarily

Suppose you're solving a maze and you know:

This path already violates a constraint.

There is no reason to continue exploring it.

Instead:

Invalid state
     ↓
Stop exploring
     ↓
Backtrack

This is called pruning.

Pruning can dramatically reduce the search space.

Advanced Notes

1. The Backtracking Template

Most backtracking problems can be expressed using this structure:

void backtrack(State state) {

    if (isComplete(state)) {
        saveSolution(state);
        return;
    }

    for (Choice choice : choices(state)) {

        if (!isValid(choice, state)) {
            continue;
        }

        makeChoice(choice, state);

        backtrack(state);

        undoChoice(choice, state);
    }
}

When you encounter a new backtracking problem, try mapping it to these four operations:

1. What are my choices?
2. What makes a choice valid?
3. When is the solution complete?
4. How do I undo a choice?

2. Pruning

Without pruning:

Explore everything

With pruning:

Explore
   ↓
Invalid?
   ↓
STOP

For example, suppose you are finding subsets whose sum equals 10.

Current path:

2 + 7 + 8 = 17

If all remaining numbers are positive, we already exceeded the target.

There is no point continuing.

We can immediately backtrack.

This is pruning.

3. N-Queens Problem

The N-Queens problem asks:

Can we place N queens on an N × N chessboard so that no two queens attack each other?

For four queens:

. Q . .
. . . Q
Q . . .
. . Q .

A queen attacks:

Same row
Same column
Diagonal

A backtracking solution works row by row.

Place queen
     ↓
Is position safe?
 ├── No → Try next position
 └── Yes
       ↓
   Move to next row
       ↓
   Continue
       ↓
   Dead end?
       ↓
   Remove queen
       ↓
   Try another position

This is a classic example of backtracking with pruning.

4. Sudoku

Sudoku is another classic backtracking problem.

Choose an empty cell:

      ↓
Try 1
      ↓
Valid?
 ├── No → Try 2
 └── Yes
       ↓
    Next cell
       ↓
    Eventually invalid?
       ↓
    Undo
       ↓
    Try another number

The algorithm systematically searches possible assignments while immediately abandoning invalid states.

5. Subsets

For every element, we can make two choices:

Take it
   OR
Don't take it

For:

[1, 2, 3]

The decision tree begins:

             []
           /    \
        Take    Skip
         1        1
        / \      / \
       2  skip  2  skip

This pattern appears in many problems involving:

Subsets
Combinations
Target sums
Partitioning
Selection

A useful mental pattern is:

                    Element
                   /       \
                Take       Skip

6. Combinations

Suppose we want all combinations of size 2 from:

[1, 2, 3, 4]

The results are:

[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]

Unlike permutations, order doesn't matter.

Backtracking maintains a starting index:

static void combinations(
        int[] nums,
        int start,
        int k,
        List<Integer> current) {

    if (current.size() == k) {
        System.out.println(current);
        return;
    }

    for (int i = start; i < nums.length; i++) {

        current.add(nums[i]);

        combinations(
            nums,
            i + 1,
            k,
            current
        );

        current.remove(current.size() - 1);
    }
}

The important difference is:

Permutations → can choose previous elements again
Combinations → move forward through the array

7. Word Search

Consider a character grid:

A B C
D E F
G H I

Suppose we want to find:

"BEH"

We can:

B
↓
E
↓
H

If a path doesn't match the word:

Stop
 ↓
Undo
 ↓
Try another direction

Backtracking is particularly useful when exploring paths through grids.

8. Backtracking and DFS

Backtracking is closely related to Depth-First Search.

DFS explores:

Go deep
 ↓
Explore
 ↓
Return
 ↓
Explore another branch

Backtracking adds a crucial idea:

Make a decision
 ↓
Explore
 ↓
Undo the decision

You can think of many backtracking algorithms as:

DFS over a decision tree + state modification + undoing choices.

This connects directly to the DFS concept you learned earlier.

9. Backtracking and Dynamic Programming

Backtracking and Dynamic Programming can solve some similar-looking problems, but they have different strategies.

Backtracking:

Try possibilities
 ↓
Reject invalid paths
 ↓
Continue exploring

Dynamic Programming:

Identify repeated subproblems
 ↓
Solve each once
 ↓
Store results
 ↓
Reuse them

For example:

Backtracking
       ↓
Explore search tree
       ↓
Potentially exponential

Whereas:

Dynamic Programming
       ↓
Merge repeated states
       ↓
Avoid repeated computation

An important optimization is that memoization can sometimes be added to a backtracking-style search when different paths reach the same state.

10. Time Complexity

Backtracking algorithms are often exponential.

For permutations of n elements:

n!

possible solutions exist.

Therefore, generating all permutations requires at least:

O(n!)

time just to output them.

For subset generation:

2^n

subsets exist.

So the search space is:

O(2^n)

For N-Queens, the exact complexity is more complicated, but a straightforward backtracking solution has exponential search behavior.

The key lesson:

Backtracking is not necessarily fast because it is clever; it is fast because it avoids exploring branches that can be proven useless.

11. Branch and Bound

A related optimization technique is Branch and Bound.

Backtracking usually asks:

"Is this state valid?"

Branch and Bound can additionally ask:

"Can this branch possibly produce a better solution?"

If not:

Prune the branch.

This is especially useful for optimization problems.

12. How to Recognize a Backtracking Problem

Look for problems containing phrases such as:

"Generate all..."
"Find all..."
"List every possible..."
"Can we arrange..."
"Find a valid configuration..."
"Choose or don't choose..."
"Try every possibility..."

Then ask:

What are my choices?

For example:

N-Queens:
Which column should I place the queen in?

Sudoku:
Which number should go here?

Permutations:
Which unused element should I choose?

Subset:
Should I take this element or skip it?

Maze:
Which direction should I move?

If each decision creates more decisions, you likely have a decision tree.

That is where backtracking becomes useful.

The Bigger Picture

Your algorithmic progression is now becoming much more powerful:

Data Structures
      ↓
Searching
      ↓
Sorting
      ↓
DFS / BFS
      ↓
Greedy Algorithms
      ↓
Dynamic Programming
      ↓
Backtracking

These techniques solve problems in fundamentally different ways.

Greedy

Make the best choice now.

Dynamic Programming

Solve states and reuse their answers.

Backtracking

Explore choices and undo bad decisions.

A useful comparison:

Technique	Main Idea
Greedy	Commit to a provably safe local choice
DP	Store results of overlapping subproblems
Backtracking	Explore possibilities and undo choices
DFS	Explore a graph/tree deeply
Divide & Conquer	Split into independent subproblems

Backtracking also connects several concepts you've already learned:

Recursion
   +
DFS
   +
Decision Trees
   +
Pruning
   +
State Management
   ↓
Backtracking

The Most Important Mental Model

Remember this:

MAKE
  ↓
EXPLORE
  ↓
VALID?
  ├── YES → Continue
  └── NO  → Stop
  ↓
UNDO
  ↓
TRY NEXT

Or in one sentence:

Backtracking is controlled trial and error: make a choice, explore it, and undo it when it cannot lead to a solution.

Once you can identify the choice, constraint, base case, and undo operation, many backtracking problems become much easier to structure.

Summary

Backtracking is an algorithmic technique for exploring a large set of possible solutions systematically.

Key ideas:

Backtracking explores a decision tree.
It makes a choice and recursively explores it.
It undoes the choice before trying another possibility.
Recursion is commonly used to implement backtracking.
Invalid states should be rejected as early as possible.
Pruning prevents unnecessary exploration.
Permutations, combinations, subsets, Sudoku, N-Queens, and maze solving are classic applications.
Backtracking is closely related to DFS.
Backtracking and Dynamic Programming solve problems differently.
Memoization can sometimes optimize repeated states in a search.
Many backtracking problems have exponential or factorial search spaces.
The quality of pruning can have a major impact on practical performance.

Dynamic Programming : Solving Complex Problems by Reusing Solutions

Shankar L — Thu, 17 Sep 2026 11:06:00 +0000

Why should you care?

Some programming problems look simple but become extremely expensive when solved directly.

A common pattern is:

Solve a problem
    ↓
Break it into smaller problems
    ↓
Solve those problems
    ↓
But the same problems appear again and again

If we calculate the same subproblem repeatedly, we waste time.

Dynamic Programming (DP) solves this problem by remembering solutions to subproblems and reusing them.

Dynamic Programming is one of the most important techniques in algorithmic problem solving.

It appears in:

Competitive programming
Interview problems
Pathfinding
Scheduling
Resource allocation
String algorithms
Finance
Bioinformatics
Game development
Optimization

The most important idea is simple:

Don't solve the same problem twice.

The Problem

Consider the Fibonacci sequence:

F(0) = 0
F(1) = 1

F(n) = F(n - 1) + F(n - 2)

For example:

0, 1, 1, 2, 3, 5, 8, 13, 21...

A straightforward recursive implementation is:

static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Looks simple.

But look at what happens when calculating:

fibonacci(5)

                    fib(5)
                   /      \
               fib(4)     fib(3)
              /    \      /    \
          fib(3) fib(2) fib(2) fib(1)
          /   \
      fib(2) fib(1)

Notice something?

fib(3) is calculated multiple times.

fib(2) is calculated even more times.

For larger n, this repetition becomes enormous.

The recursive solution has approximately:

O(2^n)

time complexity.

We need a way to remember results.

The Concept

Dynamic Programming solves problems by:

Breaking them into smaller subproblems.
Solving each subproblem once.
Storing its result.
Reusing the stored result whenever needed.

The general idea is:

                Original Problem
                       |
          ┌────────────┴────────────┐
          ↓                         ↓
     Subproblem A              Subproblem B
          ↓                         ↓
       Solve                    Solve
          ↓                         ↓
       Store                    Store
          └────────────┬────────────┘
                       ↓
                  Final Answer

Dynamic Programming usually relies on two important properties:

1. Overlapping Subproblems

The same smaller problems appear multiple times.

2. Optimal Substructure

The optimal solution to a problem can be constructed from optimal solutions to its subproblems.

When both properties exist, Dynamic Programming becomes a strong candidate.

Simple Explanation

Imagine you are solving a maze.

Without remembering anything, you might repeatedly walk through the same corridor:

Start
 ↓
A
 ↓
B
 ↓
C

Later, another route reaches B.

Instead of exploring everything from B again, you remember:

"B → destination requires 7 steps."

The next time you reach B:

Look up the answer.
Don't solve it again.

That is the basic idea behind Dynamic Programming.

Real-world Analogy

Imagine you are studying for an exam.

You solve:

Question 1 → Answer: 42

Later, another question requires the answer to Question 1.

Would you solve Question 1 from scratch?

Probably not.

You already know:

Question 1 = 42

So you reuse the answer.

Dynamic Programming does exactly this with subproblems:

Subproblem
    ↓
Solve once
    ↓
Remember answer
    ↓
Reuse whenever needed

Code Example

Let's solve Fibonacci using Dynamic Programming.

Approach 1: Memoization

Memoization is the top-down approach.

We keep the recursive structure but store previously calculated answers.

import java.util.Arrays;

public class Main {

    static int fibonacci(int n, int[] dp) {

        if (n <= 1) {
            return n;
        }

        // Already calculated
        if (dp[n] != -1) {
            return dp[n];
        }

        dp[n] = fibonacci(n - 1, dp)
              + fibonacci(n - 2, dp);

        return dp[n];
    }

    public static void main(String[] args) {

        int n = 10;

        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);

        System.out.println(fibonacci(n, dp));
    }
}

Output:

Now each Fibonacci value is calculated only once.

Complexity

Before:

Time: O(2^n)

With memoization:

Time: O(n)
Space: O(n)

That is a massive improvement.

Approach 2: Tabulation

Tabulation is the bottom-up approach.

Instead of starting from the final problem and recursively going down, we start with the smallest problems and build upward.

public class Main {

    static int fibonacci(int n) {

        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {

        System.out.println(fibonacci(10));
    }
}

The table looks like:

Index:  0  1  2  3  4  5  6  7  8  9  10
Value:  0  1  1  2  3  5  8 13 21 34  55

Each answer is built from previously calculated answers.

Complexity:

Time:  O(n)
Space: O(n)

Common Mistakes

Mistake 1: Thinking recursion automatically means Dynamic Programming

Recursion alone is not DP.

This:

f(n) {
    return f(n - 1) + f(n - 2);
}

is recursion.

It becomes Dynamic Programming when we identify repeated subproblems and store their results.

Recursion
    +
Remember results
    =
Memoized Dynamic Programming

Mistake 2: Using DP when subproblems don't overlap

DP is especially useful when the same subproblems are solved repeatedly.

If every subproblem is unique, storing results may provide little or no benefit.

Always ask:

Am I solving the same subproblem multiple times?

Mistake 3: Choosing the wrong state

The DP state represents the information required to describe a subproblem.

For example, in Fibonacci:

dp[i] = Fibonacci number at position i

For a knapsack problem, the state might be:

dp[i][capacity]

For a grid problem:

dp[row][column]

Choosing the correct state is often the hardest part of DP.

Advanced Notes

1. The Four-Step DP Process

A useful way to approach DP problems is:

Step 1 → Define the state
Step 2 → Find the recurrence
Step 3 → Define base cases
Step 4 → Determine the computation order

Let's apply this to Fibonacci.

Step 1: State

dp[i] = Fibonacci(i)

Step 2: Recurrence

dp[i] = dp[i - 1] + dp[i - 2]

Step 3: Base cases

dp[0] = 0
dp[1] = 1

Step 4: Order

Calculate:

dp[2]
dp[3]
dp[4]
...
dp[n]

This four-step process is extremely useful when solving unfamiliar DP problems.

2. Memoization vs Tabulation

Feature	Memoization	Tabulation
Direction	Top-down	Bottom-up
Usually uses	Recursion	Iteration
Calculates	Needed states	Usually all states
Stack usage	Yes	No
Easy to derive from recursion	Yes	Sometimes
Can optimize space	Yes	Yes

Memoization:

Problem
   ↓
Recursive subproblem
   ↓
Recursive subproblem
   ↓
Store result

Tabulation:

Smallest problem
       ↓
Next problem
       ↓
Next problem
       ↓
Final problem

3. Space Optimization

Our Fibonacci solution stores:

dp[0]
dp[1]
...
dp[n]

But to calculate the next value, we only need the previous two values.

So we can reduce space from:

O(n)

to:

O(1)

public class Main {

    static int fibonacci(int n) {

        if (n <= 1) {
            return n;
        }

        int prev2 = 0;
        int prev1 = 1;

        for (int i = 2; i <= n; i++) {

            int current = prev1 + prev2;

            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }

    public static void main(String[] args) {

        System.out.println(fibonacci(10));
    }
}

Now:

Time:  O(n)
Space: O(1)

This is an important DP optimization.

4. 0/1 Knapsack

One of the most famous DP problems is the 0/1 Knapsack.

Suppose you have:

Capacity = 7

Items:

Item	Weight	Value
A	1	1
B	3	4
C	4	5
D	5	7

Each item can either be:

Take

or:

Don't take

A common DP state is:

dp[i][w]

meaning:

Maximum value using the first i items with capacity w.

For each item, we have two choices:

Don't take item
        OR
Take item

Therefore:

dp[i][w] =
max(
    dp[i-1][w],
    value[i] + dp[i-1][w-weight[i]]
)

This is fundamentally different from Fractional Knapsack.

Greedy works for fractional knapsack, but generally fails for 0/1 knapsack.

Dynamic Programming handles the latter.

5. Grid Path Problems

Suppose you have a grid:

S . . .
. . # .
. # . .
. . . E

You can move:

Right
Down

A DP solution can define:

dp[i][j]

as:

Number of ways to reach cell (i, j).

Then:

dp[i][j] =
dp[i-1][j] + dp[i][j-1]

assuming the cell is not blocked.

This pattern appears in many grid problems.

6. Longest Common Subsequence

DP is also extremely important for strings.

Given:

A = "ABCBDAB"
B = "BDCAB"

We want the longest sequence that appears in both strings without changing the order.

The DP state can be:

dp[i][j]

representing the answer for the first i characters of A and first j characters of B.

If characters match:

dp[i][j] = dp[i-1][j-1] + 1

Otherwise:

dp[i][j] =
max(dp[i-1][j], dp[i][j-1])

This is one of the foundational patterns in string DP.

7. DP on Subsequences

Many DP problems involve choosing or skipping elements.

The recurring structure is:

Take the element
        OR
Skip the element

For example:

                  Element
                 /       \
              Take       Skip

This pattern appears in:

Subset Sum
0/1 Knapsack
Longest Increasing Subsequence
Partition problems
Counting subsets

Recognizing this decision structure can make DP problems much easier.

8. DP on Trees

Dynamic Programming is not limited to arrays.

We can also perform DP on trees.

For example:

A DP value can be calculated for each node based on its children.

This is called Tree DP.

The general idea remains the same:

Solve smaller subtrees
        ↓
Store their results
        ↓
Build the parent's answer

9. DP on Graphs

DP can also appear in graph problems.

Examples include:

Shortest paths in DAGs
Counting paths
Longest paths in DAGs
State-based graph problems

For example, in a Directed Acyclic Graph:

A → B → D
 \       ↑
  → C ───

We can process vertices in topological order and build answers from previously solved states.

This connects DP with the graph algorithms you have already learned.

10. Dynamic Programming vs Greedy

This distinction is extremely important.

Suppose you need to optimize something.

Greedy asks:

"What is the best choice right now?"

Dynamic Programming asks:

"What is the best result for every relevant state?"

Comparison:

Greedy	Dynamic Programming
Makes a local decision	Evaluates subproblem states
Commits to choices	Keeps alternatives through states
Usually no backtracking	Stores multiple possibilities
Often simpler	Often more memory
Requires greedy-choice proof	Uses recurrence/state formulation

A useful rule:

If you cannot prove that a local choice is safe, consider DP.

11. Dynamic Programming vs Divide and Conquer

You have already learned Merge Sort and Quick Sort.

They use Divide and Conquer:

Divide
 ↓
Solve independent subproblems
 ↓
Combine

Dynamic Programming:

Divide
 ↓
Solve overlapping subproblems
 ↓
Store results
 ↓
Reuse results

The key difference is overlap.

If the subproblems are independent, Divide and Conquer is usually appropriate.

If they overlap, Dynamic Programming may be beneficial.

12. Common DP Complexity

If there are:

n states

and each state requires:

O(1)

work:

Time = O(n)

If there are:

n × m states

and each takes constant time:

Time = O(nm)

For example:

LCS → O(nm)
0/1 Knapsack → O(nW)

where W is the capacity.

This is why defining the number of states is important when analyzing DP complexity.

The Bigger Picture

Dynamic Programming is a major step forward in algorithm design.

Your progression now looks like:

Data Structures
      ↓
Searching
      ↓
Sorting
      ↓
DFS / BFS
      ↓
Greedy Algorithms
      ↓
Dynamic Programming

The mindset is changing.

Earlier:

How do I store data?

Then:

How do I search efficiently?

Then:

How do I traverse a structure?

Then:

Can I make the best decision immediately?

Now:

What if I need to consider many possible decisions,
but many of those decisions lead to the same subproblems?

That's where Dynamic Programming becomes powerful.

The Most Important Mental Model

Think of Dynamic Programming as:

Solve every important subproblem once, remember the answer, and build the final solution from those answers.

When you encounter a difficult optimization problem, don't immediately think:

"How do I solve the whole problem?"

Instead ask:

"What smaller problem am I really solving?"

Then:

Can I define a state?
        ↓
Can I express the current answer
using smaller states?
        ↓
Can I store those answers?

If the answer is yes, you may have found a DP solution.

Summary

Dynamic Programming is a technique for solving problems by breaking them into subproblems and storing their results for reuse.

The key ideas are:

DP avoids repeated computation.
It commonly relies on overlapping subproblems.
It commonly relies on optimal substructure.
Memoization is the top-down approach.
Tabulation is the bottom-up approach.
Choosing the correct DP state is often the hardest part.
A recurrence describes how states depend on each other.
Base cases initialize the smallest problems.
DP can often be optimized for space.
Classic DP problems include Knapsack, LCS, LIS, Grid Paths, and Subset Sum.
DP can be applied to arrays, strings, trees, and graphs.
Greedy commits to a local choice; DP keeps track of multiple possibilities through states.
Divide and Conquer solves independent subproblems, while DP is especially useful when subproblems overlap.

Greedy Algorithms : Making the Best Choice at Every Step

Shankar L — Wed, 16 Sep 2026 11:05:00 +0000

Why should you care?

Many programming problems ask us to make a sequence of decisions:

Which activity should we choose first?
Which item should we process next?
How can we minimize cost?
How can we maximize profit?
What is the minimum number of resources required?

One approach is to try every possible combination. But that can quickly become too expensive.

Greedy algorithms provide a powerful alternative:

At every step, make the best choice available right now.

The interesting part is that a greedy algorithm does not simply mean "choose what looks best."

For greedy algorithms to work, the locally optimal choice must lead to a globally optimal solution.

Understanding when this is true—and when it is not—is one of the most important skills in algorithm design.

The Problem

Suppose you have several activities:

Activity	Start	Finish
A	1	3
B	2	5
C	4	6
D	6	8
E	5	9

You want to attend the maximum number of non-overlapping activities.

A brute-force approach could try every possible subset.

But there is a much simpler strategy:

Choose the activity that finishes earliest.
Remove conflicting activities.
Repeat.

For the example:

A: 1 → 3
C: 4 → 6
D: 6 → 8

We selected three activities.

The surprising part is that choosing the activity that finishes earliest is not just a reasonable heuristic.

For this particular problem, it can be proven to produce an optimal solution.

That is the foundation of greedy algorithms.

The Concept

A greedy algorithm builds a solution step by step.

At every step:

Choose the best option available right now.

It does not normally reconsider previous decisions.

The general structure looks like this:

Start with an empty solution

while the problem is not solved:
    choose the best available option
    make that choice
    update the remaining problem

The key idea is local optimality.

Local vs Global Optimality

A locally optimal choice is the best choice right now.

A globally optimal solution is the best solution overall.

For example:

Greedy:

Step 1 → Best current choice
Step 2 → Best current choice
Step 3 → Best current choice
...
        ↓
   Optimal solution

But this only works when the problem has the right mathematical properties.

Simple Explanation

Imagine you are hiking and want to reach the top of a mountain.

At every point, you choose the path that goes uphill the most.

That is a greedy strategy:

"Take the best-looking option right now."

But it may fail.

You could reach a small peak where every available path goes downward, while another path that initially goes slightly downhill would eventually reach the highest mountain.

So:

Greedy choices can be excellent, but they are not automatically correct.

The real question is:

Can we prove that making this local choice never prevents an optimal final solution?

If yes, greedy is a strong candidate.

Real-world Analogy

Imagine you are scheduling meetings in a conference room.

You have many meetings, but only one room.

Your goal is to schedule as many meetings as possible.

One strategy would be:

Choose the meeting that starts earliest.

But this can be bad.

Suppose:

Meeting A:  9:00 ───────────────── 17:00

Meeting B:  9:00 ─ 10:00
Meeting C: 10:00 ─ 11:00
Meeting D: 11:00 ─ 12:00

Choosing A because it starts earliest gives you:

1 meeting

Choosing the meeting that finishes earliest gives:

B → C → D

3 meetings

So the greedy rule is not arbitrary.

For this problem:

Always choose the compatible activity that finishes earliest.

This leaves the maximum amount of time for future activities.

Code Example

Let's implement the classic Activity Selection Problem.

Input

Activities:

Start:  [1, 3, 0, 5, 8, 5]
Finish: [2, 4, 6, 7, 9, 9]

First, sort activities by their finishing time.

import java.util.*;

class Activity {
    int start;
    int finish;

    Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class Main {

    public static void main(String[] args) {

        List<Activity> activities = new ArrayList<>();

        activities.add(new Activity(1, 2));
        activities.add(new Activity(3, 4));
        activities.add(new Activity(0, 6));
        activities.add(new Activity(5, 7));
        activities.add(new Activity(8, 9));
        activities.add(new Activity(5, 9));

        // Sort by finishing time
        activities.sort(
            Comparator.comparingInt(a -> a.finish)
        );

        int lastFinish = -1;

        System.out.println("Selected activities:");

        for (Activity activity : activities) {

            if (activity.start >= lastFinish) {

                System.out.println(
                    activity.start + " -> " + activity.finish
                );

                lastFinish = activity.finish;
            }
        }
    }
}

Output

Selected activities:
1 -> 2
3 -> 4
5 -> 7
8 -> 9

We selected four non-overlapping activities.

Why does it work?

After sorting by finish time:

Choose earliest finishing activity
        ↓
It leaves maximum time remaining
        ↓
Choose next compatible activity
        ↓
Repeat

This is a greedy strategy.

Proving the Greedy Choice

This is where greedy algorithms become interesting.

Suppose the activity that finishes earliest is:

Consider an optimal solution.

If that optimal solution already starts with A, we're done.

If it starts with another activity B that finishes later:

A finishes at 3
B finishes at 5

We can replace B with A.

Since A finishes earlier, replacing B with A cannot reduce the number of activities that can be scheduled afterward.

Therefore, there exists an optimal solution that begins with A.

This is called the greedy-choice property.

Once we make that choice, the remaining problem has exactly the same structure:

Choose the next compatible activity

This gives us the optimal substructure needed for the greedy solution.

Common Mistakes

Mistake 1: Assuming every optimization problem can be solved greedily

This is the biggest mistake.

Consider the coin-change problem.

Coins:

1, 3, 4

Target:

A greedy algorithm chooses:

Remaining:

Then:

1 + 1

Total:

4 + 1 + 1 = 3 coins

But the optimal solution is:

3 + 3 = 2 coins

So greedy fails here.

The lesson:

A greedy-looking strategy must be proven correct for the specific problem.

Mistake 2: Confusing greedy with brute force

Greedy does not try every possibility.

Brute force:

Try A
Try B
Try C
Try A + B
Try A + C
Try B + C
...

Greedy:

Choose best current option
Choose best current option
Choose best current option

This is why greedy algorithms are often much faster.

Mistake 3: Choosing the largest immediate value

"Best" does not always mean:

largest number

or:

smallest number

The correct greedy criterion depends on the problem.

Examples:

Problem	Greedy choice
Activity Selection	Earliest finish time
Fractional Knapsack	Highest value/weight
Huffman Coding	Lowest frequencies
Dijkstra	Smallest current distance
Minimum Spanning Tree	Safest minimum-cost edge
Job Scheduling	Depends on objective

The hardest part is often identifying the correct greedy rule.

Advanced Notes

1. Greedy-Choice Property

A problem has the greedy-choice property when making the locally optimal choice can lead to a globally optimal solution.

The important phrase is:

"can lead to an optimal solution."

It does not mean that every arbitrary greedy choice works.

2. Optimal Substructure

A problem has optimal substructure when an optimal solution contains optimal solutions to its subproblems.

For example:

Optimal solution
       ↓
Greedy choice
       +
Optimal solution to remaining problem

Both properties are commonly used when proving greedy algorithms.

3. Fractional Knapsack

Suppose you have a bag with capacity:

50 kg

and items:

Item	Weight	Value
A	10	60
B	20	100
C	30	120

In fractional knapsack, you can take part of an item.

Calculate:

Value / Weight

Item	Value/Weight
A	6
B	5
C	4

Take:

A → 10 kg
B → 20 kg
C → 20 kg

Total:

50 kg

Value:

60 + 100 + 80 = 240

The greedy rule is:

Take the item with the highest value-to-weight ratio first.

This works for fractional knapsack.

But it does not work for the 0/1 Knapsack problem, where an item must be taken completely or not at all.

That distinction is extremely important.

4. Huffman Coding

Greedy algorithms are also used in data compression.

Huffman coding repeatedly combines the two least-frequent symbols.

For example:

A → 45
B → 13
C → 12
D → 16
E → 9
F → 5

The algorithm repeatedly chooses the two smallest frequencies and combines them.

This produces a prefix-free binary tree where frequently occurring characters receive shorter codes.

The greedy choice leads to an optimal prefix code.

5. Minimum Spanning Tree

Greedy algorithms are fundamental to graph algorithms.

Two famous algorithms are:

Kruskal's Algorithm
Prim's Algorithm

Kruskal repeatedly chooses the lowest-weight edge that does not create a cycle.

Prim repeatedly chooses the cheapest edge that expands the current tree.

Both rely on greedy choices.

6. Dijkstra's Algorithm

Dijkstra's shortest-path algorithm also uses a greedy strategy.

At each step:

Choose the unvisited vertex
with the smallest known distance.

Then update its neighbors.

For graphs with non-negative edge weights, this greedy decision can be proven correct.

However, if negative edge weights exist, standard Dijkstra's algorithm is not valid.

7. Greedy vs Dynamic Programming

Greedy and Dynamic Programming are often confused.

Greedy	Dynamic Programming
Makes one choice and commits	Considers multiple possibilities
Usually doesn't revisit choices	Stores/reuses subproblem results
Often simpler	Usually more complex
Can be very fast	Often uses more memory
Requires greedy-choice property	Uses overlapping subproblems + optimal substructure

A useful question is:

Can I safely commit to the best choice now?

If yes, greedy may work.

If not, dynamic programming may be necessary.

8. Greedy vs Backtracking

Backtracking explores choices and can undo them.

Choose
 ↓
Explore
 ↓
Wrong?
 ↓
Undo
 ↓
Try another

Greedy:

Choose
 ↓
Commit
 ↓
Never undo

This makes greedy algorithms much more efficient when their correctness can be guaranteed.

9. Complexity

Many greedy algorithms have excellent performance.

For activity selection:

Sorting: O(n log n)
Selection: O(n)

Therefore:

Total = O(n log n)

If activities are already sorted by finish time:

O(n)

The greedy decision itself is often cheap.

The expensive part is frequently sorting the input.

10. How to Recognize a Greedy Problem

When facing an optimization problem, ask:

1. What am I trying to maximize/minimize?

2. What is the best choice I can make right now?

3. If I make that choice, can I safely discard the alternatives?

4. Does the remaining problem have the same structure?

5. Can I prove that replacing the first choice
   with my greedy choice never makes the solution worse?

That last question is especially important.

Do not use greedy simply because the solution "looks right."

Try to prove it.

The Bigger Picture

Greedy algorithms fit into a larger algorithm-design progression.

You have already learned several fundamental techniques:

Arrays
   ↓
Linked Lists
   ↓
Stacks / Queues
   ↓
Trees / Graphs
   ↓
Searching
   ↓
Sorting
   ↓
DFS / BFS
   ↓
Greedy Algorithms

Now the focus changes.

Previously, we often asked:

"How can I efficiently process the data?"

With greedy algorithms, we start asking:

"How can I make the right decisions efficiently?"

This is a major transition from learning data structures to learning algorithmic problem solving.

Greedy algorithms also prepare you for more advanced concepts:

Greedy
   ├── Activity Selection
   ├── Fractional Knapsack
   ├── Huffman Coding
   ├── Dijkstra
   ├── Prim
   └── Kruskal
          ↓
Dynamic Programming
          ↓
Advanced Algorithm Design

The Most Important Mental Model

Think of a greedy algorithm as:

"Make the best decision you can prove is safe, then never look back."

The phrase "you can prove is safe" is the most important part.

Greedy is not:

Pick what looks best.

It is:

Pick what is provably safe and optimal at this step.

Summary

Greedy algorithms solve optimization problems by repeatedly making a locally optimal choice.

Key ideas:

Greedy algorithms make decisions step by step.
They generally do not reconsider previous decisions.
Local optimality does not automatically guarantee global optimality.
Correct greedy algorithms require a justification or proof.
The greedy-choice property is central to greedy correctness.
Optimal substructure is commonly present.
Activity Selection is a classic greedy problem.
Fractional Knapsack can be solved greedily.
0/1 Knapsack cannot generally be solved using the same greedy strategy.
Huffman Coding, Dijkstra, Prim, and Kruskal use greedy ideas.
Sorting is often the main cost of a greedy solution.
Greedy is different from Dynamic Programming and Backtracking.

BFS : Exploring Graphs Level by Level

Shankar L — Tue, 15 Sep 2026 11:04:00 +0000

Why should you care?

In the previous article, we learned DFS (Depth-First Search).

DFS explores a graph by going as deep as possible before backtracking.

But sometimes we don't want to go deep.

We want to explore the graph level by level.

That's where Breadth-First Search (BFS) comes in.

BFS is useful for:

Finding shortest paths in unweighted graphs
Social-network connections
Finding nearby locations
Network broadcasting
Web crawling
Level-order tree traversal
Maze solving
Recommendation systems
Finding the minimum number of steps between states

The key idea is simple:

Explore everything nearby before going farther away.

The Problem

Consider this graph:

```text id="q7m2ds"
A
/ \
B C
/ \ \
D E F




Starting from `A`, we want to visit every node.

DFS might visit:



```text id="qk5zq0"
A → B → D → E → C → F

BFS takes a different approach.

It first visits nodes at distance 1:

```text id="7lq3h0"
A
↓
B, C




Then nodes at distance 2:



```text id="p3u7qy"
D, E, F

So the traversal becomes:

```text id="u1z4gf"
A → B → C → D → E → F




The exact order can depend on how neighbors are stored, but the **level-by-level behavior** is the important part.

---

## The Concept

BFS stands for:

> **Breadth-First Search**

It explores a graph in layers.

The basic process is:



```text id="q7pv0r"
Start
  ↓
Visit starting node
  ↓
Add its neighbors to a queue
  ↓
Remove the first node from queue
  ↓
Visit its unvisited neighbors
  ↓
Repeat

The most important data structure used by BFS is a:

```text id="l1z3j4"
Queue




This gives BFS its characteristic behavior:



```text id="q4o8pf"
First In → First Out

The nodes discovered first are processed first.

Simple Explanation

Imagine a fire spreading through a building.

At time:

```text id="6s2c4z"
0




only the starting room is affected.

At time:



```text id="0v6xqv"
1

the fire reaches all directly connected rooms.

At time:

```text id="6j0z9f"
2




it reaches rooms connected to those rooms.

And so on.

The spread happens in **layers**:



```text id="h6j5r7"
Level 0 → Start

Level 1 → Direct neighbors

Level 2 → Neighbors of neighbors

Level 3 → Next layer

...

BFS explores a graph in exactly this way.

Real-world Analogy

Imagine you're looking for a friend in a social network.

You start with:

```text id="l3g7tc"
You




First, check your direct friends:



```text id="q1y4bd"
You
 ↓
Your friends

If you don't find the person, check your friends' friends:

```text id="m2z9ab"
You
↓
Friends
↓
Friends of friends




Then:



```text id="n0g1wv"
Friends of friends of friends

You're expanding outward one connection at a time.

This is exactly what BFS does.

Code Example

Let's implement BFS in Java using an adjacency list.

```java id="8g8w2n"
public static void bfs(
String start,
Map> graph) {

Set<String> visited = new HashSet<>();

Queue<String> queue = new LinkedList<>();

visited.add(start);
queue.add(start);

while (!queue.isEmpty()) {

    String node = queue.poll();

    System.out.println(node);

    for (String neighbor : graph.get(node)) {

        if (!visited.contains(neighbor)) {

            visited.add(neighbor);
            queue.add(neighbor);
        }
    }
}

}




Example graph:



```java id="7o6g8c"
Map<String, List<String>> graph = new HashMap<>();

graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D", "E"));
graph.put("C", Arrays.asList("A", "F"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("B"));
graph.put("F", Arrays.asList("C"));

Run BFS:

```java id="r6c8d4"
bfs("A", graph);




Possible output:



```text id="j0l9pp"
A
B
C
D
E
F

Understanding the Code

The first important structure is:

```java id="i8xq8q"
Queue queue = new LinkedList<>();




The queue controls the order in which nodes are processed.

We start with:



```java id="m7o6j5"
queue.add(start);

Suppose:

```text id="w4m8cw"
start = A




The queue contains:



```text id="4u2o5r"
[A]

We remove A:

```java id="f5u0fa"
String node = queue.poll();




Now inspect its neighbors:



```text id="a8o9er"
B
C

Add them to the queue:

```text id="d7r5mw"
[B, C]




Remove `B`:



```text id="f6x4wz"
[C]

B's unvisited neighbors are:

```text id="o8w3vl"
D
E




Add them:



```text id="w1d0g6"
[C, D, E]

Now process C.

Its neighbor:

```text id="u8s4dz"
F




gets added:



```text id="y7q2qm"
[D, E, F]

Eventually:

```text id="u4y8tw"
D → E → F




are processed.

Therefore:



```text id="pr0n7m"
A → B → C → D → E → F

Why Do We Need `visited`?

Graphs can contain cycles.

Consider:

```text id="q6b3f7"
A → B
↑ ↓
└───C




If we don't track visited nodes:



```text id="qf7z8p"
A → B → C → A → B → C → ...

The algorithm could continue forever.

Therefore:

```java id="2l6w3s"
Set visited




keeps track of nodes that have already been discovered.

An important detail is that we mark a node as visited **when we add it to the queue**, rather than waiting until we remove it.

This prevents the same node from being added multiple times through different paths.

---

## BFS and Shortest Path

One of the most important applications of BFS is finding the **shortest path in an unweighted graph**.

Consider:



```text id="0i7j56"
A ─ B ─ D
 \   \
  C ─ E

Suppose we want the shortest path from A to E.

BFS explores by distance:

```text id="x4m8c4"
Distance 0:
A

Distance 1:
B, C

Distance 2:
D, E




When BFS reaches `E`, it has found the minimum number of edges needed to reach it.

This works because BFS explores nodes in increasing distance from the starting node.

---

## Finding the Actual Shortest Path

BFS can be extended to store each node's parent.

For example:



```java id="j8d4s5"
Map<String, String> parent = new HashMap<>();

When discovering a new node:

```java id="c1p9s2"
parent.put(neighbor, node);




Suppose:



```text id="g6v7mc"
parent[E] = C
parent[C] = A

We can reconstruct:

```text id="1w4s3r"
E
↑
C
↑
A




Therefore:



```text id="2v0k2p"
A → C → E

is the path.

This technique is widely used in shortest-path problems.

BFS on a Tree

BFS is also called Level-Order Traversal when applied to a tree.

Consider:

```text id="6e9q7r"
A
/ \
B C
/ \ \
D E F




BFS visits:



```text id="f1s9x0"
Level 0 → A
Level 1 → B C
Level 2 → D E F

Traversal:

```text id="c7d3n4"
A → B → C → D → E → F




This is useful when you need to process a tree level by level.

---

## Time Complexity

For a graph represented using an adjacency list:



```text id="q5m6g2"
O(V + E)

where:

```text id="6z9c4q"
V = number of vertices
E = number of edges




Why?

BFS visits each reachable vertex at most once:



```text id="2a5j3y"
O(V)

It also examines each relevant edge:

```text id="4k7t9r"
O(E)




Therefore:



```text id="q8s0j1"
O(V + E)

This is the same asymptotic complexity as DFS.

The difference isn't primarily speed.

It is how the graph is explored.

Space Complexity

BFS needs:

```text id="0o7j1h"
Visited set → O(V)




and a queue.

In the worst case, the queue can contain:



```text id="0k1z7e"
O(V)

vertices.

Therefore:

```text id="9u0f1p"
Space = O(V)




in the worst case.

This is an important difference from DFS in terms of practical memory behavior.

A graph with a very wide level can cause BFS's queue to become large.

---

## Common Mistakes

### Mistake 1: Using a Stack instead of a Queue

BFS requires:



```text id="2qj9tx"
Queue

not:

```text id="8n9w2v"
Stack




A stack gives:



```text id="7j5z6m"
Last In → First Out

which naturally leads toward DFS behavior.

Remember:

```text id="0r4l9g"
DFS → Stack
BFS → Queue




---

### Mistake 2: Marking nodes as visited too late

Consider:



```text id="r5x7m3"
A
/ \
B  C
 \ /
  D

Both B and C can discover D.

If D isn't marked visited until it is removed from the queue, it could be inserted multiple times.

Instead:

```java id="6t0d8h"
visited.add(neighbor);
queue.add(neighbor);




Mark it when it is discovered.

---

### Mistake 3: Assuming BFS always finds the shortest path

BFS guarantees a shortest path in terms of the **number of edges** when the graph is unweighted.

But consider weighted edges:



```text id="5m8n1f"
A ──1── B
 \     /
  10  1
   \ /
    C

The path with fewer edges isn't necessarily the path with the smallest total weight.

For weighted shortest-path problems, algorithms such as:

```text id="5y5f3q"
Dijkstra's Algorithm
Bellman-Ford




may be appropriate depending on the graph.

---

### Mistake 4: Forgetting disconnected components

Suppose:



```text id="4tdm7v"
A ─ B ─ C

D ─ E

Starting BFS from A only reaches:

```text id="98s0jv"
A, B, C




It won't automatically reach `D` and `E`.

If you need to traverse the entire graph, you can run BFS from every unvisited vertex.

---

### Mistake 5: Assuming BFS order is always identical

Neighbor ordering affects traversal order.

For example:



```text id="1x7y9m"
A → B, C

could produce:

```text id="ux9m5s"
A B C




while a different adjacency ordering could produce:



```text id="x3w4s8"
A C B

The important property is that nodes are processed according to their distance from the starting node.

Advanced Notes

1. BFS Using an ArrayDeque

In Java, ArrayDeque is generally a better choice for a queue than the legacy Stack class.

For example:

```java id="n6n3d1"
Queue queue = new ArrayDeque<>();

queue.add(start);

while (!queue.isEmpty()) {

String node = queue.poll();

// process node

}




This provides efficient queue operations.

---

### 2. BFS with Distance

We can store the distance from the starting node.



```java id="8j5t1k"
Map<String, Integer> distance = new HashMap<>();

distance.put(start, 0);

When discovering a neighbor:

```java id="r0t7hy"
distance.put(
neighbor,
distance.get(node) + 1
);




Now:



```text id="q6n7b5"
distance[X]

tells us how many edges are required to reach X.

This is extremely useful for shortest-path problems.

3. Multi-Source BFS

BFS doesn't have to start with one node.

Suppose several locations are sources:

```text id="9m5w3k"
A
C
F




We can put all of them into the queue initially:



```text id="q4r9c2"
[A, C, F]

Then perform normal BFS.

This is called Multi-Source BFS.

It can solve problems such as:

Nearest facility
Spread simulation
Multiple starting points
Distance to the nearest source

4. BFS on a Grid

A 2D grid can be treated as a graph.

For example:

```text id="h8m4p1"
. . .
. # .
. . .




Each cell can represent a vertex.

Neighbors are typically:



```text id="e4g9z6"
up
down
left
right

BFS can then find the shortest path from one cell to another.

This is common in:

Maze problems
Grid games
Robot navigation
Pathfinding problems

5. Bipartite Graph Detection

BFS can be used to determine whether a graph is bipartite.

A common technique is to assign alternating colors:

```text id="j3x8v5"
A → Color 0

Neighbors → Color 1

Their neighbors → Color 0




If an edge connects two nodes that have the same color, the graph is not bipartite.

This demonstrates how BFS can do much more than simple traversal.

---

### 6. BFS vs DFS

This is the most important comparison.

| Feature                           | BFS                    | DFS                  |
| --------------------------------- | ---------------------- | -------------------- |
| Strategy                          | Level by level         | Depth first          |
| Main structure                    | Queue                  | Stack                |
| Shortest path in unweighted graph | Yes                    | Not guaranteed       |
| Typical use                       | Levels, shortest paths | Cycles, backtracking |
| Time                              | O(V + E)               | O(V + E)             |
| Space                             | O(V)                   | O(V)                 |

The algorithms have the same asymptotic graph traversal complexity, but their behavior is fundamentally different.

---

## The Bigger Picture

BFS connects several concepts we've already learned.

### Queues

We previously learned:



```text id="o0a5b9"
Queue
 ↓
FIFO

BFS is one of the most important practical applications of a queue.

```text id="1n6j6r"
BFS
↓
Queue
↓
Level-by-level exploration




---

### DFS

We just learned:



```text id="j4r7q2"
DFS → Deep first

BFS gives us the complementary strategy:

```text id="1l9x3v"
BFS → Broad first




Together, they form the two fundamental graph traversal techniques.

---

### Graphs

Our Graph article introduced:



```text id="d7v2q9"
Vertices
+
Edges

BFS gives us a systematic way to navigate those relationships.

```text id="1q6y5w"
Graph
↓
BFS
↓
Traversal
↓
Shortest paths / levels / connectivity




---

### Big-O

From our Big-O article:



```text id="j2g0s7"
BFS = O(V + E)

This demonstrates why graph algorithms are often analyzed in terms of both vertices and edges.

Binary Search

Binary Search taught us to reduce the search space intelligently.

BFS uses a different strategy.

Instead of repeatedly cutting the search space in half, BFS expands outward by distance:

```text id="x5t8w4"
Distance 0
↓
Distance 1
↓
Distance 2
↓
Distance 3




The goal is not the same, but both algorithms demonstrate an important principle:

> **Choose an exploration strategy that matches the structure of the problem.**

---

## The Most Important Mental Model

Don't think of BFS as:

> "DFS but with a queue."

Think:

> **"Explore everything at the current distance before moving farther away."**

Visualize:



```text id="0z2j8q"
             A
           /   \
          B     C
         / \     \
        D   E     F

BFS moves:

```text id="8x4g7p"
Level 0:
A

Level 1:
B C

Level 2:
D E F




So:



```text id="z8c5h2"
A → B → C → D → E → F

This is why BFS naturally solves shortest-path problems in unweighted graphs.

If every edge represents one unit of distance, BFS discovers:

```text id="0t5y1c"
closest nodes first




---

## Summary

Breadth-First Search is a graph traversal algorithm that explores nodes **level by level**.

The basic process is:



```text id="w0r7kp"
Start
  ↓
Queue
  ↓
Process first node
  ↓
Add unvisited neighbors
  ↓
Process next node
  ↓
Repeat

Key points:

BFS uses a queue.
It explores nodes according to their distance from the starting point.
A visited set prevents repeated processing.
BFS runs in O(V + E) with an adjacency-list graph.
Its additional space can be O(V).
BFS finds shortest paths in unweighted graphs.
It can perform level-order tree traversal.
It can be adapted for grids, multi-source problems, and bipartite detection.
BFS and DFS have the same typical graph traversal complexity but explore the graph differently.

The fundamental comparison is:

```text id="m7y9s4"
DFS
↓
Go deep
↓
Stack
↓
Backtrack

BFS
↓
Go wide
↓
Queue
↓
Next level

DFS : Exploring Graphs One Path at a Time

Shankar L — Mon, 14 Sep 2026 11:03:00 +0000

Why should you care?

In the previous Graphs article, we learned how graphs represent relationships between objects.

But storing a graph is only the beginning.

A common question is:

How do we actually explore everything inside a graph?

This is where Depth-First Search, commonly called DFS, comes in.

DFS is used in:

Graph traversal
Tree traversal
Finding connected components
Detecting cycles
Maze solving
Path finding
Topological sorting
Dependency analysis
Backtracking algorithms
Network exploration

DFS is especially important because it teaches a fundamental algorithmic pattern:

Go as deep as possible before going back.

The Problem

Suppose we have this graph:

```text id="c9qv8j"
A
/ \
B C
/ \ \
D E F




We want to visit every node.

Where should we start?

If we simply move from one node to another without a strategy, we could:

* Visit nodes multiple times.
* Get stuck in cycles.
* Miss parts of the graph.
* Waste computation.

We need a systematic traversal algorithm.

Two of the most important graph traversal algorithms are:



```text id="v5h0mt"
BFS → Breadth-First Search
DFS → Depth-First Search

DFS explores one path deeply before returning and exploring another.

The Concept

The basic DFS process is:

```text id="t0w8w8"
Start at a node
↓
Visit it
↓
Choose an unvisited neighbor
↓
Visit that neighbor
↓
Continue deeper
↓
No unvisited neighbors?
↓
Go back
↓
Continue another path




The "go back" operation is called **backtracking**.

DFS can be implemented using:

1. **Recursion**
2. **An explicit Stack**

This is an important connection:



```text id="4b9lqa"
DFS
 ↓
Stack

Recursion itself uses the call stack internally.

Simple Explanation

Consider:

```text id="k1x3d6"
A
/ \
B C
/ \
D E




Start at `A`.

DFS visits:



```text id="b5sl4n"
A

Then goes deeper:

```text id="yx3h85"
A → B




Then deeper again:



```text id="1e6hlc"
A → B → D

D has no unvisited neighbors.

So we go back:

```text id="zpjx5k"
A → B




Then explore:



```text id="1c6dgt"
A → B → E

After finishing B, return to A.

Then explore:

```text id="2t5z99"
A → C




A possible traversal order is:



```text id="n76w4n"
A → B → D → E → C

The exact order depends on how neighbors are stored.

The important part is the strategy:

Go deep first.

Real-world Analogy

Imagine exploring a maze.

You enter through the starting point.

Instead of exploring every nearby corridor first, you:

Choose one corridor.
Keep walking forward.
Continue until you reach a dead end.
Walk backward to the last decision point.
Try another unexplored corridor.
Repeat.

That is DFS.

Visually:

```text id="h3l2cu"
Start
↓
Path 1
↓
Path 1.1
↓
Path 1.1.1
↓
Dead end
↓
Backtrack
↓
Path 1.2




This is exactly how DFS explores a graph.

---

## Code Example

Let's implement DFS recursively in Java.

Suppose our graph is represented using an adjacency list:



```java id="k4os65"
Map<String, List<String>> graph = new HashMap<>();

graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D", "E"));
graph.put("C", Arrays.asList("A"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("B"));

Now implement DFS:

```java id="j3z9n8"
public static void dfs(
String node,
Map> graph,
Set visited) {

visited.add(node);

System.out.println(node);

for (String neighbor : graph.get(node)) {

    if (!visited.contains(neighbor)) {
        dfs(neighbor, graph, visited);
    }
}

}




Call it using:



```java id="j5s6da"
Set<String> visited = new HashSet<>();

dfs("A", graph, visited);

A possible output:

```text id="lq98x4"
A
B
D
E
C




---

## Understanding the Code

The first important line is:



```java id="6l1q7k"
visited.add(node);

We mark the current node as visited.

Why?

Because graphs can contain cycles.

For example:

```text id="m5l1kd"
A → B
↑ ↓
└───C




If we don't remember which nodes we've visited, DFS could keep going:



```text id="7v6vpy"
A → B → C → A → B → C → ...

forever.

The visited set prevents this.

Exploring Neighbors

Then:

```java id="w6ydx9"
for (String neighbor : graph.get(node)) {




we examine every neighboring node.

If we haven't visited it:



```java id="jz0m7c"
if (!visited.contains(neighbor)) {

we recursively explore it:

```java id="y5yk5b"
dfs(neighbor, graph, visited);




This is the key line.

It tells DFS:

> "Don't just visit the neighbor. Go all the way down that path."

---

## The Call Stack

DFS recursion becomes much easier to understand when you visualize the call stack.

Suppose:



```text id="zw8ks8"
A → B → D

DFS does:

```text id="a3cnz7"
dfs(A)
↓
dfs(B)
↓
dfs(D)




The call stack becomes:



```text id="h2m4xz"
┌─────────┐
│ dfs(D)  │
├─────────┤
│ dfs(B)  │
├─────────┤
│ dfs(A)  │
└─────────┘

When D has no more neighbors:

```text id="m3j4bw"
dfs(D)




returns.

Then:



```text id="5r2jpb"
dfs(B)

continues.

This is exactly the backtracking behavior of DFS.

Iterative DFS Using a Stack

DFS doesn't have to use recursion.

We can explicitly create a stack.

```java id="g65g4e"
public static void dfsIterative(
String start,
Map> graph) {

Set<String> visited = new HashSet<>();

Stack<String> stack = new Stack<>();

stack.push(start);

while (!stack.isEmpty()) {

    String node = stack.pop();

    if (visited.contains(node)) {
        continue;
    }

    visited.add(node);

    System.out.println(node);

    for (String neighbor : graph.get(node)) {

        if (!visited.contains(neighbor)) {
            stack.push(neighbor);
        }
    }
}

}




The important difference is:



```text id="w2d5lq"
Recursive DFS
    ↓
Uses call stack

Iterative DFS
    ↓
Uses explicit stack

The underlying idea is the same.

DFS on a Tree

DFS isn't limited to graphs.

Trees can also be traversed using DFS.

Consider:

```text id="3b2t4y"
A
/ \
B C
/ \
D E




There are three classic DFS tree traversals.

### Preorder



```text id="6b7b8b"
Root
Left
Right

Result:

```text id="b9n0m8"
A B D E C




### Inorder



```text id="ap5o5k"
Left
Root
Right

Result:

```text id="g4efh0"
D B E A C




This is especially important for Binary Search Trees because inorder traversal produces values in sorted order.

### Postorder



```text id="0q8x9n"
Left
Right
Root

Result:

```text id="5z2fda"
D E B C A




All three are forms of **Depth-First Traversal**.

---

## Time Complexity

For a graph represented using an adjacency list:



```text id="j8y0on"
O(V + E)

where:

```text id="oq8t3u"
V = number of vertices
E = number of edges




Why?

DFS visits every reachable vertex at most once:



```text id="1y1ujv"
O(V)

It also examines the edges:

```text id="j5xk1y"
O(E)




Therefore:



```text id="7lhqym"
O(V + E)

This is one of the fundamental graph algorithm complexities.

Space Complexity

DFS requires:

```text id="b8xk5g"
Visited set → O(V)




The recursion stack can also grow to:



```text id="x9s2cm"
O(V)

in the worst case.

Therefore, recursive DFS generally uses:

```text id="w0r7bn"
O(V)




additional space.

Iterative DFS also requires:



```text id="e9ay4n"
O(V)

for the stack and visited set in the worst case.

Common Mistakes

Mistake 1: Forgetting the visited set

This is one of the most dangerous DFS mistakes.

Consider:

```text id="spzgjq"
A → B
↑ ↓
└───C




Without `visited`, DFS can repeatedly follow:



```text id="q8rj1u"
A → B → C → A → B → C → ...

Always track visited nodes when traversing a general graph.

Mistake 2: Marking nodes too late

A common mistake is marking a node as visited only after recursively exploring its neighbors.

That can cause the same node to be added to the recursion path multiple times in graphs with cycles or converging paths.

A safe general pattern is:

```java id="8zv0f5"
visited.add(node);

for (...) {
if (!visited.contains(neighbor)) {
dfs(...);
}
}




Mark the node when you begin processing it.

---

### Mistake 3: Thinking DFS always finds the shortest path

DFS finds a path if one exists, but it does **not** generally find the shortest path in an unweighted graph.

For shortest paths in an unweighted graph, **BFS** is usually the appropriate algorithm.

For example:



```text id="l4qlpi"
A ─── B ─── D
 \          /
  └── C ───

DFS may explore a longer route before discovering a shorter one.

DFS and BFS solve different traversal problems.

Mistake 4: Assuming DFS has one fixed traversal order

Consider:

```text id="f5v2dl"
A
├── B
└── C




DFS could produce:



```text id="xkz5l4"
A B C

or:

```text id="d5h7u0"
A C B




depending on neighbor ordering.

The DFS strategy remains the same.

The exact traversal order depends on the graph representation.

---

### Mistake 5: Ignoring recursion depth

A graph can contain a very long chain:



```text id="k9h2sd"
A
 ↓
B
 ↓
C
 ↓
D
 ↓
...

Recursive DFS may create a very deep call stack.

For sufficiently large graphs, an iterative implementation with an explicit stack can avoid recursion-depth limitations.

Advanced Notes

1. DFS for Cycle Detection

DFS can detect cycles.

For an undirected graph, one approach is to keep track of the parent node.

For directed graphs, we can track the current recursion path.

For example:

```text id="6e2q2m"
A → B → C
↑ ↓
└─────




DFS eventually encounters a node that is already part of the current recursion path.

That indicates a cycle.

Cycle detection is useful for:

* Dependency systems
* Build systems
* Scheduling
* Graph validation

---

### 2. Connected Components

Suppose a graph contains:



```text id="b5k6ub"
A ─ B ─ C

D ─ E

F

There are three connected components:

```text id="3fs0a1"
{A, B, C}
{D, E}
{F}




We can run DFS from every unvisited node.

Each DFS identifies one connected component.

This is a common graph problem.

---

### 3. Topological Sorting

DFS can also be used for **topological sorting** of a Directed Acyclic Graph.

For example:



```text id="r7i4a8"
Requirements
    ↓
Programming
    ↓
Data Structures
    ↓
Algorithms

DFS can explore dependencies and add nodes after their descendants have been processed.

Reversing that finishing order gives a topological ordering.

This is useful for:

Course prerequisites
Build dependencies
Task scheduling
Package dependencies

4. Backtracking

DFS is closely related to backtracking.

The general pattern is:

```text id="7k7w9q"
Choose
↓
Explore
↓
Valid?
↓
Continue
↓
Dead end?
↓
Undo
↓
Try another choice




This appears in problems such as:

* Maze solving
* Sudoku
* N-Queens
* Permutations
* Combinations
* Path finding

The key idea is that DFS provides the exploration mechanism while backtracking provides the "undo and try another option" behavior.

---

### 5. DFS vs BFS

This is one of the most important comparisons to understand.

| Feature                           | DFS                               | BFS                    |
| --------------------------------- | --------------------------------- | ---------------------- |
| Main structure                    | Stack                             | Queue                  |
| Strategy                          | Go deep                           | Go wide                |
| Typical implementation            | Recursion / Stack                 | Queue                  |
| Shortest path in unweighted graph | Not guaranteed                    | Yes                    |
| Memory                            | Can be O(V)                       | Can be O(V)            |
| Useful for                        | Exploration, cycles, backtracking | Shortest paths, levels |

Think:



```text id="u3l8mw"
DFS → Deep first

BFS → Broad first

The Bigger Picture

DFS connects almost everything we've learned so far.

Stack

DFS is naturally implemented using a stack.

```text id="2vq5bi"
DFS
↓
Stack




Recursion provides an implicit stack.

---

### Trees

Tree traversals such as:



```text id="7d8o2k"
Preorder
Inorder
Postorder

are DFS-based traversals.

Graphs

DFS provides a systematic way to explore graphs.

```text id="j1q9cp"
Graph
↓
DFS
↓
Traversal




---

### Recursion

Recursive DFS repeatedly solves the same problem on a neighboring node:



```text id="z8g4ds"
dfs(current)
    ↓
dfs(neighbor)
        ↓
dfs(next neighbor)

Big-O

From our Big-O article:

```text id="l2xw6h"
DFS → O(V + E)




This gives us a way to reason about how graph traversal scales.

---

### Binary Search and Sorting

Binary Search and sorting algorithms taught us how algorithms reduce problems into smaller pieces.

DFS applies a similar recursive mindset:



```text id="g1j8qt"
Current problem
      ↓
Choose neighbor
      ↓
Solve smaller exploration problem
      ↓
Return
      ↓
Explore next neighbor

The Most Important Mental Model

Don't think of DFS as:

"An algorithm that visits nodes."

Think:

"Keep going forward until you can't, then backtrack."

Visualize:

```text id="u3e9ro"
A
/ \
B C
/ \
D E




DFS:



```text id="q9azj7"
A
↓
B
↓
D
↑
B
↓
E
↑
B
↑
A
↓
C

The arrows going down represent exploration.

The arrows going up represent backtracking.

That is DFS.

Summary

Depth-First Search is a graph traversal algorithm that explores as deeply as possible before backtracking.

The basic process is:

```text id="2y7b0p"
Visit node
↓
Choose unvisited neighbor
↓
Go deeper
↓
Dead end?
↓
Backtrack
↓
Explore another path




Key points:

* DFS explores deeply before moving to another branch.
* It can be implemented recursively or with a stack.
* A `visited` set prevents repeated exploration and infinite loops.
* DFS on an adjacency-list graph takes `O(V + E)`.
* Recursive DFS can use `O(V)` stack space.
* DFS does not generally guarantee the shortest path.
* It is useful for cycle detection, connected components, topological sorting, and backtracking.
* Tree preorder, inorder, and postorder traversals are DFS-based.
* BFS is the natural alternative when you need level-by-level exploration or shortest paths in an unweighted graph.

The core relationship is:



```text id="w3p4cr"
DFS
 ↓
Go deep
 ↓
Stack
 ↓
Backtrack

Quick Sort: Fast Sorting with Divide and Conquer

Shankar L — Sun, 13 Sep 2026 11:01:00 +0000

Why should you care?

Sorting is everywhere in software.

We sort:

Numbers
Names
Search results
Prices
Database records
Files
Scores
Logs

In the previous article, we learned Merge Sort, which can sort an array in O(n log n) time.

Quick Sort also uses the Divide and Conquer strategy, but it approaches the problem differently.

Instead of splitting the array simply in half, Quick Sort chooses an element called a pivot and rearranges the array so that:

smaller values | pivot | larger values

It then recursively sorts the two sides.

Quick Sort is particularly important because it is often very fast in practice and is a fundamental sorting algorithm to understand.

The Problem

Consider:

[8, 3, 1, 7, 0, 10, 2]

We want:

[0, 1, 2, 3, 7, 8, 10]

One approach is Merge Sort:

Divide → Sort → Merge

Quick Sort takes another approach:

Choose pivot
     ↓
Partition
     ↓
Sort left side
     ↓
Sort right side

For example, choose:

pivot = 7

Rearrange the array around it:

[3, 1, 0, 2]  7  [8, 10]

Now 7 is in its correct final position.

We only need to sort:

[3, 1, 0, 2]

and:

[8, 10]

This is the central idea behind Quick Sort.

The Concept

Quick Sort has three main steps:

1. Choose a pivot
2. Partition the array
3. Recursively sort the partitions

Step 1: Choose a pivot

The pivot can be selected in several ways:

First element
Last element
Middle element
Random element
Median-based strategy

For a simple implementation, we can choose the last element.

Step 2: Partition

Rearrange the array so that:

values < pivot
        ↓
      pivot
        ↓
values > pivot

For example:

[6, 3, 8, 5, 2, 7, 4]
                  ↑
                pivot

After partitioning:

[3, 5, 2, 4] [6] [8, 7]

The exact arrangement can vary depending on the partition algorithm.

The important property is that elements on the left are smaller than the pivot and elements on the right are larger.

The pivot is now in its final position.

Step 3: Recursively sort

Now apply Quick Sort to the two partitions:

[3, 5, 2, 4]

and:

[8, 7]

Continue until the partitions contain zero or one element.

At that point, they are already sorted.

Simple Explanation

Imagine organizing students according to height.

Choose one student as the reference student.

Then ask everyone else to move:

Shorter students → left
Reference student → middle
Taller students → right

Now the reference student's relative position is correct.

You don't need to move that student again.

Then repeat the same process for the shorter group and taller group.

Eventually:

Shorter group
     ↓
sorted

Reference
     ↓

Taller group
     ↓
sorted

Together, everything is sorted.

That's Quick Sort.

Real-world Analogy

Imagine arranging books by thickness.

Pick one book as the pivot.

Place:

Thinner books → left
Pivot book    → middle
Thicker books → right

Now take the left group and repeat.

Then take the right group and repeat.

Eventually, every book ends up in the correct order.

The key idea is not that the pivot immediately sorts the entire collection.

Instead:

The pivot divides one large sorting problem into smaller sorting problems.

Code Example

Let's implement Quick Sort in Java using the Lomuto partition scheme.

public static void quickSort(
        int[] arr,
        int low,
        int high) {

    if (low < high) {

        int pivotIndex = partition(arr, low, high);

        quickSort(arr, low, pivotIndex - 1);

        quickSort(arr, pivotIndex + 1, high);
    }
}

Now the partition function:

public static int partition(
        int[] arr,
        int low,
        int high) {

    int pivot = arr[high];

    int i = low - 1;

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {

            i++;

            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

We can use it like this:

public static void main(String[] args) {

    int[] arr = {
        8, 3, 1, 7, 0, 10, 2
    };

    quickSort(arr, 0, arr.length - 1);

    for (int value : arr) {
        System.out.print(value + " ");
    }
}

Output:

0 1 2 3 7 8 10

Understanding Partition

This is the most important part of Quick Sort.

Consider:

[4, 2, 7, 3, 1, 6]

Suppose:

pivot = 6

We want:

[values ≤ 6]  6  [values > 6]

The partition algorithm scans the array.

Whenever it finds a value smaller than or equal to the pivot, it moves that value toward the left partition.

Eventually we get something like:

[4, 2, 3, 1]  6  [7]

The pivot is now correctly positioned.

We then recursively sort:

[4, 2, 3, 1]

and:

[7]

The right side is already sorted.

Why Does Quick Sort Work?

The most important observation is:

Once the pivot is placed correctly, it never needs to move again.

Suppose:

[4, 2, 1, 3, 8, 7, 5]

Choose:

pivot = 5

After partitioning:

[4, 2, 1, 3] 5 [8, 7]

Everything on the left belongs before 5.

Everything on the right belongs after 5.

Therefore, the original problem:

Sort 7 elements

becomes:

Sort 4 elements
+
Sort 2 elements

The pivot itself is already finished.

This process continues recursively.

Time Complexity

Quick Sort has different performance depending on how well the pivot divides the array.

Best Case

If every pivot approximately divides the array in half:

n
↓
n/2 + n/2
↓
n/4 + n/4 + ...

There are approximately:

log n

levels.

Each level processes approximately:

elements.

Therefore:

O(n log n)

Average Case

With reasonably good pivot selection, Quick Sort has an average complexity of:

O(n log n)

Worst Case

Suppose the array is already sorted:

[1, 2, 3, 4, 5, 6, 7]

and we always choose the last element as the pivot.

Then:

pivot = 7

gives:

[1, 2, 3, 4, 5, 6] 7

pivot = 6

gives:

[1, 2, 3, 4, 5] 6

And so on.

Instead of dividing the problem in half, we get:

n
n - 1
n - 2
n - 3
...

This results in:

O(n²)

Therefore:

Case	Time Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

Space Complexity

Quick Sort is often described as an in-place sorting algorithm because it can partition the array without creating another array proportional to n.

However, recursion requires stack space.

With reasonably balanced partitions:

O(log n)

stack space is typical.

In the worst case, recursion can become:

O(n)

deep.

So:

Case	Auxiliary Space
Average	O(log n)
Worst	O(n)

Implementation details and pivot strategy can affect these values.

Common Mistakes

Mistake 1: Confusing partitioning with sorting

Partitioning does not completely sort the array.

For example:

[3, 1, 4, 2] 5 [8, 7]

The left side isn't necessarily sorted:

3, 1, 4, 2

It only satisfies the partition property.

We still need to recursively sort both sides.

Mistake 2: Forgetting the base case

Quick Sort must stop when the partition contains zero or one element.

if (low < high) {
    // partition and recurse
}

Without this condition, recursion will not terminate correctly.

Mistake 3: Creating bad partitions repeatedly

Consider:

[1, 2, 3, 4, 5, 6, 7]

If the pivot is always the largest element:

[1, 2, 3, 4, 5, 6] 7

we get highly unbalanced partitions.

Repeatedly doing this results in:

O(n²)

worst-case performance.

Pivot selection matters.

Mistake 4: Assuming Quick Sort is always O(n log n)

Quick Sort is:

Average → O(n log n)

but:

Worst case → O(n²)

The quality of the partitions determines the performance.

Mistake 5: Forgetting that duplicates matter

Consider:

[5, 5, 5, 5, 5]

Depending on the partition scheme, many equal values can lead to poor partitioning.

More sophisticated partition strategies, such as three-way partitioning, can handle many duplicates more efficiently.

Advanced Notes

1. Pivot Selection

The pivot is one of the most important decisions in Quick Sort.

Common approaches include:

First element

pivot = arr[low]

Simple, but potentially bad for sorted data.

Last element

pivot = arr[high]

Also simple, but has the same worst-case issue.

Middle element

Choosing a middle position can reduce some bad cases, although it does not guarantee good partitions.

Random pivot

Choose a random element.

Randomization makes consistently bad partition patterns much less likely.

Median-of-three

Choose the median among:

first
middle
last

This can provide better pivot choices for certain input patterns.

2. Lomuto vs Hoare Partition

The implementation above uses Lomuto partitioning.

Another common approach is Hoare partitioning.

Lomuto is generally easier to understand.

Hoare partitioning can perform fewer swaps and is often more efficient in practice.

Understanding both is useful when implementing Quick Sort from scratch.

3. Three-Way Partitioning

Suppose:

[4, 2, 4, 4, 7, 4, 1]

There are many duplicates.

Instead of dividing into only two sections:

< pivot | ≥ pivot

we can create three:

< pivot | = pivot | > pivot

For pivot 4:

[2, 1] | [4, 4, 4, 4] | [7]

The equal section requires no further sorting.

This can make Quick Sort much more efficient when there are many duplicate values.

4. Quick Sort vs Merge Sort

Both are fundamental O(n log n) sorting algorithms on average.

Feature	Quick Sort	Merge Sort
Average Time	O(n log n)	O(n log n)
Worst Time	O(n²)	O(n log n)
Typical Auxiliary Space	O(log n)	O(n)
Stable	Usually No	Yes
In-place	Usually Yes	Usually No
Main Operation	Partition	Merge

The biggest conceptual difference is:

Merge Sort:
Divide → Sort → Merge

Quick Sort:
Partition → Sort left/right

Merge Sort does most of its important work while merging.

Quick Sort does most of its important work while partitioning.

5. Why Quick Sort Can Be Fast in Practice

Even though Merge Sort has a guaranteed O(n log n) worst-case complexity, Quick Sort can be extremely fast in practice.

One reason is that good implementations can operate largely within the original array.

That can provide:

Good cache behavior
Low memory overhead
Fewer allocations
Efficient in-place partitioning

So algorithm analysis tells us the theoretical behavior, while implementation details influence real-world performance.

6. Tail Recursion Optimization

A careful Quick Sort implementation can reduce recursion depth by recursively processing the smaller partition first and handling the larger partition iteratively.

This can help limit stack usage even when partitions are unbalanced.

This is an example of an important engineering principle:

Algorithm design and implementation strategy both matter.

The Bigger Picture

Quick Sort connects several concepts we've already learned.

Big-O

From the previous article:

O(n)
O(log n)
O(n log n)
O(n²)

Quick Sort demonstrates why average-case and worst-case analysis matter.

Its typical performance is:

O(n log n)

but poor pivot choices can produce:

O(n²)

Binary Search

Binary Search taught us the power of reducing a problem by eliminating part of the search space.

Quick Sort uses a related strategy.

Instead of searching:

"Which element am I looking for?"

we ask:

"Which elements belong on each side of the pivot?"

Merge Sort

Merge Sort and Quick Sort both use:

Divide and Conquer

but divide the problem differently.

Merge Sort:
Split by position
        ↓
Sort
        ↓
Merge

Quick Sort:
Choose pivot
        ↓
Partition by value
        ↓
Sort partitions

This distinction is extremely important.

Recursion

Quick Sort is another excellent example of recursion.

quickSort(left)
quickSort(right)

Each call works on a smaller part of the original problem.

The Most Important Mental Model

Don't think:

"Quick Sort chooses a random element and sorts around it."

Think:

"Put one pivot into its final position, then solve the two remaining problems."

For example:

Before:

[8 3 1 7 0 10 2]

Choose pivot = 7

        ↓

[3 1 0 2] 7 [8 10]

        ↓

Sort left      Sort right

        ↓

[0 1 2 3] 7 [8 10]

        ↓

[0 1 2 3 7 8 10]

The pivot creates a boundary:

everything smaller | pivot | everything larger

Once that boundary is correct, the original problem becomes two smaller problems.

That's the essence of Quick Sort.

Summary

Quick Sort is a Divide and Conquer sorting algorithm based on partitioning around a pivot.

The process is:

Choose Pivot
     ↓
Partition
     ↓
Pivot reaches final position
     ↓
Recursively sort left
     ↓
Recursively sort right

Important points:

Quick Sort works by partitioning around a pivot.
The pivot ends up in its final position after partitioning.
The remaining partitions are sorted recursively.
Average time complexity is O(n log n).
Worst-case time complexity is O(n²).
Good pivot selection helps avoid poor partitions.
Quick Sort usually requires less auxiliary memory than Merge Sort.
Standard Quick Sort is generally not stable.
Three-way partitioning is useful when many duplicate values exist.
Quick Sort is one of the most important examples of Divide and Conquer.

The central comparison is:

Merge Sort
    ↓
Divide → Sort → Merge

Quick Sort
    ↓
Partition → Sort → Repeat

Merge Sort : Sorting in O(n log n) Using Divide and Conquer

Shankar L — Sat, 12 Sep 2026 11:00:00 +0000

Why should you care?

Sorting is one of the most common problems in programming.

You may need to sort:

Student marks
Product prices
Names
Search results
Timestamps
Database records
Large datasets

A simple sorting algorithm might work well for a small array, but performance becomes important when the input grows.

Merge Sort can sort n elements in:

O(n log n)

More importantly, Merge Sort introduces a powerful problem-solving technique:

Divide the problem into smaller problems, solve them, and combine the results.

This technique is called Divide and Conquer and appears throughout computer science.

The Problem

Suppose we have:

[38, 27, 43, 3, 9, 82, 10]

We want:

[3, 9, 10, 27, 38, 43, 82]

A straightforward approach is to repeatedly find the smallest element and place it in the correct position.

But as the input grows, some sorting algorithms become very slow.

For example, a quadratic algorithm has:

O(n²)

complexity.

Merge Sort improves this to:

O(n log n)

The key idea is that instead of trying to sort the entire array at once, we repeatedly divide it into smaller pieces.

The Concept

Merge Sort follows three major steps:

Divide
  ↓
Conquer
  ↓
Merge

1. Divide

Split the array into two halves.

[38, 27, 43, 3, 9, 82, 10]

          ↓

[38, 27, 43]    [3, 9, 82, 10]

Continue dividing:

[38, 27, 43]
      ↓
[38] [27, 43]
         ↓
      [27] [43]

Eventually every part contains one element.

2. Conquer

A single-element array is already sorted.

[38]
[27]
[43]

Now we begin combining them.

3. Merge

Merge two sorted arrays into one sorted array.

For example:

[27] + [43]

becomes:

[27, 43]

Then:

[38] + [27, 43]

becomes:

[27, 38, 43]

This merging process continues until the entire array is sorted.

Simple Explanation

Imagine you have a pile of 1,000 papers that need to be sorted by number.

Instead of sorting all 1,000 papers at once:

Split them into two piles.
Split each pile again.
Keep splitting until each pile has one paper.
Combine small sorted piles.
Continue combining larger sorted piles.
Eventually you get one completely sorted pile.

The clever part is the merge.

When two groups are already sorted, combining them is easy.

For example:

Group A:
[2, 7, 15]

Group B:
[3, 5, 12]

Compare the front elements:

2 vs 3 → take 2
7 vs 3 → take 3
7 vs 5 → take 5
7 vs 12 → take 7
15 vs 12 → take 12

Finally:

[2, 3, 5, 7, 12, 15]

This is the core operation behind Merge Sort.

Real-world Analogy

Imagine two queues of students where each queue is already sorted by height.

Queue A:
Short → Medium → Tall

Queue B:
Short → Medium → Tall

You don't need to completely reorder either queue.

You simply compare the person at the front of each queue.

Take the shorter person.

Then compare the new front positions.

Repeat until both queues are empty.

That's exactly what the merge step does.

Merge Sort creates many small sorted sequences and then efficiently merges them.

Code Example

Let's implement Merge Sort in Java.

public static void mergeSort(int[] arr, int left, int right) {

    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

Now we need the merge operation:

public static void merge(
        int[] arr,
        int left,
        int mid,
        int right) {

    int[] temp = new int[right - left + 1];

    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {

        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (int x = 0; x < temp.length; x++) {
        arr[left + x] = temp[x];
    }
}

We can use it like this:

public static void main(String[] args) {

    int[] arr = {
        38, 27, 43, 3, 9, 82, 10
    };

    mergeSort(arr, 0, arr.length - 1);

    for (int value : arr) {
        System.out.print(value + " ");
    }
}

Output:

3 9 10 27 38 43 82

How the code works

The recursive function first keeps splitting:

[38, 27, 43, 3, 9, 82, 10]

into smaller pieces.

Eventually:

[38] [27] [43] [3] [9] [82] [10]

Then merge() starts combining them.

For example:

[27] + [43]

becomes:

[27, 43]

Then:

[38] + [27, 43]

becomes:

[27, 38, 43]

The same process happens on the other side.

Finally:

[27, 38, 43]
+
[3, 9, 10, 82]

becomes:

[3, 9, 10, 27, 38, 43, 82]

Visualizing Merge Sort

The complete process looks like this:

Starting array:

[38, 27, 43, 3, 9, 82, 10]

Divide

             [38 27 43 3 9 82 10]
                    /       \
             [38 27 43]   [3 9 82 10]
              /    \        /      \
           [38]  [27 43]  [3 9]  [82 10]
                  / \      / \     / \
                [27][43] [3][9] [82][10]

Now every piece is individually sorted.

Merge

[27] + [43]
      ↓
[27 43]

[3] + [9]
      ↓
[3 9]

[82] + [10]
       ↓
[10 82]

Continue:

[38] + [27 43]
        ↓
[27 38 43]

[3 9] + [10 82]
        ↓
[3 9 10 82]

Finally:

[27 38 43]
      +
[3 9 10 82]

        ↓

[3 9 10 27 38 43 82]

Time Complexity

Merge Sort has:

O(n log n)

time complexity.

Why?

There are two important parts.

Number of levels

Every time we divide the array, its size is approximately halved.

Therefore, the number of levels is:

log n

Work at each level

At every level, all elements are processed during merging.

That's:

O(n)

work.

Therefore:

O(n) × O(log n)

gives:

O(n log n)

This applies to the best, average, and worst cases for the standard Merge Sort algorithm.

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Space Complexity

The implementation above creates temporary arrays during merging.

Therefore, its auxiliary space complexity is:

O(n)

The recursive calls also require stack space:

O(log n)

But the temporary merge arrays dominate the additional memory usage.

So the typical overall auxiliary space is:

O(n)

This is one of the major trade-offs of Merge Sort:

Excellent time complexity
        ↓
O(n log n)

But

Additional memory required
        ↓
O(n)

Common Mistakes

Mistake 1: Forgetting the base case

Recursive Merge Sort needs to stop when the range contains one element.

if (left >= right) {
    return;
}

Without this condition, the recursion never terminates.

Mistake 2: Incorrectly calculating the middle

Avoid:

int mid = (left + right) / 2;

For large indexes, addition can overflow.

Prefer:

int mid = left + (right - left) / 2;

This is the same safe calculation we saw with Binary Search.

Mistake 3: Forgetting the remaining elements

During merging, one side may become empty first.

For example:

Left:
[2, 5, 8]

Right:
[3]

After selecting:

2
3

the left side still contains:

5, 8

These elements must be copied into the result.

That's why we need:

while (i <= mid) {
    temp[k++] = arr[i++];
}

and:

while (j <= right) {
    temp[k++] = arr[j++];
}

Mistake 4: Thinking the merge operation sorts arbitrary arrays

The merge step assumes that both input portions are already sorted.

For example:

[2, 7, 10]
[1, 5, 9]

can be efficiently merged.

But:

[7, 2, 10]
[9, 1, 5]

cannot simply be merged correctly without first sorting those portions.

That's why Merge Sort works from the bottom up: smaller pieces become sorted before larger pieces are merged.

Advanced Notes

1. Merge Sort is Stable

A sorting algorithm is called stable if equal elements maintain their original relative order.

Consider:

(John, 90)
(Alex, 90)

If sorting by marks, a stable algorithm keeps:

John, 90
Alex, 90

in their original relative order.

Our merge implementation uses:

if (arr[i] <= arr[j])

rather than:

if (arr[i] < arr[j])

This allows the element from the left half to be selected first when values are equal.

Therefore, this implementation is stable.

2. Merge Sort vs Quick Sort

Both are important O(n log n) sorting algorithms.

Feature	Merge Sort	Quick Sort
Average Time	O(n log n)	O(n log n)
Worst Time	O(n log n)	O(n²)
Stable	Yes	Usually No
Extra Space	O(n)	Typically O(log n) stack
Main Idea	Divide + Merge	Divide around Pivot

The biggest difference is the strategy.

Merge Sort divides the array and then performs a carefully controlled merge.

Quick Sort chooses a pivot and partitions the elements around it.

3. Bottom-Up Merge Sort

The implementation we've seen is top-down Merge Sort.

It starts with the entire array:

[entire array]

and recursively divides it.

There is another approach called bottom-up Merge Sort.

It starts with individual elements:

[38] [27] [43] [3] [9] [82] [10]

Then merges pairs:

[27 38] [3 43] [9 82] [10]

Then:

[3 27 38 43] [9 10 82]

And finally:

[3 9 10 27 38 43 82]

It avoids recursion and can be useful in certain implementations.

4. Merge Sort on Linked Lists

Merge Sort is particularly well suited to linked lists.

Why?

Linked lists don't provide efficient random access.

An algorithm that constantly needs:

arr[mid]

is not ideal for a linked list.

But Merge Sort primarily requires:

Splitting the list
Traversing nodes
Merging sorted lists

These operations work naturally with linked lists.

Therefore, Merge Sort is a common choice for sorting linked lists.

5. External Sorting

What if the dataset is too large to fit into memory?

Suppose you have:

500 GB of data

but only:

16 GB RAM

You cannot load everything into memory at once.

External Merge Sort can:

Read manageable chunks.
Sort each chunk.
Store sorted chunks.
Merge those sorted chunks.

This makes Merge Sort useful for large-scale data processing and external storage.

The Bigger Picture

Merge Sort connects several concepts we've already learned.

Big-O

We just learned that:

O(n log n)

is generally much more scalable than:

O(n²)

Merge Sort is one of the classic algorithms that achieves O(n log n) sorting.

Binary Search

Binary Search taught us the power of:

Divide the search space.

Merge Sort applies a related idea:

Divide the problem.
Solve smaller problems.
Combine the results.

Recursion

Merge Sort is a classic example of recursion.

A large problem becomes smaller versions of the same problem:

sort(large array)
       ↓
sort(left half)
sort(right half)
       ↓
merge

Divide and Conquer

This is the deeper lesson.

The pattern is:

                 Problem
                    ↓
              Divide it
              /       \
         Subproblem  Subproblem
              \       /
               Solve
                 ↓
                Merge

This strategy appears in many algorithms beyond sorting.

The Most Important Mental Model

Don't memorize Merge Sort as a collection of recursive function calls.

Remember:

Split until the pieces are easy, then merge them back in sorted order.

The entire algorithm can be summarized as:

        [8 3 5 4 7 6 1 2]
                 ↓
          Split repeatedly
                 ↓
       [8] [3] [5] [4] [7] [6] [1] [2]
                 ↓
          Merge sorted pairs
                 ↓
       [3 8] [4 5] [6 7] [1 2]
                 ↓
          Merge larger groups
                 ↓
       [3 4 5 8] [1 2 6 7]
                 ↓
             Final merge
                 ↓
       [1 2 3 4 5 6 7 8]

The algorithm doesn't magically know where every element belongs.

It makes the problem manageable by ensuring that every merge combines two already-sorted sequences.

Summary

Merge Sort is a comparison-based sorting algorithm based on Divide and Conquer.

The process is:

Divide
  ↓
Sort smaller pieces
  ↓
Merge

Important points:

It repeatedly divides the array into halves.
Single-element arrays are considered sorted.
Sorted portions are merged together.
Time complexity is O(n log n) in best, average, and worst cases.
Standard implementations require O(n) auxiliary space.
Merge Sort is stable.
It works particularly well with linked lists.
It can be adapted for external sorting.
It teaches the important Divide and Conquer technique.

The progression is:

Binary Search
     ↓
Divide the search space
     ↓
Merge Sort
     ↓
Divide the problem
     ↓
Solve smaller problems
     ↓
Combine the results

Binary Search : Finding Data in O(log n)

Shankar L — Fri, 11 Sep 2026 10:58:00 +0000

Why should you care?

Searching is one of the most common operations in programming.

Suppose you have an array containing 1 million sorted numbers and need to find one particular value.

A simple approach is to check each element:

1 → 2 → 3 → 4 → ...

In the worst case, you may need to check all 1 million elements.

But what if you could eliminate half of the remaining elements after every comparison?

That's exactly what Binary Search does.

Instead of checking every element, Binary Search repeatedly divides the search space in half.

This gives us:

O(log n)

which is dramatically faster than:

O(n)

for large datasets.

The Problem

Consider this sorted array:

[10, 20, 30, 40, 50, 60, 70, 80, 90]

We want to find:

A linear search checks:

That's 7 comparisons.

Binary Search takes a different approach.

Start with the middle:

[10, 20, 30, 40, 50, 60, 70, 80, 90]
                    ↑
                   50

We compare:

70 > 50

Therefore, we know the answer cannot be in the left half.

We discard:

10 20 30 40 50

Now search:

60 70 80 90

Check the middle:

60 70 80 90
   ↑
   70

We found it.

Instead of examining every element, we eliminated large portions of the array at each step.

The Concept

Binary Search works by maintaining a search range:

left
right

At every step:

Find the middle element.
Compare it with the target.
If it matches, return the result.
If the target is smaller, search the left half.
If the target is larger, search the right half.
Repeat until the search range becomes empty.

The fundamental operation is:

middle = (left + right) / 2

A safer version in Java is:

int mid = left + (right - left) / 2;

This avoids integer overflow when left and right are very large.

Simple Explanation

Imagine you're guessing a number between:

1 and 100

Someone tells you:

"I'm thinking of a number."

You could guess:

1
2
3
4
5
...

That is essentially linear search.

Instead, guess:

If they say:

"Too low."

You immediately know the answer is between:

51 and 100

Now guess:

If they say:

"Too high."

You know the answer is between:

51 and 74

Every guess removes roughly half the possibilities.

That's Binary Search.

Real-world Analogy

Imagine searching for a word in a physical dictionary.

You don't open the dictionary at the first page and read every word.

You open somewhere near the middle.

Suppose you're looking for:

"programming"

but you land around:

"machine"

Since programming comes after machine alphabetically, you ignore everything before that point.

You open the middle of the remaining section.

Then repeat.

Entire dictionary
       ↓
    Half left
       ↓
    Half left
       ↓
    Half left
       ↓
      ...

This is Binary Search.

The dictionary works because its words are sorted.

And that's the most important requirement for traditional Binary Search:

The search space must have an ordering that lets you eliminate half of it.

Code Example

Let's implement Binary Search in Java.

public static int binarySearch(int[] arr, int target) {

    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Example:

public static void main(String[] args) {

    int[] numbers = {
        10, 20, 30, 40, 50,
        60, 70, 80, 90
    };

    int result = binarySearch(numbers, 70);

    System.out.println(result);
}

Output:

Because:

numbers[6] = 70

Understanding the Algorithm Step by Step

Suppose:

arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]
target = 70

Initially:

left = 0
right = 8

Calculate:

mid = 0 + (8 - 0) / 2
    = 4

So:

arr[4] = 50

Compare:

70 > 50

Therefore:

left = mid + 1

Now:

left = 5
right = 8

Next middle:

mid = 6

And:

arr[6] = 70

Target found.

Why Is It O(log n)?

Suppose we have:

n = 1,000,000

elements.

Binary Search repeatedly divides the search space:

The number of times we can divide n by 2 before reaching 1 is approximately:

log₂(n)

Therefore:

Binary Search = O(log n)

For one million elements, that means only around 20 divisions in the worst case.

Compare that with linear search:

Linear Search  → O(n)
Binary Search  → O(log n)

This difference becomes enormous as n grows.

Common Mistakes

Mistake 1: Using Binary Search on unsorted data

Consider:

[50, 10, 80, 30, 70]

There is no useful ordering.

If we inspect 80 and the target is 30, we cannot safely conclude which half contains the target.

Binary Search depends on being able to eliminate a portion of the search space.

For a standard array implementation, sorting is therefore a prerequisite.

Mistake 2: Updating the boundaries incorrectly

Suppose:

if (arr[mid] < target) {
    left = mid;
}

This can cause the algorithm to repeatedly examine the same middle element.

Usually we need:

left = mid + 1;

Similarly:

right = mid - 1;

The searched middle element has already been examined, so it should be excluded from the next range.

Mistake 3: Using `(left + right) / 2` blindly

You will often see:

int mid = (left + right) / 2;

It works for normal-sized arrays.

But if left + right exceeds the maximum integer value, integer overflow can occur.

Prefer:

int mid = left + (right - left) / 2;

This is a small implementation detail, but it is a good habit.

Mistake 4: Forgetting the target may not exist

Consider:

[10, 20, 30, 40, 50]

and search for:

The algorithm eventually reaches an empty search range.

Therefore, we need:

return -1;

or another appropriate "not found" result.

Mistake 5: Assuming Binary Search is always better

Binary Search has a major requirement:

The data must be ordered in a searchable way.

If you have an unsorted array and only need one search, sorting it first may cost:

O(n log n)

That may not be worth doing.

If you're going to perform thousands of searches, however, sorting once and then using Binary Search can be very beneficial.

Advanced Notes

1. Recursive Binary Search

Binary Search can also be implemented recursively.

public static int binarySearch(
        int[] arr,
        int left,
        int right,
        int target) {

    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    }

    if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, right, target);
    }

    return binarySearch(arr, left, mid - 1, target);
}

The time complexity remains:

O(log n)

But the recursive version uses call-stack space:

O(log n)

The iterative version generally uses:

O(1)

additional space.

2. Finding the First Occurrence

Suppose the array contains duplicates:

[10, 20, 20, 20, 30]

Searching for:

may return any matching position depending on the implementation.

But sometimes we need the first occurrence.

We can continue searching toward the left after finding a match.

public static int firstOccurrence(int[] arr, int target) {

    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {

            result = mid;
            right = mid - 1;

        } else if (arr[mid] < target) {

            left = mid + 1;

        } else {

            right = mid - 1;
        }
    }

    return result;
}

This is still:

O(log n)

3. Finding the Last Occurrence

We can do the opposite.

When we find the target, continue searching toward the right:

if (arr[mid] == target) {
    result = mid;
    left = mid + 1;
}

This allows Binary Search to solve more than simple "does this value exist?" problems.

4. Lower Bound and Upper Bound

Binary Search can be generalized to find boundaries.

For example:

[1, 2, 2, 2, 4, 5]

We can find:

First position where value is ≥ target
First position where value is > target

These ideas are commonly called:

Lower Bound
Upper Bound

They are extremely useful in competitive programming and algorithmic problem solving.

5. Binary Search on the Answer

Binary Search isn't limited to searching arrays.

Sometimes the search space is a range of possible answers.

Suppose the question is:

What is the minimum capacity required to complete a task within k days?

You might have:

minimum possible answer
        ↓
maximum possible answer

If you can determine whether a particular capacity is sufficient, you can binary-search the answer space.

This technique is called Binary Search on Answer.

It is one of the most important advanced applications of Binary Search.

6. Complexity

For an array containing n elements:

Operation	Complexity
Best-case search	O(1)
Worst-case search	O(log n)
Average-case search	O(log n)
Iterative space	O(1)
Recursive space	O(log n)

The key improvement is:

O(n) → O(log n)

when the search space can be repeatedly halved.

The Bigger Picture

Binary Search connects directly to the Big-O concept from the previous article.

We learned:

O(n)

means the work grows linearly.

Binary Search gives us:

O(log n)

because each operation removes approximately half of the remaining search space.

It also connects to the data structures we've already studied.

Array

Arrays provide efficient indexing:

arr[index]

which is:

O(1)

When the array is sorted, we can combine that efficient access with Binary Search.

Binary Search Tree

A Binary Search Tree uses a similar idea:

smaller values → left
larger values  → right

At every step, we choose a direction based on comparison.

So Binary Search and Binary Search Trees share the same fundamental strategy:

Use ordering to eliminate unnecessary possibilities.

Tries

Our previous topic, Trie, also reduces the search space by following the relevant characters.

Different data structures solve different search problems, but the underlying principle is similar:

Don't search what you already know cannot contain the answer.

The Most Important Mental Model

Don't think of Binary Search as:

"Look at the middle element."

The deeper idea is:

"Every comparison should eliminate as much of the search space as possible."

The middle element is simply the best choice when the search space is ordered and the two sides are roughly equal.

Visualize:

Before:

[ 1  2  3  4  5  6  7  8  9 ]
              ↑
             mid

After one comparison:

[ 6  7  8  9 ]

Then:

[ 6  7  8  9 ]
      ↑
     mid

After another comparison:

[ 6  7 ]

And continue.

The algorithm is powerful because one comparison destroys an entire portion of the search space.

Summary

Binary Search is an efficient searching algorithm that works by repeatedly dividing an ordered search space in half.

Key ideas:

The search space must be ordered or otherwise partitionable.
Maintain left and right boundaries.
Calculate the middle position.
Compare the middle element with the target.
Discard the impossible half.
Repeat until the target is found or the range becomes empty.
Worst-case time complexity is O(log n).
Iterative Binary Search uses O(1) additional space.
It can be extended to find first/last occurrences and boundaries.
Binary Search can also be applied to an abstract range of possible answers.

The fundamental comparison is:

Linear Search → O(n)
Binary Search → O(log n)

For a million sorted elements, that difference can mean checking roughly:

1,000,000

elements versus roughly:

steps.

Big-O Notation : Understanding Algorithm Efficiency

Shankar L — Thu, 10 Sep 2026 10:57:00 +0000

Why should you care?

You can write a program that works perfectly and still have a serious problem: it might be too slow when the input becomes large.

Consider two algorithms that search for an element.

Algorithm A takes:

10 operations for 10 elements
100 operations for 100 elements
1,000 operations for 1,000 elements

Algorithm B takes:

3 operations for 10 elements
7 operations for 100 elements
10 operations for 1,000 elements

Both might work perfectly for small inputs.

But as the input grows, their performance becomes dramatically different.

This is where Big-O notation becomes important.

Big-O helps us understand how the running time or memory requirements of an algorithm grow as the input size increases.

It is one of the most important concepts in computer science because it allows us to answer:

"How will this algorithm behave when my input becomes really large?"

The Problem

Suppose you have an array:

[10, 20, 30, 40, 50]

and want to find:

You could check every element:

10 → 20 → 30 → 40

For five elements, this is trivial.

But imagine:

10,000 elements

or:

1,000,000 elements

or:

1,000,000,000 elements

Now the algorithm's growth rate matters.

Another algorithm might be able to find the same element much faster.

For example, binary search can repeatedly divide the search space in half.

So we need a mathematical way to describe algorithmic growth.

That's what Big-O notation provides.

The Concept

Big-O notation describes the asymptotic growth of an algorithm.

In simple terms:

Big-O tells us how the amount of work grows as the input size grows.

We usually represent input size using:

For example:

n = number of elements in an array

If an algorithm examines every element:

n operations

we write:

O(n)

If it repeatedly divides the input in half:

O(log n)

If it compares every element with every other element:

O(n²)

Simple Explanation

Imagine you are looking for a person in a line.

O(1) — Constant

The person is always standing at a known position.

You immediately access them.

1 operation

It doesn't matter whether there are:

10 people

or:

1,000,000 people

The work remains approximately constant.

Therefore:

O(1)

O(n) — Linear

You check people one by one.

Person 1
Person 2
Person 3
...
Person n

If the number of people doubles, the maximum amount of work approximately doubles.

Therefore:

O(n)

O(log n) — Logarithmic

Imagine the people are sorted and you repeatedly eliminate half of them.

1,000,000
   ↓
500,000
   ↓
250,000
   ↓
125,000
   ↓
...

You don't need to inspect everyone.

The search space shrinks exponentially.

Therefore:

O(log n)

Binary search is the classic example.

O(n²) — Quadratic

Suppose every person needs to compare themselves with every other person.

For:

n people

you can end up with approximately:

n × n

comparisons.

Therefore:

O(n²)

Nested loops are a common source of quadratic complexity.

Real-world Analogy

Imagine finding a book in a library.

O(n)

You start at the first book and check every book one by one.

Book 1
Book 2
Book 3
...
Book n

O(log n)

The books are sorted alphabetically.

You open the middle of the library.

If your book should come before that point, ignore the second half.

Then repeat.

1,000,000 books
        ↓
500,000
        ↓
250,000
        ↓
125,000
        ↓
...

This is logarithmic behavior.

O(1)

The library system tells you:

Computer Science → Shelf 42 → Position 17

You directly access the location.

That's constant-time access.

Code Example

Let's look at some common examples.

O(1)

int getFirst(int[] arr) {
    return arr[0];
}

Regardless of the array size:

10 elements
100 elements
1,000,000 elements

we access one position.

Therefore:

O(1)

O(n)

void printAll(int[] arr) {

    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

If there are n elements, the loop executes n times.

Therefore:

O(n)

O(n²)

void printPairs(int[] arr) {

    for (int i = 0; i < arr.length; i++) {

        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

The outer loop executes:

n times

The inner loop also executes:

n times

Total:

n × n = n²

Therefore:

O(n²)

O(log n)

Binary search is a classic example:

int binarySearch(int[] arr, int target) {

    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Every iteration eliminates approximately half of the remaining elements.

Therefore:

O(log n)

Common Big-O Complexities

From generally more scalable to less scalable:

O(1)
   ↓
O(log n)
   ↓
O(n)
   ↓
O(n log n)
   ↓
O(n²)
   ↓
O(n³)
   ↓
O(2ⁿ)
   ↓
O(n!)

A rough intuition:

Complexity	Common Example
O(1)	Array access
O(log n)	Binary search
O(n)	Linear search
O(n log n)	Merge sort
O(n²)	Nested loops
O(n³)	Three nested loops
O(2ⁿ)	Some recursive subset algorithms
O(n!)	Brute-force permutations

The exact performance depends on the algorithm and implementation, but this hierarchy is extremely useful.

Dropping Constants

Consider:

void example(int[] arr) {

    for (int x : arr) {
        System.out.println(x);
    }

    for (int x : arr) {
        System.out.println(x);
    }
}

The first loop takes:

operations.

The second takes:

operations.

Total:

2n

Technically:

O(2n)

But Big-O focuses on the growth rate, so we simplify:

O(n)

We drop constant factors.

Similarly:

O(5n) → O(n)

O(100n) → O(n)

Dropping Lower-Order Terms

Consider:

O(n² + n)

As n becomes very large, n² grows much faster than n.

Therefore:

O(n² + n)

becomes:

O(n²)

Similarly:

O(n³ + n² + n)

becomes:

O(n³)

The dominant term determines the asymptotic growth.

Time Complexity vs Space Complexity

Big-O isn't only about execution time.

We can also analyze memory usage.

Time Complexity

How does the amount of computation grow?

Example:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

Time:

O(n)

Space Complexity

How much additional memory does the algorithm need?

Example:

int[] copy = new int[n];

The new array grows with n.

Therefore:

O(n)

space.

An algorithm can therefore have:

Time:  O(n)
Space: O(1)

or:

Time:  O(n)
Space: O(n)

These are separate measurements.

Common Mistakes

Mistake 1: Thinking Big-O gives the exact execution time

If an algorithm is:

O(n)

that does not mean it takes exactly n milliseconds.

Big-O describes growth, not a stopwatch measurement.

Two O(n) algorithms can have very different real-world performance.

Mistake 2: Assuming O(1) means instantaneous

O(1) means the operation does not grow with input size.

It doesn't mean:

0 seconds

or:

always extremely fast

A constant-time operation could still perform a relatively expensive fixed amount of work.

Mistake 3: Counting every line equally

Consider:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

The important question isn't:

"How many lines are in the code?"

Instead ask:

"How many times does each operation execute as n grows?"

The loop executes n times.

Therefore:

O(n)

Mistake 4: Assuming nested loops always mean O(n²)

Consider:

for (int i = 0; i < n; i++) {

    for (int j = 0; j < 10; j++) {
        System.out.println(i + j);
    }
}

The inner loop always runs only 10 times.

Total work:

10n

Therefore:

O(n)

not:

O(n²)

Nested loops matter based on how their iteration counts depend on n.

Mistake 5: Ignoring input characteristics

Consider searching an array.

Linear search can be:

Best case:    O(1)
Worst case:   O(n)

If the target is the first element, we're done immediately.

If it is the last element, we may inspect everything.

Big-O is often used for worst-case analysis, but best-case and average-case complexity can also be important.

Advanced Notes

1. Big-O vs Big-Theta vs Big-Omega

These notations are related but technically different.

Big-O:

O(f(n))

represents an asymptotic upper bound.

Big-Omega:

Ω(f(n))

represents an asymptotic lower bound.

Big-Theta:

Θ(f(n))

represents a tight asymptotic bound.

For example, if an algorithm consistently grows linearly:

Θ(n)

is a more precise statement than simply:

O(n)

because O(n) technically allows functions that grow more slowly as well.

In everyday algorithm discussions, however, "Big-O" is commonly used to describe asymptotic complexity generally.

2. Amortized Complexity

Some operations are occasionally expensive but cheap on average over a sequence of operations.

A dynamic array is a good example.

Most insertions may take:

O(1)

But occasionally the array becomes full and needs to resize.

That particular operation can take:

O(n)

Yet insertion has an amortized O(1) complexity.

This is why analyzing a sequence of operations can sometimes be more useful than analyzing one operation in isolation.

3. Recursive Algorithms

Big-O becomes especially important with recursion.

Consider:

void countdown(int n) {

    if (n == 0) {
        return;
    }

    System.out.println(n);

    countdown(n - 1);
}

There are n recursive calls.

Therefore:

Time:  O(n)
Space: O(n)

The space complexity comes from the recursive call stack.

4. Exponential Complexity

Consider an algorithm that branches into two recursive calls:

void solve(int n) {

    if (n <= 0) {
        return;
    }

    solve(n - 1);
    solve(n - 1);
}

The number of calls grows approximately exponentially.

Its complexity is roughly:

O(2ⁿ)

This becomes impractical very quickly.

For example:

n = 10
→ around 1,000 operations

n = 20
→ around 1,000,000 operations

n = 30
→ around 1,000,000,000 operations

This is why algorithm design matters so much.

5. Big-O and the Data Structures We Learned

Big-O connects directly to the data structures we've studied.

For example:

Data Structure	Operation	Typical Complexity
Array	Access	O(1)
Array	Search	O(n)
Linked List	Access	O(n)
Linked List	Insert at head	O(1)
Stack	Push	O(1)
Stack	Pop	O(1)
Queue	Enqueue	O(1)
Queue	Dequeue	O(1)
Hash Table	Search	O(1) average
BST	Search	O(log n) average
Heap	Insert	O(log n)
Heap	Extract min/max	O(log n)
Graph	BFS/DFS	O(V + E)
Trie	Search	O(L)

This is one reason Big-O should be learned alongside data structures.

The data structure you choose directly affects the complexity of the operations your program performs.

The Bigger Picture

Big-O gives us a way to compare the algorithms and data structures we have learned.

Imagine searching for an element.

With an unsorted array:

O(n)

With a sorted array using binary search:

O(log n)

With a hash table:

O(1) average

With a balanced search tree:

O(log n)

The problem may be the same:

"Find this element."

But the data structure changes the algorithmic complexity.

This is one of the central ideas of computer science:

Choosing the right data structure can transform the performance of an algorithm.

The Most Important Mental Model

Don't memorize Big-O as a list of symbols.

Instead, ask:

"If I make the input 10× larger, how much more work does my algorithm have to do?"

For example:

O(1)

Input grows → work stays roughly the same.

O(log n)

Input grows → work increases slowly.

O(n)

Input grows 10× → work grows roughly 10×.

O(n²)

Input grows 10× → work grows roughly 100×.

O(2ⁿ)

Input grows slightly → work can explode.

That mental model is more useful than simply memorizing the notation.

Summary

Big-O notation describes how an algorithm's resource requirements grow as the input size increases.

The most important complexities to recognize are:

O(1)       Constant
O(log n)   Logarithmic
O(n)       Linear
O(n log n) Linearithmic
O(n²)      Quadratic
O(2ⁿ)      Exponential
O(n!)      Factorial

Remember:

Big-O describes growth, not exact execution time.
n usually represents input size.
Constants are ignored.
Lower-order terms are ignored.
Time and space complexity are separate.
Worst-case complexity is commonly discussed, but best and average cases also matter.
Data-structure choices strongly affect complexity.
A theoretically better complexity can become dramatically more important as n grows.

The ultimate goal isn't to memorize:

O(1), O(log n), O(n), O(n²)...

The goal is to look at an algorithm and predict how it will scale.

Trie The Data Structure Behind Fast Prefix Searching

Shankar L — Wed, 09 Sep 2026 10:52:00 +0000

Why should you care?

Imagine typing app into a search box and immediately getting:

apple
application
apply
appointment

How does the system find all words beginning with app so efficiently?

One data structure designed specifically for this kind of problem is a Trie.

Tries are useful for:

Autocomplete
Spell checkers
Search suggestions
Dictionary implementations
Prefix matching
IP routing
Word games
Text processing

Unlike many data structures we've studied so far, a Trie is designed around characters and prefixes.

The Problem

Suppose we have these words:

apple
app
application
apply
banana
band
bandage

We want to answer questions such as:

Does "apple" exist?
Does "app" exist?
What words start with "app"?
What words start with "ban"?

A simple approach is to store the words in an array or list and compare each word.

For example:

apple
application
apply
banana
band
bandage

To find words beginning with app, we may have to inspect many strings.

Hash tables are excellent for checking whether an exact word exists:

"apple" → exists
"app"   → exists

But they are not naturally designed for:

"Give me every word beginning with app"

We need a structure that represents shared prefixes efficiently.

That is where a Trie comes in.

The Concept

A Trie is a tree-like data structure used to store strings.

Each path from the root represents characters in a word.

For example, consider:

app
apple
apply

The Trie can look conceptually like:

The important idea is that common prefixes are shared.

The words:

app
apple
application
apply

all begin with:

app

Instead of storing app repeatedly, the Trie stores those characters along one shared path.

Each node generally contains:

Links to child nodes
Information about whether a complete word ends there

For example:

Node
 ├── children
 └── isEndOfWord

Simple Explanation

Think of a Trie as a character-by-character dictionary.

Suppose we insert:

cat
car
can

The Trie begins with:

root
 |
 c
 |
 a

Then the paths split:

The prefix:

ca

is shared.

But the final characters:

t
r
n

represent different words.

The key point is:

Each level of the Trie represents another character in the word.

So if we search for:

car

we follow:

root → c → a → r

If the r node marks the end of a word, car exists.

Real-world Analogy

Imagine a large dictionary organized like a filing system.

Instead of sorting complete words alphabetically, you organize them character by character.

Start with:

A
B
C
...

Under C:

CA
CB
CC
CD
...

Under CA:

CAB
CAC
CAD
...

Now suppose you want every word beginning with:

CAR

You simply navigate:

C → A → R

Once you reach CAR, everything below that point represents words beginning with CAR.

That is exactly what a Trie does.

Code Example

Let's implement a simple Trie in Java.

class TrieNode {

    TrieNode[] children = new TrieNode[26];

    boolean isEndOfWord;
}

Each node contains 26 possible children:

a → index 0
b → index 1
c → index 2
...
z → index 25

Now let's create the Trie:

class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {

        TrieNode current = root;

        for (char c : word.toCharArray()) {

            int index = c - 'a';

            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }

            current = current.children[index];
        }

        current.isEndOfWord = true;
    }

    public boolean search(String word) {

        TrieNode current = root;

        for (char c : word.toCharArray()) {

            int index = c - 'a';

            if (current.children[index] == null) {
                return false;
            }

            current = current.children[index];
        }

        return current.isEndOfWord;
    }
}

We can use it like this:

public class Main {

    public static void main(String[] args) {

        Trie trie = new Trie();

        trie.insert("apple");
        trie.insert("app");
        trie.insert("apply");

        System.out.println(trie.search("app"));
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("banana"));
    }
}

Output:

true
true
false

How insertion works

When inserting:

apple

we follow:

root
 ↓
a
 ↓
p
 ↓
p
 ↓
l
 ↓
e

At e, we set:

isEndOfWord = true;

Now insert:

app

The nodes:

a → p → p

already exist.

We simply follow them and mark the p node as another word ending.

This is why prefixes are shared.

Prefix Search

One of the biggest advantages of a Trie is prefix searching.

Suppose we inserted:

apple
app
application
apply
banana
band

We can ask:

Does any word start with "app"?

We don't need to compare against every word.

We simply follow:

a → p → p

If that path exists, the prefix exists.

A simple prefix-check method:

public boolean startsWith(String prefix) {

    TrieNode current = root;

    for (char c : prefix.toCharArray()) {

        int index = c - 'a';

        if (current.children[index] == null) {
            return false;
        }

        current = current.children[index];
    }

    return true;
}

Now:

trie.startsWith("app");

returns:

true

while:

trie.startsWith("xyz");

returns:

false

Time Complexity

Let:

L = length of the word

Then:

Operation	Time Complexity
Insert	O(L)
Search	O(L)
Prefix Search	O(L)
Delete	O(L)

The important observation is that the complexity depends on the length of the string, not directly on the number of words stored.

For example, searching for:

application

requires following roughly 11 characters regardless of whether the Trie contains:

100 words

or:

1,000,000 words

The actual performance also depends on the implementation and alphabet.

Common Mistakes

Mistake 1: Thinking every node represents a complete word

Consider:

car
cart

The node representing:

car

is shared by both words.

Therefore, we need:

isEndOfWord

to distinguish between:

car

and:

cart

A node can be:

A prefix only
The end of a word
Both a prefix and the end of a word

Mistake 2: Assuming Tries are always memory efficient

Tries can consume significant memory.

If every node contains:

TrieNode[] children = new TrieNode[26];

each node reserves space for 26 references.

For a large vocabulary, this can become expensive.

Alternative implementations can use:

Map<Character, TrieNode>

instead of a fixed array.

This saves space when each node has only a few children, although hash-map overhead can also be significant.

Mistake 3: Ignoring case and character sets

The example implementation assumes:

a-z

Only.

Real applications may need:

A-Z
0-9
Unicode
spaces
punctuation

A production Trie therefore needs a carefully designed character representation.

Advanced Notes

1. Trie vs Hash Table

A hash table is excellent for:

Does this exact word exist?

A Trie is excellent for:

Does this prefix exist?
What words begin with this prefix?

For example:

Hash Table

apple → value
apply → value
banana → value

Trie:

a
|
p
|
p
├── l → e
└── l → y

The Trie explicitly represents the relationship between strings and their prefixes.

2. Trie vs Binary Search Tree

A Binary Search Tree organizes elements based on comparisons.

A Trie organizes strings based on their characters.

For example:

BST:
Compare complete strings

Trie:
Compare character by character

This makes Tries particularly useful for prefix-based operations.

3. Autocomplete

Suppose a user types:

pro

The application navigates to the node representing:

p → r → o

Then it explores the subtree below that node.

It might find:

program
programming
programmer
project
process

These become autocomplete suggestions.

4. Compressed Trie

A normal Trie can contain many nodes with only one child.

For example:

c
|
o
|
m
|
p
|
u
|
t
|
e
|
r

A compressed Trie can combine chains of single-child nodes:

computer

This reduces the number of nodes and can improve memory usage.

A compressed Trie is also commonly called a Radix Tree or Patricia Trie, depending on the specific variant.

5. Deletion

Deleting a word from a Trie requires care.

Suppose we have:

car
cart

If we delete:

car

we cannot necessarily delete the r node because:

cart

still needs it.

Instead, we can simply change:

isEndOfWord = false;

If the nodes are no longer needed by any other word, they can potentially be removed.

6. Unicode and Memory Optimization

For large-scale systems, a fixed array like:

new TrieNode[26]

may not be appropriate.

Other approaches include:

HashMap
Sorted Map
Compressed Trie
Ternary Search Tree
Memory-mapped structures

The correct choice depends on the alphabet, dataset size, access patterns, and memory constraints.

The Bigger Picture

Look at how our data structures have evolved:

Arrays
   ↓
Linked Lists
   ↓
Stacks / Queues
   ↓
Hash Tables
   ↓
Trees
   ↓
Heaps
   ↓
Graphs
   ↓
Tries

Each structure solves a different kind of problem.

A Hash Table gives us fast exact lookup.

A Heap gives us efficient priority-based access.

A Graph represents relationships.

A Trie represents strings and their prefixes.

The interesting part is that a Trie is actually built on a familiar idea:

Trie = Tree + Character-based navigation

This is an important connection.

We learned that trees allow one node to have multiple children.

A Trie takes that idea and uses each level to represent another character.

The Most Important Mental Model

Remember this:

A Trie is a tree where each path represents a string, and shared paths represent shared prefixes.

For example:

The path:

root → c → a → t

represents:

cat

The path:

root → c → a → r

represents:

car

The shared path:

c → a

represents their common prefix.

If you remember "tree of characters", you understand the core idea of a Trie.

Summary

A Trie is a tree-based data structure designed primarily for storing and searching strings.

Key ideas:

Each node represents a character.
A path from the root represents a string.
Common prefixes are shared.
isEndOfWord identifies complete words.
Search takes O(L), where L is the string length.
Prefix searches are one of its biggest strengths.
Tries are useful for autocomplete and dictionary-like applications.
They can consume significant memory.
Compressed Tries can reduce memory usage.

The most important distinction is:

Hash Table → Exact lookup

Trie → Prefix-aware lookup

Graphs

Shankar L — Tue, 08 Sep 2026 10:48:00 +0000

Why should you care?

Many real-world problems are not naturally represented as a simple sequence or hierarchy.

Consider:

Cities connected by roads
People connected through friendships
Computers connected through a network
Web pages connected through hyperlinks
Courses connected through prerequisites
Social networks
Maps and navigation systems

These relationships can be represented using a graph.

Graphs are one of the most important data structures in computer science because they allow us to model relationships between objects.

They are the foundation of algorithms such as:

Breadth-First Search (BFS)
Depth-First Search (DFS)
Dijkstra's algorithm
Bellman-Ford algorithm
Floyd-Warshall algorithm
Prim's algorithm
Kruskal's algorithm
Topological sorting

The Problem

Suppose a college has several campuses:

Chennai
Bangalore
Coimbatore
Madurai
Dindigul

Some campuses are connected by roads:

Chennai ─── Bangalore
   │
   │
Coimbatore ─── Madurai
   │
   │
Dindigul

Now suppose we want to answer questions like:

Is there a path from Chennai to Madurai?
What is the shortest route?
Which cities are connected?
What happens if a road is removed?
What is the cheapest way to connect all cities?

A simple array, linked list, stack, or queue doesn't naturally represent these relationships.

We need a structure that can represent:

Objects and the relationships between them.

That's what graphs provide.

The Concept

A graph is a collection of:

Vertices (nodes) — the objects
Edges — the connections between objects

For example:

       A
      / \
     /   \
    B─────C
     \
      \
       D

Here:

Vertices = A, B, C, D

Edges = A-B
        A-C
        B-C
        B-D

Mathematically, a graph can be represented as:

G = (V, E)

where:

V = set of vertices
E = set of edges

For example:

V = {A, B, C, D}

E = {(A,B), (A,C), (B,C), (B,D)}

The important idea is that edges describe relationships between vertices.

Simple Explanation

Think of a graph as a collection of dots connected by lines.

A ─── B
│     │
│     │
C ─── D

The dots are:

Vertices

The lines are:

Edges

You can represent almost anything as a graph if there are objects and relationships between them.

For example:

People → friendships
Cities → roads
Computers → network connections
Web pages → hyperlinks
Courses → prerequisites

The same mathematical structure can represent all of them.

Real-world Analogy

Think about a social network.

Suppose:

Alice
Bob
Charlie
David

Alice is friends with Bob and Charlie:

Alice ─── Bob
  │
  │
  └──── Charlie

Bob is also friends with David:

Alice ─── Bob ─── David
  │
  │
Charlie

Each person is a vertex.

Each friendship is an edge.

Now you can ask graph-related questions:

"Can Alice reach David through friendships?"

Yes:

Alice → Bob → David

This is the basic idea behind graph traversal.

Code Example

One common way to represent a graph is an adjacency list.

Consider:

A ─── B
│     │
│     │
C ─── D

We can represent it as:

A → B, C
B → A, D
C → A, D
D → B, C

In Java:

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Map<String, List<String>> graph = new HashMap<>();

        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D"));
        graph.put("C", Arrays.asList("A", "D"));
        graph.put("D", Arrays.asList("B", "C"));

        System.out.println(graph.get("A"));
    }
}

Output:

[B, C]

This tells us:

A
├── B
└── C

Traversing the graph

We can use BFS:

Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();

queue.offer("A");
visited.add("A");

while (!queue.isEmpty()) {

    String current = queue.poll();

    System.out.println(current);

    for (String neighbor : graph.get(current)) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.offer(neighbor);
        }
    }
}

The queue manages which vertex should be processed next.

The visited set prevents us from processing the same vertex repeatedly.

Common Mistakes

Mistake 1: Thinking graphs are always directed

Graphs can be directed or undirected.

An undirected graph:

A ─── B

means the relationship works both ways.

For example:

Alice ─── Bob

could represent friendship.

A directed graph:

A → B

means the relationship has a direction.

For example:

Instagram user A → follows → user B

A following B does not necessarily mean B follows A.

Mistake 2: Thinking every graph has weights

Some graphs have weights:

A ──5── B

where 5 could represent:

Distance
Cost
Time
Network latency

But graphs don't necessarily need weights.

An unweighted graph might simply be:

A ─── B

So:

Graph
├── Weighted
└── Unweighted

Mistake 3: Forgetting cycles

Graphs can contain cycles:

A ─── B
│     │
│     │
D ─── C

You can travel:

A → B → C → D → A

If your traversal algorithm doesn't track visited nodes, it can repeatedly follow the cycle.

That's why graph traversal commonly uses a structure such as:

Set<String> visited

to remember which vertices have already been processed.

Advanced Notes

1. Directed vs Undirected Graphs

An undirected graph:

A ─── B

can be represented as:

A → B
B → A

conceptually.

A directed graph:

A → B

only has:

A → B

not necessarily:

B → A

This distinction is extremely important in graph algorithms.

2. Weighted Graphs

A weighted graph associates a value with each edge:

A ──10── B
│        │
5        3
│        │
C ──7─── D

The weight might represent:

Distance
Cost
Time
Capacity
Latency

For example, GPS navigation can model:

City A ── 120 km ── City B

Now the problem becomes:

Find the path with the minimum total weight.

This leads directly to shortest-path algorithms.

3. Adjacency Matrix

Another way to represent a graph is an adjacency matrix.

For:

A ─── B
│
C

we can use:

A 1 means:

An edge exists.

A 0 means:

No edge.

For weighted graphs, the matrix can store weights instead.

The major trade-off is memory.

For V vertices, an adjacency matrix requires approximately:

O(V²)

space.

4. Adjacency List

An adjacency list stores only the connections that actually exist:

A → B, C
B → A
C → A

For a graph with relatively few edges, this can be much more memory-efficient.

Typical space:

O(V + E)

where:

V = vertices
E = edges

So the common comparison is:

Representation	Space
Adjacency Matrix	O(V²)
Adjacency List	O(V + E)

5. BFS

Breadth-First Search explores a graph level by level.

It uses a queue.

Consider:

Starting from A:

Level 0 → A
Level 1 → B, C
Level 2 → D, E

Traversal:

A → B → C → D → E

BFS is particularly useful for finding the shortest path in an unweighted graph.

6. DFS

Depth-First Search explores as far as possible along one path before backtracking.

It can be implemented using:

A stack
Recursion

For example:

DFS might follow:

A → B → D
      ↑
   backtrack
      ↓
      C

DFS is useful for:

Cycle detection
Connected components
Backtracking
Topological sorting
Path exploration

7. Shortest Path

Suppose we have:

A ──5── B
│       │
2       3
│       │
C ──4── D

We want the shortest route from A to D.

Possible paths:

A → B → D
5 + 3 = 8

A → C → D
2 + 4 = 6

Therefore:

Shortest path = A → C → D
Cost = 6

Different graph algorithms solve different shortest-path problems.

For example:

BFS → unweighted graphs
Dijkstra → non-negative edge weights
Bellman-Ford → can handle negative edge weights
Floyd-Warshall → all-pairs shortest paths

8. Topological Sorting

Some graphs represent dependencies.

Suppose:

Learn C
   ↓
Learn Data Structures
   ↓
Learn Algorithms

You must learn C before Data Structures, and Data Structures before Algorithms.

A directed graph can represent this:

C → Data Structures → Algorithms

A topological ordering produces an order that respects these dependencies:

C
↓
Data Structures
↓
Algorithms

This is useful for:

Course prerequisites
Build systems
Package dependencies
Task scheduling

A topological ordering is defined for a directed acyclic graph (DAG).

The Bigger Picture

Graphs bring together many of the data structures you've learned so far.

You can think of the progression as:

Arrays
   ↓
Linked Lists
   ↓
Stacks / Queues
   ↓
Trees
   ↓
Heaps
   ↓
Graphs

But graphs are more general than trees.

A tree can be viewed as a special kind of graph with particular properties.

For example:

Tree:

       A
      / \
     B   C
    /
   D

has:

No cycles
A connected structure
A hierarchical relationship

A general graph can be much more flexible:

A ─── B
│   / │
│  /  │
C ─── D

It can contain cycles, multiple paths, and arbitrary connections.

Graphs also bring together the structures you've already learned:

Graph Algorithms
      ↓
 ┌────┴────┐
 ↓         ↓
Queue     Stack
 ↓         ↓
 BFS       DFS

And heaps become important when graph algorithms need to repeatedly select the next lowest-cost vertex:

Graph
  ↓
Dijkstra
  ↓
Priority Queue
  ↓
Heap

This is why learning data structures sequentially is useful: each concept becomes a building block for the next.

The Most Important Mental Model

A graph is a collection of things and the relationships between them.

Think:

Objects          Relationships

  A ───────────── B
   \              /
    \            /
     \          /
       C ───── D

The objects are vertices.

The relationships are edges.

Everything else builds on top of this:

Graph
├── Directed / Undirected
├── Weighted / Unweighted
├── Cyclic / Acyclic
├── Connected / Disconnected
├── Adjacency List / Matrix
└── Traversal / Path Algorithms

When you encounter a graph problem, the first question should often be:

What are my objects, and what relationship connects them?

Once you've identified those two things, the graph becomes much easier to model.

Summary

A graph is a non-linear data structure used to represent relationships between objects.

The key ideas are:

Vertices represent objects.
Edges represent relationships.
Graphs can be directed or undirected.
Graphs can be weighted or unweighted.
Graphs can contain cycles.
Adjacency lists use O(V + E) space.
Adjacency matrices use O(V²) space.
BFS uses a queue and explores level by level.
DFS uses a stack or recursion and explores deeply.
Weighted graphs can represent distance, cost, time, or other quantities.
Graphs are used in networks, maps, social platforms, dependency systems, and recommendation systems.
Important graph algorithms include BFS, DFS, Dijkstra, Bellman-Ford, Prim, Kruskal, and topological sorting.