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 32value: [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 elementThe 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 valuesint first = numbers[0]; // 10 (access)numbers[1] = 25; // [10, 25, 30, 40] (update)int length = numbers.length; // 4 (a field, so no brackets)
| Operation | Example | Time |
|---|---|---|
| Create | int[] arr = new int[5]; | O(n) |
| Initialize | int[] arr = {1, 2, 3}; | O(n) |
| Access | arr[0] | O(1) |
| Update | arr[0] = 10; | O(1) |
| Length | arr.length | O(1) |
Things to remember:
new int[5]fills the array with default values:0for numbers,falsefor booleans, andnullfor objects.lengthis a field on arrays (arr.length). On a String it is a method (s.length()).- Going outside
0tolength - 1throws an ArrayIndexOutOfBoundsException.
Looping Through an Array
int[] numbers = {10, 20, 30, 40};// Index loop: use when you need the positionfor (int index = 0; index < numbers.length; index++) {System.out.print(numbers[index] + " ");}// For-each loop: use when you only need the valuesfor (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 --> 2The 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; // 2int columns = matrix[0].length; // 3for (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 awaySystem.out.println(s); // Hello (unchanged)s = s.toUpperCase(); // save the new StringSystem.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 Heap6+-----------+ +-----------+7| "Hello" | <--- a, c | "Hello" | <--- b8+-----------+ +-----------+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
| Method | Example | Result |
|---|---|---|
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(); // 5char 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"); // trueboolean has = text.contains("ell"); // trueint 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)includesstartbut excludesend. Sosubstring(1, 4)takes indexes 1, 2, and 3.indexOf()returns-1when 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:
- Create a new String big enough for the old text plus the new part.
- Copy all the old characters into it.
- Add the new part.
- 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 character4step 2: copy 2 characters5step 3: copy 3 characters6step 4: copy 4 characters7step 5: copy 5 characters8 9total copies = 1 + 2 + 3 + ... + n = about n * n / 2 --> O(n^2)10 11Using StringBuilder:12 13each append writes only the new part14total 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 loopString result = "";for (int i = 0; i < 5; i++) {result += i;}// Fast: one StringBuilder is reused in every loopStringBuilder 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 objectappendwrites the new characters into the free slots and increaseslength. No new object is created.- If the buffer is full, Java creates a bigger array (roughly double), copies the old characters once, and continues.
- Doubling is rare, so the cost per append is O(1) on average. This is called amortized O(1).
- 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 Worldbuilder.insert(0, "Hi "); // Hi Hello Worldbuilder.delete(0, 3); // Hello World (end is excluded)builder.setCharAt(0, 'J'); // Jello Worldbuilder.deleteCharAt(0); // ello Worldbuilder.reverse(); // dlroW ollechar first = builder.charAt(0); // 'd'int length = builder.length(); // 10String text = builder.toString(); // "dlroW olle"
| Method | Example | Purpose | Time |
|---|---|---|---|
append() | sb.append("Java") | Add text at the end | O(k) amortized, k = new text |
insert() | sb.insert(0, "Hi ") | Insert text | O(n), later characters shift |
delete() | sb.delete(0, 3) | Delete a range | O(n), later characters shift |
deleteCharAt() | sb.deleteCharAt(0) | Delete one character | O(n), later characters shift |
reverse() | sb.reverse() | Reverse in place | O(n) |
charAt() | sb.charAt(0) | Get a character | O(1) |
setCharAt() | sb.setCharAt(0, 'A') | Change a character | O(1) |
length() | sb.length() | Get the length | O(1) |
toString() | sb.toString() | Convert to String | O(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:
StringBuilderdoes not overrideequals(). 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
| String | StringBuilder | StringBuffer | |
|---|---|---|---|
| Mutable? | No | Yes | Yes |
| Thread-safe? | Yes (it never changes) | No | Yes (synchronized) |
| Speed | Slow for many changes | Fastest | Slower than StringBuilder |
| Use when | The value will not change | Building text in one thread | Many threads change the same text |
Interview Tip: Whenever you build a String inside a loop (reversing, joining, building an answer), use
StringBuilderinstead 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 type | Algorithm used | Stable? | Time |
|---|---|---|---|
Primitives (int[], char[]) | Dual-Pivot Quicksort | Not needed, equal numbers look the same | O(n log n) on average |
Objects (Integer[], String[]) | TimSort (merge sort based) | Yes | O(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 valueArrays.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]]
| Method | Use for | Example output |
|---|---|---|
Arrays.toString(arr) | 1D array | [10, 20, 30] |
Arrays.deepToString(arr) | 2D array (or deeper) | [[1, 2], [3, 4]] |