Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

DSA PATTERN

Array Traversal

Read each value once while carrying only the state needed for the answer.

Recognition signals
every element matters · one pass is possible · the answer can be updated while scanning
Core invariant
After index i, the stored state correctly describes the processed prefix from 0 through i.
Typical cost
Usually O(n) time; Usually O(1) auxiliary space
Common mistakes
Starting from an unsafe default value · Skipping the first or last index · Forgetting empty-input behavior
Java
for (int index = 0; index < values.length; index++) {
    int value = values[index];
    // Update the answer using value.
}

Available on the Atlas

DSA PATTERN

Running Answer

Maintain the best answer seen so far instead of storing or sorting everything.

Recognition signals
largest or smallest seen so far · one result from an unsorted input · sorting feels unnecessary
Core invariant
The running variables contain the best valid answer for the prefix already processed.
Typical cost
Usually O(n) time; Usually O(1) auxiliary space
Common mistakes
Using zero as the initial answer · Updating dependent answers in the wrong order · Ignoring duplicate rules
Java
int best = values[0];
for (int index = 1; index < values.length; index++) {
    best = Math.max(best, values[index]);
}

Available on the Atlas

DSA PATTERN

Two Pointers

Coordinate two positions so each movement removes work that never needs to be repeated.

Recognition signals
sorted input with a safe elimination rule · preserve order in place · compare from two positions · merge two sequences · find a linked-list middle or cycle
Core invariant
Define what each pointer means and which positions are settled or candidates can safely be discarded; the exact promise depends on the problem.
Typical cost
Often O(n) or O(n + m) time; Often O(1), excluding output auxiliary space
Common mistakes
Moving without a safe elimination rule · Using sorted pair-sum moves on unsorted input · Losing stable order · Not advancing on equal values
Java
int left = 0;
int right = values.length - 1;
while (left < right) {
    // Inspect both boundaries and move at least one pointer.
}

Available on the Atlas

DSA PATTERN

In-place Compaction

Use separate read and write positions to keep valid values at the front of the same array.

Recognition signals
modify the same array · preserve relative order · return the new valid length
Core invariant
Positions before write contain exactly the valid values encountered so far, in original order.
Typical cost
O(n) time; O(1) auxiliary space
Common mistakes
Advancing write for rejected values · Reading overwritten data · Returning the last index instead of the length
Java
int write = 0;
for (int read = 0; read < values.length; read++) {
    if (shouldKeep(values[read])) {
        values[write++] = values[read];
    }
}

Available on the Atlas

DSA PATTERN

Reversal

Reverse carefully chosen ranges to move array blocks without extra array storage.

Recognition signals
rotate in place · move a prefix behind a suffix · reverse words or ranges
Core invariant
Each completed reversal places one required block orientation into the transformation sequence.
Typical cost
O(n) time; O(1) auxiliary space
Common mistakes
Not normalizing k · Using the wrong inclusive boundaries · Forgetting the empty array
Java
while (left < right) {
    int temporary = values[left];
    values[left++] = values[right];
    values[right--] = temporary;
}

Available on the Atlas

DSA PATTERN

Hashing

Trade extra memory for fast lookup of information seen earlier.

Recognition signals
have we seen this before · count occurrences · find a matching earlier state
Core invariant
The map contains exactly the historical facts needed to answer the current step.
Typical cost
Usually O(n) expected time; Usually O(n) auxiliary space
Common mistakes
Overwriting the earliest index · Assuming worst-case O(1) lookup · Using a map when a small fixed array is clearer
Java
Map<Integer, Integer> firstIndex = new HashMap<>();
for (int index = 0; index < values.length; index++) {
    firstIndex.putIfAbsent(values[index], index);
}

Available on the Atlas

DSA PATTERN

Prefix Sum

Represent a range by subtracting two cumulative totals.

Recognition signals
contiguous subarray · range sum · sum ending at this index
Core invariant
prefix is the exact sum from index 0 through the current index.
Typical cost
O(n) preprocessing or scan; O(1) to O(n), depending on stored history auxiliary space
Common mistakes
Missing the empty prefix at index -1 · Using int when sums may overflow · Applying a positive-only window to negative values
Java
long prefix = 0;
for (int value : values) {
    prefix += value;
    // Compare or store this prefix state.
}

Available on the Atlas

DSA PATTERN

XOR Cancellation

Cancel paired values so the unpaired value remains.

Recognition signals
every value appears twice except one · numbers come from a known range · constant extra space
Core invariant
All matched values cancel regardless of processing order, while the unmatched value remains.
Typical cost
O(n) time; O(1) auxiliary space
Common mistakes
Using XOR without the required pairing guarantee · Forgetting expected range values · Treating XOR as addition
Java
int answer = 0;
for (int value : values) {
    answer ^= value;
}

Available on the Atlas

DSA PATTERN

Recursion

Solve a problem by defining a smaller version of the same problem and a stopping condition.

Recognition signals
same task on smaller input · tree or directory structure · choose and continue
Core invariant
Each call owns one well-defined subproblem and moves closer to the base case.
Typical cost
Depends on branches and depth; At least O(depth) call stack auxiliary space
Common mistakes
Missing a base case · Not reducing the problem · Ignoring call-stack space
Java
static void solve(int index) {
    if (index == limit) return;
    solve(index + 1);
}

Available on the Atlas

DSA PATTERN

Backtracking

Explore a choice, undo it, then explore the next choice from the same clean state.

Recognition signals
all combinations · choose or skip · return every valid arrangement
Core invariant
The current path represents exactly the decisions made before the current depth.
Typical cost
Often exponential because the output is exponential; O(depth), excluding output auxiliary space
Common mistakes
Forgetting to undo a choice · Adding the mutable path without copying it · Claiming output space as constant
Java
path.add(value);
search(nextIndex, path, answer);
path.remove(path.size() - 1);
search(nextIndex, path, answer);

Available on the Atlas