Arrays and types

Use int[] when every value and every intermediate result fits in 32 bits, and long[] otherwise (large sums, products, prefix sums over many large numbers). A long[] doubles the memory and halves how many values fit in a cache line.

Summing int values into an int accumulator overflows silently. Make the accumulator long even when the array is int[].

1int[] a = {2_000_000_000, 2_000_000_000};
2int bad = a[0] + a[1];          // -294967296 (overflow)
3long good = (long) a[0] + a[1]; // 4000000000

char is a 16-bit unsigned number that prints as a character. Arithmetic on it produces an int, which makes counting letters easy: c - 'a' is the 0-25 index of a lowercase letter, and c - '0' is a digit's value.

Cast back to char when you want a character result.

1int idx = 'd' - 'a';              // 3
2int digit = '7' - '0';            // 7
3char next = (char) ('a' + 2);     // 'c'
4int[] freq = new int[26];
5for (char c : "banana".toCharArray()) freq[c - 'a']++;   // a=3, b=1, n=2

A 2D array is an array of row arrays. new int[3][4] makes three rows of four columns, each element 0. Access is grid[row][col]. Traverse row by row for cache-friendly access.

The animation in Chapter 4 shows why row-major order is faster than column-major.

1int[][] grid = new int[3][4];
2grid[1][2] = 5;
3int rows = grid.length, cols = grid[0].length;
4for (int r = 0; r < rows; r++)
5    for (int c = 0; c < cols; c++) grid[r][c] += r * cols + c;

Rows of a Java 2D array can have different lengths. Allocate only the first dimension, then each row separately. Jagged arrays save memory for triangular data such as Pascal's triangle or adjacency lists.

Always loop with row.length rather than assuming a rectangle.

1int[][] tri = new int[4][];
2for (int i = 0; i < tri.length; i++) {
3    tri[i] = new int[i + 1];
4    tri[i][0] = tri[i][i] = 1;
5    for (int j = 1; j < i; j++) tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
6}
7// tri = [[1], [1,1], [1,2,1], [1,3,3,1]]

Array elements are initialised automatically: 0 for numeric types, false for boolean, '\u0000' for char and null for references. Local variables are not.

To start from another value use Arrays.fill. A common choice is Integer.MAX_VALUE / 2 as “infinity” in distance arrays, to avoid overflow when adding.

1int[] a = new int[3];            // [0, 0, 0]
2String[] s = new String[2];      // [null, null]
3int[] dist = new int[5];
4Arrays.fill(dist, Integer.MAX_VALUE / 2);

An array variable holds a reference. b = a makes two names for one array, so writing through b changes what a shows. Passing an array to a method also shares it.

Use the animation to step through alias, clone, shallow copy and deep copy of a 2D array and see exactly which cells are shared.

1int[] a = {1, 2, 3};
2int[] b = a;     // alias
3b[0] = 99;       // a[0] is now 99 as well
4int[] c = a.clone();
5c[1] = -1;       // a is unchanged

1int[] a = { 10, 20, 30, 40 };               // options 0 and 1 use this 1D array
2int[] b = a;                                // option 0: copies the reference only
3int[] b = a.clone();                        // option 1: copies the elements
4int[][] a2 = { { 10, 20 }, { 30, 40 } };    // options 2 and 3 use this 2D array
5int[][] b2 = a2.clone();                    // option 2: new outer array, SAME row objects
6int[][] b2 = Arrays.stream(a2).map(int[]::clone).toArray(int[][]::new);   // option 3: rows copied too
7b[idx] = v;                                 // (b2[0][idx] = v for options 2 and 3)
8System.out.println(Arrays.toString(a));     // does a see the change?

To copy a 1D primitive array use clone(), Arrays.copyOf(a, len) or System.arraycopy. copyOf can also grow or truncate. For 2D arrays clone() is shallow: it copies the row references, so rows are still shared. Copy each row to get a deep copy.

System.arraycopy handles overlapping ranges correctly, which is useful for shifting elements.

1int[][] g = {{1, 2}, {3, 4}};
2int[][] shallow = g.clone();                 // rows shared
3int[][] deep = new int[g.length][];
4for (int i = 0; i < g.length; i++) deep[i] = g[i].clone();
5shallow[0][0] = 9;   // visible in g
6deep[1][1] = 7;      // not visible in g
7
8int[] x = {1, 2, 3, 4, 5};
9System.arraycopy(x, 0, x, 1, 4);   // shift right by one: [1, 1, 2, 3, 4]

1int[] a = { 10, 20, 30, 40 };               // options 0 and 1 use this 1D array
2int[] b = a;                                // option 0: copies the reference only
3int[] b = a.clone();                        // option 1: copies the elements
4int[][] a2 = { { 10, 20 }, { 30, 40 } };    // options 2 and 3 use this 2D array
5int[][] b2 = a2.clone();                    // option 2: new outer array, SAME row objects
6int[][] b2 = Arrays.stream(a2).map(int[]::clone).toArray(int[][]::new);   // option 3: rows copied too
7b[idx] = v;                                 // (b2[0][idx] = v for options 2 and 3)
8System.out.println(Arrays.toString(a));     // does a see the change?

java.util.Arrays provides sort, fill, copyOf, copyOfRange, equals, toString, deepToString, binarySearch, asList and stream. Never print an array directly; System.out.println(a) shows the reference, not the values.

Arrays.equals compares contents; a.equals(b) compares references. Use deepEquals and deepToString for nested arrays.

1int[] a = {5, 3, 9, 1};
2Arrays.sort(a);                          // [1, 3, 5, 9]
3System.out.println(Arrays.toString(a));
4int pos = Arrays.binarySearch(a, 5);     // 2
5int[] part = Arrays.copyOfRange(a, 1, 3);// [3, 5]
6boolean same = Arrays.equals(a, new int[]{1, 3, 5, 9});   // true
7int total = Arrays.stream(a).sum();      // 18