The Patterns That Betray You: Two Pointers, Hashing, and Linked Lists

By FreePare Team · Wed Aug 12 2026 · 9 min read

Lab 2 of the 75-problem placement system

This is the second of four labs. It assumes the foundations built in Lab 1 — arrays, hashing and honest cost analysis — and is followed by Lab 3 on stacks, queues, backtracking and trees, and Lab 4 on binary-search-tree invariants, heaps and graphs.

Patterns are compression tools. "Sliding window" compresses a proof about a contiguous range. "Two pointers" compresses a proof about monotonic movement. "Fast and slow" compresses a proof about relative speed through a linked structure.

The danger begins when the name replaces the proof. This lab makes you state the conditions that allow each pattern and supplies counterexamples when those conditions disappear.

Entry check

Answer before coding:

1. Why does pair-sum two-pointer search usually require sorted data?

2. What exactly does a fixed window preserve after each slide?

3. Why can shrinking a variable window be unsound when negative values are allowed?

4. When is sorting preferable to a hash set for deduplication?

5. Which invariant makes a dummy head useful?

6. Why does Floyd cycle detection find a meeting point, and how do you recover the cycle entry?

If you cannot answer four, complete the worked traces. If you answer all six, attempt the exit lab first.

Java 25 is the primary language. Java documents expected basic-operation costs and key contracts for HashMap and HashSet. Those expected costs depend on suitable hash dispersion; they are not unconditional worst-case guarantees.

Use the NIST Dictionary of Algorithms and Data Structures as a terminology anchor when a platform label and an algorithmic definition differ.

1. Two pointers: movement needs a reason

Opposite ends on sorted data

static int[] pairWithSum(int[] sorted, int target) {
    int left = 0;
    int right = sorted.length - 1;

    while (left < right) {
        long sum = (long) sorted[left] + sorted[right];
        if (sum == target) {
            return new int[]{left, right};
        }
        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[0];
}

Invariant: no discarded pair can equal the target. If the current sum is too small, pairing sorted[left] with any smaller right-side value cannot help, so advancing left is safe. That argument collapses on unsorted input.

Counterexample: [3, 1, 4, 2], target 6. Pointer movement based on endpoint values cannot discard a whole region because values inside are not ordered.

If original indices matter, preserve (value, originalIndex) pairs before sorting or use a map. "Sort first" is a design decision, not a free step.

Fixed sliding window

Find the maximum sum of exactly k consecutive values:

static long maximumWindowSum(int[] values, int k) {
    if (k <= 0 || k > values.length) {
        throw new IllegalArgumentException("invalid window size");
    }

    long window = 0;
    for (int i = 0; i < k; i++) {
        window += values[i];
    }

    long best = window;
    for (int right = k; right < values.length; right++) {
        window += values[right];
        window -= values[right - k];
        best = Math.max(best, window);
    }
    return best;
}

Invariant: after each update, window equals the sum of the last k processed elements. Every element enters once and leaves once, giving Theta(n) time and Theta(1) auxiliary space.

Variable window with a monotonic condition

For positive integers, find the shortest subarray whose sum is at least target:

static int shortestPositiveWindow(int[] positive, long target) {
    int left = 0;
    int best = Integer.MAX_VALUE;
    long sum = 0;

    for (int right = 0; right < positive.length; right++) {
        if (positive[right] <= 0) {
            throw new IllegalArgumentException("values must be positive");
        }
        sum += positive[right];

        while (sum >= target) {
            best = Math.min(best, right - left + 1);
            sum -= positive[left++];
        }
    }
    return best == Integer.MAX_VALUE ? -1 : best;
}

Positivity creates monotonic behavior: expanding never lowers the sum; shrinking never raises it. With negatives, both statements fail. For [2, -1, 2], local shrink/expand decisions based only on current sum can discard a prefix that becomes useful later. Depending on the problem, use prefix sums with a map, binary search, or a monotonic deque.

Pattern gate:

• contiguous range required? A window may fit.
• endpoint decision justified by sorted/monotonic data? Two pointers may fit.
• each pointer moves only forward? Linear analysis may fit.
• negative values or non-monotonic state? Demand a counterexample before proceeding.

2. Hash maps and sets: expected speed has a price

Membership and frequency are different workloads

Use a set when only existence matters:

static boolean intersects(int[] first, int[] second) {
    java.util.Set<Integer> seen = new java.util.HashSet<>();
    for (int value : first) {
        seen.add(value);
    }
    for (int value : second) {
        if (seen.contains(value)) {
            return true;
        }
    }
    return false;
}

Use a map when multiplicity matters:

static java.util.Map<Integer, Integer> frequency(int[] values) {
    java.util.Map<Integer, Integer> count = new java.util.HashMap<>();
    for (int value : values) {
        count.merge(value, 1, Integer::sum);
    }
    return count;
}

For n inserted keys, both use Theta(n) extra entries. If memory is tight and reordering is allowed, sorting followed by a linear scan can use less auxiliary memory. It costs O(n log n) comparison time but gives deterministic ordering and avoids hash-quality assumptions.

Deduplication must define order

"Remove duplicates" is incomplete. Which occurrence survives, and must encounter order remain?

static int[] distinctInEncounterOrder(int[] values) {
    java.util.Set<Integer> seen = new java.util.LinkedHashSet<>();
    for (int value : values) {
        seen.add(value);
    }
    return seen.stream().mapToInt(Integer::intValue).toArray();
}

A plain hash set does not promise encounter-order iteration. An ordered set or explicit result list does.

Collision counterexample

Two unequal keys may share a hash code. Correctness survives because the table still compares keys; performance can degrade as more work collects in the same bucket. Never replace equality with hash-code equality.

Mutable equality-relevant fields are worse: changing a key after insertion can make lookup search a different bucket. Prefer immutable keys.

3. Linked lists: code the relationships

final class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

A singly linked list supports constant-time insertion after a known node, but finding the node is linear. It has no constant-time random index access. State whether a method may mutate links and whether external references to nodes can observe that mutation.

Dummy heads remove a branch

Delete every node equal to target:

static Node removeAll(Node head, int target) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node current = dummy;

    while (current.next != null) {
        if (current.next.value == target) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return dummy.next;
}

Invariant: every node before current.next has already been processed, and dummy.next is always the current result head. Deleting the original head needs no special branch.

Reversal preserves an unprocessed suffix

static Node reverse(Node head) {
    Node previous = null;
    Node current = head;

    while (current != null) {
        Node next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

Invariant: previous is the reversed processed prefix; current starts the untouched suffix. Saving next before rewiring prevents the suffix from being lost.

Cycle detection and entry

static Node cycleEntry(Node head) {
    Node slow = head;
    Node fast = head;

    do {
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
    } while (slow != fast);

    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

The first meeting proves a cycle exists; it is not generally the entry. Resetting one pointer to the head and moving both one step at a time brings them to the entry because the traveled distances differ by a whole number of cycle lengths.

Trace it once

That last sentence is the least convincing one in this lab while it is only asserted, so run it on a list small enough to see. Six nodes hold the values 1 to 6, and node 6 points back to node 3: a two-node prefix and a four-node cycle.

1 -> 2 -> 3 -> 4 -> 5 -> 6
          ^              |
          +--------------+

Phase one moves slow one node and fast two:

They meet at node 5. Node 5 is inside the cycle and is not its entry, which is exactly what the name "cycle detection" hides — the meeting proves the cycle exists and says nothing about where it starts. Phase two puts slow back at the head and moves both pointers one node at a time:

They meet at node 3, which is the entry. It works because fast had covered exactly twice slow's distance at the moment they met, so the difference between them was a whole number of laps; walking the prefix length from the head and from the meeting point therefore arrives at the same node. Before trusting this on an input you cannot see, trace it again on the two lists that break careless versions: one where the entry is the head, and one single node pointing at itself.

Test: empty list, one node without cycle, one node pointing to itself, two nodes, cycle at head, cycle after a non-cycle prefix, and duplicate values. Compare node identity, not value equality.

Problem batch: S01-S13

Exit lab

Complete in 70 minutes:

1. a pair or window problem with a written monotonicity proof;

2. a membership/frequency problem with a set-versus-sort trade-off;

3. a linked-list mutation with empty, singleton, head, tail, and cycle-related tests.

Each task is worth 10: selection (2), invariant/proof (2), code (2), edge tests (2), complexity and assumptions (2). Pass at 24/30, with no task below 7. A hint-assisted pass schedules retries after 2 and 7 days; only the unaided retry counts as clean.

Next in this series: Stacks, Queues, Deques, Backtracking & Trees, which takes the same demand for a stated invariant into structures that decide what becomes available next.

Tags: coding-practice, coding-fundamentals, computer-science-fundamentals, programming-fundamentals, study-tips-for-students, career-growth-skills, freepare-blogs, effective-study-techniques