Array Manipulation

At a glance

The instinct

Array manipulation is not one algorithm but a family of moves you make on the array itself. The interviewer has usually banned the easy way out ("do it in place", "no extra array", "without division") or wants a single pass. When the obvious solution is "copy into a new array" or "for each element, scan everything else", ask yourself: can I carry a tiny bit of state while I walk once, or reuse the array as my scratch pad?

Almost every problem in this family reduces to four moves: a write pointer that compacts kept elements, a reversal that rearranges blocks, a left pass + right pass that gathers information from both sides, and index marking that stores facts in the array's own slots.

Recognise it

Not this pattern if...

• The question asks about a contiguous window that must satisfy a constraint (length, distinct count): that is Sliding Window.
• The array is sorted and you need a pair or triple with a target sum: that is Two Pointers from opposite ends.
• You need many range sum queries: that is Prefix Sum.
• The best contiguous sum or product is the goal: that is Kadane's Running Best.

Memory hack

Say it out loud in the interview:

1. "Can I solve this in one pass with a reader and a writer, or a running best variable?"
2. "If I need information from both sides of an index, I'll do a left pass and then a right pass."
3. "If values fit in 1..n, I'll use the array's own indices to mark what I've seen."

How it works

The write-pointer move is the backbone. The reader r visits every element; the writer w marks the next free slot for an element we decide to keep. Everything left of w is the finished answer, so the invariant is easy to state and easy to defend.

Trace for Move Zeroes on [0, 1, 0, 3, 12]:

Rotation uses the fact that reversing twice restores order. To rotate right by k: reverse everything, then reverse the first k items, then reverse the rest. In Rotate Array, [1..7] with k = 3 becomes [7..1], then [5,6,7 | 4,3,2,1], then [5,6,7,1,2,3,4].

Two-sided passes solve Product of Array Except Self: the first pass writes the product of everything to the left of each index, the second pass multiplies in a running product of everything to the right. No division, so zeros are harmless.

Index marking solves First Missing Positive: swap each value v in 1..n into slot v-1 (cyclic placement). Afterwards the first slot i where nums[i] != i + 1 reveals the answer.

Java template

import java.util.Arrays;

class ArrayToolkit {
    // 1) Read fast, write slow: keep elements that pass a test, preserve order.
    static int compact(int[] nums) {
        int w = 0;
        for (int r = 0; r < nums.length; r++) {
            if (keep(nums, r, w)) {          // problem-specific test
                nums[w++] = nums[r];
            }
        }
        Arrays.fill(nums, w, nums.length, 0); // optional: tidy the tail
        return w;                             // new logical length
    }

    static boolean keep(int[] nums, int r, int w) {
        return nums[r] != 0;                  // e.g. "not zero", or nums[r] != nums[w - 1] for dedupe
    }

    // 2) Rotate right by k with three reversals.
    static void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    static void reverse(int[] a, int i, int j) {
        while (i < j) {
            int t = a[i]; a[i++] = a[j]; a[j--] = t;
        }
    }

    // 3) Left pass + right pass: combine info from both sides of each index.
    static int[] exceptSelf(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        int left = 1;
        for (int i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
        return out;
    }

    // 4) Index as hash: place value v (1..n) at slot v-1.
    static void cyclicPlace(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int j = nums[i] - 1;
                int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
            }
        }
    }
}

Complexity

Variations

• Filter / compact: keep elements passing a test, order preserved. Move Zeroes, Remove Duplicates from Sorted Array.
• Running extreme: track the min-so-far or max-so-far while scanning. Best Time to Buy and Sell Stock; Increasing Triplet Subsequence keeps the two smallest "tails".
• Greedy accumulation: add every positive day-to-day gain. Best Time to Buy and Sell Stock II.
• Block rearrangement: reversals or cyclic replacements. Rotate Array.
• Two-sided precomputation: prefix and suffix products or maxima. Product of Array Except Self.
• Index marking: cyclic sort or sign flipping for values in 1..n. First Missing Positive.
• Voting / counting runs: a candidate plus a counter, or a running streak length. Majority Element (Boyer-Moore), Number of Zero-Filled Subarrays.

Common mistakes

• Forgetting k %= n before rotating, which breaks when k is larger than the array length.
• Returning the array instead of the new length (or vice versa) in compaction problems; read the required return contract carefully.
• Allocating a copy "just to be safe" when the problem demands O(1) space, then being asked to redo it.
• In cyclic placement, using if instead of while, so a value swapped into slot i is never itself placed.
• Integer overflow on products or running sums; switch to long when the constraints allow large values.

All practice problems

10 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.