☕ DSA Java Articles

Topics › Basics › Things to Know in C++/Java/Python or any language

What are arrays, strings?

Easy TUF ID 2869 A2Z

Java source ↗ Edit this article ↗

What this covers

Arrays and strings are the two data structures that every other topic on these sheets is built on. An array is a fixed-size block of slots of one type, addressed by an index from 0 to length - 1. A String is an immutable sequence of characters with a rich set of methods. This article explains how each is created and accessed, the reference semantics that make arrays behave differently from numbers when passed around, two-dimensional arrays, the immutability of strings and what it means for performance, and the char-arithmetic trick that turns letters into array indices.

Creating and indexing an array

new int[n] allocates n slots, all initialised to 0 (false for boolean[], null for object arrays). Reading or writing uses a[i], and a.length (a field, not a method) gives the size. Indices run from 0 to n - 1; anything else throws ArrayIndexOutOfBoundsException.

static int[] squares(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = i * i;
    return a;
}

For n = 0 the array is empty and the loop runs zero times, which is a legitimate value, not an error. When the index itself is not needed, the enhanced for visits each element in order:

static long sum(int[] a) {
    long total = 0;
    for (int x : a) total += x;
    return total;
}

The accumulator is a long because 10^5 values of 10^4 each already exceed what an int holds. The enhanced loop gives you a copy of each element in x; assigning to x does not change the array, so use an index loop when you need to write.

Arrays are references

An array variable does not hold the elements; it holds a reference to the array object. Passing the array to a method copies that reference, so the method works on the same elements and any change it makes is visible to the caller. That is what makes in-place algorithms possible:

static void reverseInPlace(int[] a) {
    int i = 0, j = a.length - 1;
    while (i < j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
        i++;
        j--;
    }
}

The method returns nothing, yet after the call the caller’s array is reversed. The same fact has a flip side. Writing int[] alias = a; does not copy the elements; it creates a second name for the same array. To get an independent copy, use Arrays.copyOf:

static boolean[] aliasVersusCopy(int[] a) {
    int[] alias = a;
    int[] copy = Arrays.copyOf(a, a.length);
    alias[0] = 99;
    return new boolean[]{a[0] == 99, copy[0] == 99};
}

The result is always {true, false}: writing through alias changed a, while copy kept the old value. Comparing arrays has the same trap: a == b asks whether they are the same object; Arrays.equals(a, b) asks whether they hold the same elements. Arrays.toString(a) prints the contents, whereas System.out.println(a) prints something like [I@1b6d3586.

Two-dimensional arrays

new int[rows][cols] creates an array of rows references, each pointing at a row array of cols ints. grid[r][c] is column c of row r, and grid.length is the number of rows while grid[r].length is the width of that row.

static int[][] identity(int n) {
    int[][] grid = new int[n][n];
    for (int i = 0; i < n; i++) grid[i][i] = 1;
    return grid;
}

Because every row is its own array, rows may have different lengths (a “jagged” array), and a row may even be empty. Code that loops to a fixed width breaks on such input; looping to grid[r].length does not:

static int[] rowSums(int[][] grid) {
    int[] sums = new int[grid.length];
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[r].length; c++) sums[r] += grid[r][c];
    }
    return sums;
}

To compare 2D arrays by content use Arrays.deepEquals; plain Arrays.equals would compare the row references.

Strings: a sequence of chars

A String is a sequence of char values. s.length() (a method this time) gives the count, s.charAt(i) returns the character at index i, and the same 0 to length - 1 rule applies. The usual loop looks exactly like an array loop:

static int countVowels(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = Character.toLowerCase(s.charAt(i));
        if ("aeiou".indexOf(c) >= 0) count++;
    }
    return count;
}

"aeiou".indexOf(c) returns the position of c in that string, or -1 when absent, which is a compact membership test for a handful of characters. Other everyday methods: substring(from, to) (end exclusive), indexOf, contains, startsWith, split, trim, toUpperCase, and equals for comparison.

Strings are immutable

No method on String changes the string it is called on. Every “modifying” method returns a new string, and the original is untouched:

static String[] concatDoesNotMutate(String s) {
    String t = s.concat("!");
    return new String[]{s, t};
}

concatDoesNotMutate("hi") returns {"hi", "hi!"}. Calling s.concat("!") and ignoring the result does nothing at all, which is a frequent beginner bug. Immutability also means a string cannot be reversed in place; the standard approach is to copy it into a char[], which is mutable, work there, and build a new string at the end:

static String reverse(String s) {
    char[] c = s.toCharArray();
    int i = 0, j = c.length - 1;
    while (i < j) {
        char t = c[i];
        c[i] = c[j];
        c[j] = t;
        i++;
        j--;
    }
    return new String(c);
}

Compare this with reverseInPlace above: the loop is identical, only the container changed.

Letters as array indices

Because a char is a number ('a' is 97), c - 'a' maps the lowercase letters to 0 through 25. A 26-slot array indexed this way is the fastest possible frequency table, and it appears in anagram checks, first-unique-character problems and many string hashing solutions:

static int[] letterFrequency(String s) {
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= 'a' && c <= 'z') freq[c - 'a']++;
    }
    return freq;
}

The range check matters: without it an uppercase letter or a space would produce a negative or oversized index and throw. For arbitrary characters use a HashMap<Character, Integer> or a int[128] table indexed by the char itself.

Building strings efficiently

Since each + on strings creates a new object and copies all characters so far, building a long string with result += piece in a loop costs O(n^2) characters copied. StringBuilder keeps a growable buffer and appends in amortised constant time; convert to a String once at the end.

static String joinReversedWords(String sentence) {
    String[] words = sentence.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        if (sb.length() > 0) sb.append(' ');
        sb.append(words[i]);
    }
    return sb.toString();
}

The sb.length() > 0 guard adds a space before every word except the first, so there is no trailing space to trim afterwards. split("\\s+") collapses runs of blanks, and trim() prevents an empty first piece when the sentence starts with spaces.

Edge cases and pitfalls