On this page

Arrays & Strings

Arrays

An array is a fixed-size collection of elements of the same data type, stored one after another in memory. Each element has an index, and indexes start at 0.

How an Array Is Stored

When you create an array, Java reserves one continuous block of memory big enough for all the elements. This is why the size is fixed: the block cannot grow in place.

1index: 0 1 2 3
2value: [10] [20] [30] [40]
3address: 100 104 108 112 (an int takes 4 bytes)
4
5address of numbers[i] = start address + i * size of one element

The address is found with one calculation, so reading or updating any element by index takes O(1) time. This is the biggest strength of an array.

1D Array

int[] empty = new int[5]; // [0, 0, 0, 0, 0] (default values)
int[] numbers = {10, 20, 30, 40}; // create with values
int first = numbers[0]; // 10 (access)
numbers[1] = 25; // [10, 25, 30, 40] (update)
int length = numbers.length; // 4 (a field, so no brackets)
OperationExampleTime
Createint[] arr = new int[5];O(n)
Initializeint[] arr = {1, 2, 3};O(n)
Accessarr[0]O(1)
Updatearr[0] = 10;O(1)
Lengtharr.lengthO(1)

Things to remember:

  • new int[5] fills the array with default values: 0 for numbers, false for booleans, and null for objects.
  • length is a field on arrays (arr.length). On a String it is a method (s.length()).
  • Going outside 0 to length - 1 throws an ArrayIndexOutOfBoundsException.

Looping Through an Array

int[] numbers = {10, 20, 30, 40};
// Index loop: use when you need the position
for (int index = 0; index < numbers.length; index++) {
System.out.print(numbers[index] + " ");
}
// For-each loop: use when you only need the values
for (int value : numbers) {
System.out.print(value + " ");
}

In a for-each loop, value is a copy of the element. Changing value does not change the array.

2D Array

A 2D array is an array of arrays. It is commonly used to represent a matrix (rows and columns).

1matrix --> row 0 --> [1] [2] [3]
2 row 1 --> [4] [5] [6]
3
4matrix[0][1] means: go to row 0, then take column 1 --> 2

The first index is the row and the second index is the column.

int[][] matrix = {
{1, 2, 3},
{4, 5, 6}
};
int value = matrix[0][1]; // 2 (row 0, column 1)
int rows = matrix.length; // 2
int columns = matrix[0].length; // 3
for (int row = 0; row < matrix.length; row++) {
for (int column = 0; column < matrix[row].length; column++) {
System.out.print(matrix[row][column] + " ");
}
}

Each row is its own separate array. That is why the inner loop uses matrix[row].length, and why rows are allowed to have different lengths.

Strings

A String is a sequence of characters, like "Akash". Internally it is stored like an array of characters, so charAt(index) is fast.

Strings in Java are immutable:

Once a String is created, its value can never be changed.

1String s = "Hello";
2s ---> "Hello"
3
4s = s + " World";
5s ---> "Hello World" (a brand new String)
6 "Hello" (the old String is untouched)

So s + " World" does not change "Hello". It creates a new String and moves the variable s to point at it.

String s = "Hello";
s.toUpperCase(); // result is thrown away
System.out.println(s); // Hello (unchanged)
s = s.toUpperCase(); // save the new String
System.out.println(s); // HELLO

Why Are Strings Immutable?

  • Safe sharing: Java keeps equal string literals in a String Pool and reuses them. If one variable could change the string, every other variable pointing to it would change too.
  • Security: Strings are used for passwords, file paths, and URLs. They must not change after being checked.
  • Hashing: A String's hash code can be calculated once and saved, which makes Strings fast and safe as HashMap keys.
  • Thread safety: Many threads can read the same String without any locking.

The price is that every change creates a new String. We will see why that matters in the StringBuilder section.

String Pool and equals() vs ==

1String a = "Hello";
2String c = "Hello";
3String b = new String("Hello");
4
5 String Pool Heap
6+-----------+ +-----------+
7| "Hello" | <--- a, c | "Hello" | <--- b
8+-----------+ +-----------+
9 (shared object) (separate new object)
10
11a == c --> true (same object)
12a == b --> false (different objects)
13a.equals(b) --> true (same characters)
  • == checks if two variables point to the same object.
  • .equals() checks if two Strings have the same characters.
String a = "Hello";
String b = new String("Hello");
String c = "Hello";
System.out.println(a.equals(b)); // true (same characters)
System.out.println(a == b); // false (different objects)
System.out.println(a == c); // true (both come from the String Pool)

Interview Tip: Always use .equals() to compare String values. Use == only when you really want to check if it is the same object.

Common String Methods

MethodExampleResult
length()"Hello".length()5
charAt()"Hello".charAt(1)'e'
substring()"Hello".substring(1, 4)"ell"
toUpperCase()"hello".toUpperCase()"HELLO"
toLowerCase()"HELLO".toLowerCase()"hello"
equals()"abc".equals("abc")true
equalsIgnoreCase()"ABC".equalsIgnoreCase("abc")true
contains()"Hello".contains("ell")true
startsWith()"Hello".startsWith("He")true
endsWith()"Hello".endsWith("lo")true
indexOf()"Hello".indexOf('l')2
replace()"abc".replace('a', 'x')"xbc"
trim()" Hello ".trim()"Hello"
isEmpty()"".isEmpty()true
String text = "Hello";
int length = text.length(); // 5
char second = text.charAt(1); // 'e'
String part = text.substring(1, 4); // "ell" (end is excluded)
String upper = text.toUpperCase(); // "HELLO"
boolean same = text.equals("Hello"); // true
boolean has = text.contains("ell"); // true
int position = text.indexOf('l'); // 2 (-1 if not found)
String replaced = text.replace('H', 'J'); // "Jello"
// text is still "Hello": Strings never change

Points to remember:

  • substring(start, end) includes start but excludes end. So substring(1, 4) takes indexes 1, 2, and 3.
  • indexOf() returns -1 when the value is not found.
  • Every method returns a new String. The original is never changed.

Converting Between String and char[]

Since a String cannot be changed, we often convert it to a char[], change the array, and convert it back.

String text = "hello";
char[] chars = text.toCharArray(); // ['h', 'e', 'l', 'l', 'o']
chars[0] = 'j'; // ['j', 'e', 'l', 'l', 'o']
String result = new String(chars); // "jello"
String sameResult = String.valueOf(chars); // "jello"

StringBuilder

StringBuilder is used when you need to change a text many times, such as building an answer inside a loop.

Unlike String, a StringBuilder is mutable: it changes its own content instead of creating a new object each time.

Why Do We Need StringBuilder?

Since a String can never change, result += value does this every time:

  1. Create a new String big enough for the old text plus the new part.
  2. Copy all the old characters into it.
  3. Add the new part.
  4. Throw the old String away.

Inside a loop, this copies the whole text again and again.

1Using String with += in a loop (n = 5):
2
3step 1: copy 1 character
4step 2: copy 2 characters
5step 3: copy 3 characters
6step 4: copy 4 characters
7step 5: copy 5 characters
8
9total copies = 1 + 2 + 3 + ... + n = about n * n / 2 --> O(n^2)
10
11Using StringBuilder:
12
13each append writes only the new part
14total work = n --> O(n)

For 100,000 characters, the String way does billions of copies, while StringBuilder does about 100,000 writes.

// Slow: a new String is created in every loop
String result = "";
for (int i = 0; i < 5; i++) {
result += i;
}
// Fast: one StringBuilder is reused in every loop
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 5; i++) {
builder.append(i);
}
String finalText = builder.toString(); // "01234"

How StringBuilder Works

Inside, a StringBuilder keeps two things:

  • A character array called the buffer, which is often bigger than the text.
  • A number called length, which says how many slots are really used.

The size of the buffer is its capacity. The extra empty slots are what make appending fast.

1StringBuilder builder = new StringBuilder("Hello");
2
3buffer: [H][e][l][l][o][ ][ ][ ][ ][ ][ ] ... (capacity 21, length 5)
4
5builder.append(" World");
6
7buffer: [H][e][l][l][o][ ][W][o][r][l][d][ ] ... (capacity 21, length 11)
8 ^ written into free slots, no new object
  1. append writes the new characters into the free slots and increases length. No new object is created.
  2. If the buffer is full, Java creates a bigger array (roughly double), copies the old characters once, and continues.
  3. Doubling is rare, so the cost per append is O(1) on average. This is called amortized O(1).
  4. At the end, toString() creates one String from the buffer.

An empty new StringBuilder() starts with a capacity of 16. With new StringBuilder("Hello"), the capacity is the text length plus 16, so 21. If you know the final size, you can pass it in, like new StringBuilder(1000), to avoid resizing.

StringBuilder Methods

StringBuilder builder = new StringBuilder("Hello");
builder.append(" World"); // Hello World
builder.insert(0, "Hi "); // Hi Hello World
builder.delete(0, 3); // Hello World (end is excluded)
builder.setCharAt(0, 'J'); // Jello World
builder.deleteCharAt(0); // ello World
builder.reverse(); // dlroW olle
char first = builder.charAt(0); // 'd'
int length = builder.length(); // 10
String text = builder.toString(); // "dlroW olle"
MethodExamplePurposeTime
append()sb.append("Java")Add text at the endO(k) amortized, k = new text
insert()sb.insert(0, "Hi ")Insert textO(n), later characters shift
delete()sb.delete(0, 3)Delete a rangeO(n), later characters shift
deleteCharAt()sb.deleteCharAt(0)Delete one characterO(n), later characters shift
reverse()sb.reverse()Reverse in placeO(n)
charAt()sb.charAt(0)Get a characterO(1)
setCharAt()sb.setCharAt(0, 'A')Change a characterO(1)
length()sb.length()Get the lengthO(1)
toString()sb.toString()Convert to StringO(n), copies the buffer

Adding or deleting at the front is slow because every later character must shift. Adding at the end is the fast case.

Gotcha: StringBuilder does not override equals(). Comparing two builders with .equals() checks if they are the same object, not the same text. Convert first: sb1.toString().equals(sb2.toString()).

String vs StringBuilder vs StringBuffer

StringStringBuilderStringBuffer
Mutable?NoYesYes
Thread-safe?Yes (it never changes)NoYes (synchronized)
SpeedSlow for many changesFastestSlower than StringBuilder
Use whenThe value will not changeBuilding text in one threadMany threads change the same text

Interview Tip: Whenever you build a String inside a loop (reversing, joining, building an answer), use StringBuilder instead of +=.

Arrays.sort()

Arrays.sort() sorts an array in ascending order. It changes the original array (it sorts in place) and returns nothing.

import java.util.Arrays;
int[] arr = {5, 2, 8, 1, 3};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
// [1, 2, 3, 5, 8]

How It Works

Java uses a different algorithm depending on the array type:

Array typeAlgorithm usedStable?Time
Primitives (int[], char[])Dual-Pivot QuicksortNot needed, equal numbers look the sameO(n log n) on average
Objects (Integer[], String[])TimSort (merge sort based)YesO(n log n) worst case

Stable means that equal elements keep their original order. This matters for objects. If you sort people by age, two people with the same age stay in the order they had before.

Sorting a Range

int[] arr = {9, 5, 2, 8, 1, 7};
// Sort only from index 1 up to index 4 (end is excluded)
Arrays.sort(arr, 1, 4);
System.out.println(Arrays.toString(arr));
// [9, 2, 5, 8, 1, 7]

Sorting in Descending Order

A primitive array (int[]) cannot take a custom order. Use the boxed type (Integer[]) together with a comparator.

import java.util.Arrays;
import java.util.Collections;
Integer[] arr = {5, 2, 8, 1, 3};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(Arrays.toString(arr));
// [8, 5, 3, 2, 1]

Sorting with a Custom Rule

For a 2D array, give a comparator that says how to compare two rows. This is common in interval problems.

int[][] intervals = {{5, 8}, {1, 3}, {2, 6}};
// Sort the rows by their first value
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
System.out.println(Arrays.deepToString(intervals));
// [[1, 3], [2, 6], [5, 8]]

Use Integer.compare(a[0], b[0]) instead of a[0] - b[0]. Subtraction can overflow with very large or very small numbers.

Sorting the Characters of a String

A String cannot be sorted directly. Convert it to a char[], sort it, and convert back. This is the usual trick for anagram problems.

String word = "listen";
char[] chars = word.toCharArray();
Arrays.sort(chars);
String sortedWord = new String(chars);
System.out.println(sortedWord);
// eilnst

Arrays.toString()

Arrays.toString() converts a 1D array into a readable String.

If you print an array directly, you do not see the values. You see the type and a hash code, like [I@1b6d3586.

import java.util.Arrays;
int[] arr = {10, 20, 30};
System.out.println(arr);
// [I@1b6d3586 (not useful)
System.out.println(Arrays.toString(arr));
// [10, 20, 30]

Arrays.deepToString()

For a 2D array, Arrays.toString() would print the addresses of the inner arrays. Use Arrays.deepToString() to print everything.

int[][] matrix = {
{1, 2},
{3, 4}
};
System.out.println(Arrays.toString(matrix));
// [[I@6d06d69c, [I@7852e922] (addresses of the rows)
System.out.println(Arrays.deepToString(matrix));
// [[1, 2], [3, 4]]
MethodUse forExample output
Arrays.toString(arr)1D array[10, 20, 30]
Arrays.deepToString(arr)2D array (or deeper)[[1, 2], [3, 4]]
Next TopicClass & Object