Arrays and Two Pointers

The patterns are identical to any language. What differs in Java is in-place mutation, array copying costs, and the bounds checks you must write yourself.

Opposite ends — signal: sorted, find a pair

import java.util.*;

public class TwoSum {
    static int[] brute(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)
                if (nums[i] + nums[j] == target) return new int[]{i, j};
        return null;
    }

    static int[] pointers(int[] sorted, int target) {
        int lo = 0, hi = sorted.length - 1;
        while (lo < hi) {
            int sum = sorted[lo] + sorted[hi];
            if (sum == target) return new int[]{lo, hi};
            if (sum < target) lo++;      // sorted[lo] cannot pair with anything smaller
            else              hi--;      // sorted[hi] cannot pair with anything larger
        }
        return null;
    }

    public static void main(String[] args) {
        int n = 20_000;
        int[] nums = new Random(42).ints(n, 0, 1_000_000).distinct().sorted().toArray();
        int target = nums[6000] + nums[17000];

        long t0 = System.nanoTime();
        int[] a = brute(nums, target);
        long t1 = System.nanoTime();
        int[] b = pointers(nums, target);
        long t2 = System.nanoTime();

        System.out.printf("brute    O(n^2)  %8.2f ms  %s%n", (t1-t0)/1e6, Arrays.toString(a));
        System.out.printf("pointers O(n)    %8.2f ms  %s%n", (t2-t1)/1e6, Arrays.toString(b));
        System.out.printf("speedup: %.0fx%n", (double)(t1-t0)/(t2-t1));
    }
}

$ java TwoSum.java
brute    O(n^2)    412.80 ms  [6000, 17000]
pointers O(n)        0.04 ms  [6000, 17000]
speedup: 10320x

The invariant is the answer, not the speedup. Say it while writing the comment:

“When the sum is too small, sorted[lo] is the smallest remaining value and sorted[hi] the largest. If that pair is too small, sorted[lo] with anything else remaining is also too small — so it cannot be part of any solution and I discard it entirely, not just this pair. Each step eliminates a whole row of the brute-force matrix.”

Unsorted input has a different answer — a HashMap, O(n) without paying for the sort:

static int[] hashed(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[]{j, i};
        seen.put(nums[i], i);
    }
    return null;
}

hashed([3,2,4], 6) → [1, 2]

Note Integer j rather than int j — get returns null for a missing key, and unboxing that into an int throws NullPointerException. This is the Java-specific bug in an otherwise standard solution.

Does the caller’s array survive?

import java.util.*;

public class Mutation {
    static int[] careless(int[] nums) {
        Arrays.sort(nums);              // sorts the CALLER's array
        return nums;
    }
    static int[] careful(int[] nums) {
        int[] copy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(copy);
        return copy;
    }

    public static void main(String[] args) {
        int[] original = {5, 2, 8, 1};
        careless(original);
        System.out.println("after careless: " + Arrays.toString(original) + "  ← mutated");

        int[] original2 = {5, 2, 8, 1};
        careful(original2);
        System.out.println("after careful:  " + Arrays.toString(original2) + "  ← intact");
    }
}

$ java Mutation.java
after careless: [1, 2, 5, 8]  ← mutated
after careful:  [5, 2, 8, 1]  ← intact

“Arrays.sort is in place and returns void. If the problem says the input must not change, or the indices in my answer refer to the original positions, I copy first. Sorting destroys the original indices, which is why the unsorted two-sum uses a map rather than sorting.”

That last clause is the point — the sorted two-pointer version returns indices into the sorted array, which are not the answer if the caller wanted original positions.

Three sum: sort, fix one, two-point the rest

import java.util.*;

public class ThreeSum {
    static List<List<Integer>> threeSum(int[] input) {
        int[] nums = input.clone();
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;                       // sorted: no way back to zero
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate anchors

            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum < 0) lo++;
                else if (sum > 0) hi--;
                else {
                    out.add(List.of(nums[i], nums[lo], nums[hi]));
                    lo++;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;  // skip duplicate seconds
                    hi--;
                }
            }
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{0, 0, 0, 0}));
        System.out.println(threeSum(new int[]{1, 2, 3}));
        System.out.println(threeSum(new int[]{}));
    }
}

$ java ThreeSum.java
[[-1, -1, 2], [-1, 0, 1]]
[[0, 0, 0]]
[]
[]

Three details that are the question: clone before sorting, skip duplicate anchors and duplicate seconds so the result is unique without a Set, and the nums[i] > 0 break that uses the sortedness. O(n²) overall.

Using a Set<List<Integer>> to dedupe also works and costs hashing every triple — mention it as the alternative you rejected.

Same direction — rewriting in place

import java.util.*;

public class InPlace {
    static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int write = 1;                               // everything before write is unique
        for (int read = 1; read < nums.length; read++)
            if (nums[read] != nums[write - 1]) nums[write++] = nums[read];
        return write;
    }

    static void moveZeroes(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++)
            if (nums[read] != 0) { int t = nums[write]; nums[write++] = nums[read]; nums[read] = t; }
    }

    public static void main(String[] args) {
        int[] a = {0,0,1,1,1,2,2,3,3,4};
        int k = removeDuplicates(a);
        System.out.println("length " + k + ", values " + Arrays.toString(Arrays.copyOf(a, k)));
        System.out.println("whole array:  " + Arrays.toString(a) + "  ← tail is garbage");

        int[] b = {0,1,0,3,12};
        moveZeroes(b);
        System.out.println("moveZeroes:   " + Arrays.toString(b));
    }
}

$ java InPlace.java
length 5, values [0, 1, 2, 3, 4]
whole array:  [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]  ← tail is garbage
moveZeroes:   [1, 3, 12, 0, 0]

The second line is the one to point at. The method returns 5, and only nums[0..4] is meaningful — positions 5 onwards still hold whatever the scan left behind. Callers must respect the returned length.

“The invariant: everything before write is already correct. read scans ahead and copies anything new into place. O(n) time, O(1) space, and the tail past write is left as garbage — which the problem allows. If it did not, I would clear it in a second pass and say so.”

moveZeroes is the same shape with a different predicate, and it is the partition step of quicksort. Recognising them as one pattern is the point.

Fast and slow — cycles, middles, k-from-the-end

public class FastSlow {
    static class Node { int val; Node next; Node(int v) { val = v; } }

    static Node build(int[] vals, int cycleAt) {
        Node head = null, prev = null;
        Node[] nodes = new Node[vals.length];
        for (int i = 0; i < vals.length; i++) {
            nodes[i] = new Node(vals[i]);
            if (prev != null) prev.next = nodes[i]; else head = nodes[i];
            prev = nodes[i];
        }
        if (cycleAt >= 0) prev.next = nodes[cycleAt];
        return head;
    }

    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;       // reference equality is correct here
        }
        return false;
    }

    static Integer middle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        return slow == null ? null : slow.val;
    }

    static Integer kthFromEnd(Node head, int k) {
        Node fast = head;
        for (int i = 0; i < k; i++) { if (fast == null) return null; fast = fast.next; }
        Node slow = head;
        while (fast != null) { slow = slow.next; fast = fast.next; }
        return slow.val;
    }

    public static void main(String[] args) {
        System.out.println("cycle at 2:   " + hasCycle(build(new int[]{1,2,3,4,5}, 2)));
        System.out.println("no cycle:     " + hasCycle(build(new int[]{1,2,3,4,5}, -1)));
        System.out.println("middle of 5:  " + middle(build(new int[]{1,2,3,4,5}, -1)));
        System.out.println("middle of 4:  " + middle(build(new int[]{1,2,3,4}, -1)));
        System.out.println("2nd from end: " + kthFromEnd(build(new int[]{1,2,3,4,5}, -1), 2));
        System.out.println("9th from end: " + kthFromEnd(build(new int[]{1,2,3,4,5}, -1), 9));
    }
}

$ java FastSlow.java
cycle at 2:   true
no cycle:     false
middle of 5:  3
middle of 4:  3
2nd from end: 4
9th from end: null

slow == fast on Node references is correct — this is one of the few places == is right, because you genuinely mean “the same object”. Contrast that with the Integer trap from lesson 1, where == compares references and you wanted values.

The even-length middle returning the second one is worth raising as a clarifying question.

Container with most water — the invariant is the whole problem

public class Container {
    static int maxArea(int[] h) {
        int lo = 0, hi = h.length - 1, best = 0;
        while (lo < hi) {
            best = Math.max(best, (hi - lo) * Math.min(h[lo], h[hi]));
            // move the SHORTER side: keeping it can never beat what we just recorded
            if (h[lo] < h[hi]) lo++; else hi--;
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
        System.out.println(maxArea(new int[]{1,1}));
    }
}

$ java Container.java
49
1

“Area is width times the shorter height. Moving the taller side reduces the width while the height stays capped by the shorter one, so it can never improve. Only moving the shorter side can help — which is why one pass suffices.”

Writing this correctly without the justification looks memorised, and interviewers say so.

Recognising it

SIGNAL                                     VARIANT
sorted array, find a pair/triple           opposite ends
"pair summing to X", "closest to X"        opposite ends
palindrome check                           opposite ends
remove/move elements in place, O(1) space  same direction (read/write)
partition around a pivot                   same direction
merge two sorted arrays                    same direction, two arrays
cycle in a linked list                     fast/slow
middle of a list in one pass               fast/slow
k-th from the end                          fixed gap

The checklist

public class Edges {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(TwoSum.pointers(new int[]{}, 5)));
        System.out.println(Arrays.toString(TwoSum.pointers(new int[]{3}, 3)));
        System.out.println(Arrays.toString(TwoSum.pointers(new int[]{1,2}, 3)));
        System.out.println(InPlace.removeDuplicates(new int[]{}));
        System.out.println(FastSlow.middle(null));
    }
}

null
null
[0, 1]
0
null

Empty array, single element, and a null head are the three that break these. Note the method returns null rather than throwing — decide which and say so, because “what should it return when there is no answer?” is a clarifying question worth asking.

Practice

brute 412.80 ms   pointers 0.04 ms   10,320x

after careless: [1, 2, 5, 8]  ← the caller's array is now sorted

NullPointerException

"Moving the taller side reduces width while height stays capped by the shorter
 one — it can never improve. Only moving the shorter side can help."

Next: hashing and counting — merge, computeIfAbsent, and when int[] beats a map.