Arrays and Array-Based Problem Solving

Imagine one row of seats in a cinema. Every seat has a number, seat 0, seat 1, seat 2, and so on, and they sit side by side. If someone says "seat 7", you walk straight there. You do not check seats 0 to 6 first.

That is an array. It is the simplest data structure there is, and it sits underneath most of the others. Lists, strings, heaps and hash tables are all built on arrays in some way. If you become good at arrays, you become good at about a third of all coding problems.

• How an array is laid out in memory and why indexing is so fast.
• The cost of traversal, search, insertion and deletion.
• Frequency counting with a small array.
• In-place techniques: rotation and moving zeroes.
• What a subarray is, and how to find the maximum subarray sum in one pass.
• Java-specific array behaviour that causes bugs.

When you write int[] marks = new int[5], Java asks for one contiguous block of memory big enough for five ints. Each int takes 4 bytes, so the block is 20 bytes, and the elements sit one after the other.

index:     0     1     2     3     4        +-----+-----+-----+-----+-----+marks:  |  40 |  85 |  72 |  91 |  60 |        +-----+-----+-----+-----+-----+address: A    A+4   A+8   A+12  A+16

Because every element has the same size, the computer finds element i with simple arithmetic: start address + i × element size. That takes the same time whether i is 2 or 2 million. So reading or writing by index is O(1).

The price of this layout:

• The size is fixed. You cannot add a sixth element to this block, because the memory next to it may belong to something else.
• Inserting or deleting in the middle needs shifting. To keep elements contiguous, everything after the change must move.
• Searching for a value is a walk. Unless the array is sorted, you have to check one element after another.

Almost every array solution starts with one of these loops.

for (int i = 0; i < a.length; i++) { ... }          // forward, with the indexfor (int i = a.length - 1; i >= 0; i--) { ... }     // backwardfor (int value : a) { ... }                         // forward, values onlyfor (int i = 0; i + 1 < a.length; i++) { ... }      // pairs of neighbours a[i], a[i+1]

The fourth one deserves a comment: when you read a[i + 1], the loop must stop one step early, or you will read past the end. Look at the loop bound before you write the body.

A plain Java array cannot grow, so to insert or delete we keep a separate variable size that tracks how many slots are actually in use. The rest of the array is spare room.

Insert value at index: shift everything from index onwards one slot to the right, working from the right end so you do not overwrite elements you still need. Then write the new value.

Delete the element at index: shift everything after it one slot to the left, then reduce size.

// File: Main.javaimport java.util.Arrays;public class Main {    // Inserts value at index, shifting later elements right. Returns the new size.    static int insertAt(int[] a, int size, int index, int value) {        if (size == a.length) {            throw new IllegalStateException("array is full");        }        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("index " + index + " with size " + size);        }        for (int i = size; i > index; i--) {   // right to left, so nothing is overwritten early            a[i] = a[i - 1];        }        a[index] = value;        return size + 1;    }    // Deletes the element at index, shifting later elements left. Returns the new size.    static int deleteAt(int[] a, int size, int index) {        if (index < 0 || index >= size) {            throw new IndexOutOfBoundsException("index " + index + " with size " + size);        }        for (int i = index; i < size - 1; i++) {            a[i] = a[i + 1];        }        a[size - 1] = 0;                        // tidy up the slot that is no longer used        return size - 1;    }    public static void main(String[] args) {        int[] a = new int[6];        a[0] = 10;        a[1] = 20;        a[2] = 30;        a[3] = 40;        int size = 4;        System.out.println(Arrays.toString(a) + " size=" + size);        size = insertAt(a, size, 1, 15);        System.out.println(Arrays.toString(a) + " size=" + size);        size = deleteAt(a, size, 3);        System.out.println(Arrays.toString(a) + " size=" + size);        size = insertAt(a, size, size, 99);     // inserting at index == size means "append"        System.out.println(Arrays.toString(a) + " size=" + size);        size = insertAt(a, size, 0, 1);         // now the array is full        System.out.println(Arrays.toString(a) + " size=" + size);        try {            insertAt(a, size, 0, 2);        } catch (IllegalStateException e) {            System.out.println("error: " + e.getMessage());        }    }}

[10, 20, 30, 40, 0, 0] size=4[10, 15, 20, 30, 40, 0] size=5[10, 15, 20, 40, 0, 0] size=4[10, 15, 20, 40, 99, 0] size=5[1, 10, 15, 20, 40, 99] size=6error: array is full

Here is the insertion of 15 at index 1, step by step. The array has size = 4: [10, 20, 30, 40, _, _].

The loop runs size - index times, so inserting at the front costs size shifts and inserting at the end costs none. In the worst case it is O(n).

To find the largest value, keep the best so far. The question is what the best-so-far should be before you have looked at anything.

If you start it at 0, an array of negative numbers gives a wrong answer. If you start it at Integer.MIN_VALUE, it works for non-empty arrays, but it is easy to get wrong in related problems. The cleanest habit is to start with the first element and loop from the second:

int best = a[0];for (int i = 1; i < a.length; i++) {    if (a[i] > best) {        best = a[i];    }}

If you also need the position, store the index, not the value:

int bestIndex = 0;for (int i = 1; i < a.length; i++) {    if (a[i] > a[bestIndex]) {        bestIndex = i;    }}

This is O(n) time and O(1) space. Notice that the code assumes a.length >= 1. Decide, and document, what happens for an empty array.

A common task is "how many times does each value occur?" When the possible values are few, such as letters a to z or digits 0 to 9, you can keep one counter per value in an array. The value itself becomes the index.

// File: Main.javapublic class Main {    // counts[0] is the number of 'a's, counts[1] the number of 'b's, and so on.    static int[] countLetters(String text) {        int[] counts = new int[26];        for (char c : text.toCharArray()) {            if (c >= 'a' && c <= 'z') {                counts[c - 'a']++;          // 'c' - 'a' is 2, so letter c uses slot 2            }        }        return counts;    }    public static void main(String[] args) {        int[] counts = countLetters("banana bread");        StringBuilder line = new StringBuilder();        int bestLetter = 0;        for (int i = 0; i < 26; i++) {            if (counts[i] > 0) {                line.append((char) ('a' + i)).append('=').append(counts[i]).append(' ');            }            if (counts[i] > counts[bestLetter]) {                bestLetter = i;            }        }        System.out.println(line.toString().trim());        System.out.println("most frequent: " + (char) ('a' + bestLetter));    }}

a=4 b=2 d=1 e=1 n=2 r=1most frequent: a

The trick is c - 'a', which turns a lowercase letter into a number from 0 to 25. This runs in O(n) time for a text of length n, and O(1) space, since the counter array always has 26 slots whatever the text length. It also skips characters that are not lowercase letters. For other alphabets, upper and lower case together, or arbitrary values, you would use a larger array (such as 128 or 256 for basic characters) or a HashMap, which we cover in Hashing.

An in-place algorithm changes the array it was given and uses only O(1) extra memory. Interviewers love these because they test whether you can manage indexes carefully. Reversing an array, which you saw in the Java article, is the simplest. Here are two more.

Problem. Rotate an array to the right by k positions. For [1, 2, 3, 4, 5, 6, 7] and k = 3, the result is [5, 6, 7, 1, 2, 3, 4]: the last three elements wrap around to the front.

A direct approach moves each element k places to the right using a second array. It works in O(n) time but uses O(n) space. A neat in-place method uses three reversals:

1. Reverse the whole array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

For [1, 2, 3, 4, 5, 6, 7] with k = 3:

Why does it work? The first reversal puts the last k elements at the front, but backwards. The two smaller reversals put each block back into its original order.

Two details matter. If k is larger than the array length, rotating by k is the same as rotating by k % n. And a negative k means rotating left, which we can handle by adding n.

Problem. Move all zeroes to the end while keeping the order of the non-zero elements: [0, 1, 0, 3, 12] becomes [1, 3, 12, 0, 0].

Use two indexes. read scans the array. write marks where the next non-zero element belongs. Each time read finds a non-zero value, copy it to write and advance write. When read finishes, fill the rest with zeroes.

// File: Main.javaimport java.util.Arrays;public class Main {    // Reverses a[from..to], both ends inclusive.    static void reverse(int[] a, int from, int to) {        while (from < to) {            int temp = a[from];            a[from] = a[to];            a[to] = temp;            from++;            to--;        }    }    // Rotates right by k. A negative k rotates left.    static void rotateRight(int[] a, int k) {        int n = a.length;        if (n == 0) {            return;        }        k = k % n;        if (k < 0) {            k += n;                  // turn a left rotation into the equivalent right one        }        reverse(a, 0, n - 1);        reverse(a, 0, k - 1);        reverse(a, k, n - 1);    }    static void moveZeroesToEnd(int[] a) {        int write = 0;        for (int read = 0; read < a.length; read++) {            if (a[read] != 0) {                a[write] = a[read];                write++;            }        }        while (write < a.length) {            a[write] = 0;            write++;        }    }    public static void main(String[] args) {        int[][] tests = {{1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1}, {}};        int[] ks = {3, 10, 0, -1, 5, 2};        for (int t = 0; t < tests.length; t++) {            rotateRight(tests[t], ks[t]);            System.out.println("k=" + ks[t] + " " + Arrays.toString(tests[t]));        }        int[] withZeroes = {0, 1, 0, 3, 12};        moveZeroesToEnd(withZeroes);        System.out.println(Arrays.toString(withZeroes));    }}

k=3 [5, 6, 7, 1, 2, 3, 4]k=10 [5, 6, 7, 1, 2, 3, 4]k=0 [1, 2, 3, 4, 5, 6, 7]k=-1 [2, 3, 4, 5, 6, 7, 1]k=5 [1]k=2 [][1, 3, 12, 0, 0]

k = 10 behaves like k = 3, because 10 % 7 = 3. k = -1 rotates left by one. k = 0 leaves the array alone, and in that case the second reversal has from = 0 and to = -1, so the loop does nothing, which is exactly right. The empty and single-element cases are covered too.

Complexity: rotation does about 2n swaps in total, so O(n) time and O(1) space. Moving zeroes makes one pass and a short fill, so O(n) time and O(1) space.

A subarray is a contiguous slice of an array: it keeps the elements in order and with no gaps. For [3, 1, 4], the subarrays are [3], [1], [4], [3, 1], [1, 4] and [3, 1, 4]. A subsequence, by contrast, may skip elements. [3, 4] is a subsequence but not a subarray.

An array of length n has n × (n + 1) / 2 subarrays: for each of the n starting positions, you can end anywhere from that position onwards. That is O(n^2) subarrays, so any approach that looks at each one separately is at best quadratic.

Problem. Given an array of integers (some may be negative), find the largest sum of any non-empty subarray. For [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is 6, from [4, -1, 2, 1].

Brute force. Try every start. For each start, extend the end one step at a time, keeping a running sum, and record the best. That is O(n^2) time and O(1) space. (Computing each sum from scratch would be O(n^3), so use the running sum.)

Optimization. Walk through the array once. At each position i, ask: what is the best sum of a subarray that ends exactly here? There are only two choices. Either the subarray is just a[i] by itself (restart), or it is the best subarray ending at i - 1 plus a[i] (extend). Pick the larger:

bestEndingHere = max(a[i], bestEndingHere + a[i])bestOverall    = max(bestOverall, bestEndingHere)

If the previous running sum has become negative, extending would only drag the total down, so we restart at a[i]. This idea is known as Kadane's algorithm. It is a first taste of dynamic programming, where we build an answer from answers to smaller versions of the same question. We return to it in Dynamic Programming Foundations.

Dry run on [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

The answer is 6.

// File: Main.javapublic class Main {    // Brute force: O(n^2) time, O(1) space.    static long maxSubarraySumBrute(int[] a) {        long best = a[0];        for (int start = 0; start < a.length; start++) {            long sum = 0;            for (int end = start; end < a.length; end++) {                sum += a[end];                best = Math.max(best, sum);            }        }        return best;    }    // Kadane: O(n) time, O(1) space.    static long maxSubarraySum(int[] a) {        long bestEndingHere = a[0];        long bestOverall = a[0];        for (int i = 1; i < a.length; i++) {            bestEndingHere = Math.max(a[i], bestEndingHere + a[i]);            bestOverall = Math.max(bestOverall, bestEndingHere);        }        return bestOverall;    }    public static void main(String[] args) {        int[][] tests = {            {-2, 1, -3, 4, -1, 2, 1, -5, 4},            {-3, -1, -2},            {5},            {2, 3, 4},            {Integer.MAX_VALUE, Integer.MAX_VALUE}        };        for (int[] test : tests) {            System.out.println(maxSubarraySumBrute(test) + " " + maxSubarraySum(test));        }    }}

6 6-1 -15 59 94294967294 4294967294

Check the edge cases: when every number is negative ([-3, -1, -2]), the answer is the single largest element, -1, because the problem says the subarray must be non-empty. Starting from a[0] handles that. If instead you started bestOverall at 0, you would wrongly report an empty subarray. The last test would overflow with int arithmetic: two copies of Integer.MAX_VALUE add up to more than an int can hold. We used long for the sums.

A 2D array is an array of arrays, and traversal needs two loops. A common mistake is mixing up rows and columns. If grid is declared new int[rows][cols], then grid.length is the number of rows and grid[0].length is the number of columns.

// File: Main.javapublic class Main {    public static void main(String[] args) {        int[][] grid = {            {1, 2, 3, 4},            {5, 6, 7, 8},            {9, 10, 11, 12}        };        int rows = grid.length;        int cols = grid[0].length;        long[] rowSums = new long[rows];        long[] colSums = new long[cols];        for (int r = 0; r < rows; r++) {            for (int c = 0; c < cols; c++) {                rowSums[r] += grid[r][c];                colSums[c] += grid[r][c];            }        }        System.out.println(java.util.Arrays.toString(rowSums));        System.out.println(java.util.Arrays.toString(colSums));    }}

[10, 26, 42][15, 18, 21, 24]

Time is O(rows × cols), which is the number of cells. We will treat grids as graphs in Graphs: Representations, BFS, and DFS.

In practice: use arrays when the size is known, and ArrayList when you are collecting results whose count you do not know yet.

• Empty array. a[0] crashes. Check a.length first, or document the assumption.
• Single element. Loops that compare neighbours may not run. Check that the answer is still right.
• Off-by-one in bounds. Use i < a.length, and for neighbour access i + 1 < a.length.
• All negative numbers. Starting a maximum at 0 is wrong.
• Overflow of sums. Add ints into a long.
• Modifying the input when you should not. If the problem does not allow it, copy first with Arrays.copyOf.
• Shifting in the wrong direction. When inserting, copy from the right end. When deleting, copy from the left.
• Forgetting that arrays are references. int[] b = a does not copy, as we saw in the Java article.
• Assuming the array is sorted. Many tricks (binary search, two pointers on sorted data) only work if it is. If it is not stated, ask.

static void rotateRightBuggy(int[] a, int k) {    reverse(a, 0, a.length - 1);    reverse(a, 0, k);    reverse(a, k, a.length - 1);}

// File: Main.javapublic class Main {    static int missingNumber(int[] a) {        long n = a.length;        long expected = n * (n + 1) / 2;        long actual = 0;        for (int value : a) {            actual += value;        }        return (int) (expected - actual);    }    public static void main(String[] args) {        System.out.println(missingNumber(new int[] {3, 0, 1}));        System.out.println(missingNumber(new int[] {0, 1}));        System.out.println(missingNumber(new int[] {1}));        System.out.println(missingNumber(new int[] {0}));        System.out.println(missingNumber(new int[] {}));    }}

22010

// File: Main.javaimport java.util.Arrays;public class Main {    static int[] merge(int[] x, int[] y) {        int[] result = new int[x.length + y.length];        int i = 0;        int j = 0;        int k = 0;        while (i < x.length && j < y.length) {            if (x[i] <= y[j]) {                result[k++] = x[i++];            } else {                result[k++] = y[j++];            }        }        while (i < x.length) {            result[k++] = x[i++];        }        while (j < y.length) {            result[k++] = y[j++];        }        return result;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(merge(new int[] {1, 4, 9}, new int[] {2, 3, 10, 11})));        System.out.println(Arrays.toString(merge(new int[] {}, new int[] {5})));        System.out.println(Arrays.toString(merge(new int[] {2, 2}, new int[] {2})));        System.out.println(Arrays.toString(merge(new int[] {}, new int[] {})));    }}

[1, 2, 3, 4, 9, 10, 11][5][2, 2, 2][]

// File: Main.javapublic class Main {    static boolean isRotatedSorted(int[] a) {        int n = a.length;        int drops = 0;        for (int i = 0; i < n; i++) {            if (a[i] > a[(i + 1) % n]) {                drops++;            }        }        return drops <= 1;    }    public static void main(String[] args) {        System.out.println(isRotatedSorted(new int[] {3, 4, 5, 1, 2}));        System.out.println(isRotatedSorted(new int[] {2, 1, 3, 4}));        System.out.println(isRotatedSorted(new int[] {1, 2, 3}));        System.out.println(isRotatedSorted(new int[] {2, 2, 2}));        System.out.println(isRotatedSorted(new int[] {5}));        System.out.println(isRotatedSorted(new int[] {}));        System.out.println(isRotatedSorted(new int[] {1, 3, 2}));    }}

truefalsetruetruetruetruefalse

• Next: Strings: Characters, Immutability, and Efficient Manipulation applies the same ideas to text, with the extra twist that Java strings cannot be changed.
• Looking ahead: moving zeroes with read and write indexes is a first look at Two Pointers. Computing sums of ranges quickly is the subject of Prefix Sums and Difference Arrays.
• Practice habit: for every array problem, write down what happens with an empty array, a single element, and all-equal values before you submit.