5. Arrays & Collections

Note

Why this matters for DSA Arrays and Collections are the fundamental containers of data. 95% of LeetCode problems require storing, traversing, or searching through these collections. Choosing between a fixed-size Array, dynamic ArrayList, quick-lookup HashMap, or unique-element HashSet dictates both the time and space complexity of your solution.

5.1 Fixed-Size Arrays

Fixed-size arrays are block allocations of memory. Their sizes cannot change after creation.

java

import java.util.Arrays;

// 1. Creation & Initialization
int[] arr = new int[5]; // size 5, default values are 0
int[] primes = {2, 3, 5, 7, 11}; // initialized with values

// 2. Access
int first = primes[0]; // 2
int length = primes.length; // 5 (note: 'length' is a property, not a method)

// 3. 2D Arrays (Grid / Matrix)
int[][] grid = new int[3][4]; // 3 rows, 4 columns
int[][] initializedGrid = {
    {1, 2},
    {3, 4}
};

Essential `Arrays` Utility Methods

java

int[] nums = {3, 1, 4, 1, 5};

Arrays.sort(nums); // Sorts array in-place to [1, 1, 3, 4, 5] -> O(N log N)
Arrays.fill(nums, -1); // Fills entire array with -1 -> [ -1, -1, -1, -1, -1] -> O(N)

// Printing arrays (don't use toString() directly on arrays - prints memory reference)
System.out.println(Arrays.toString(nums)); // Prints: [-1, -1, -1, -1, -1]
System.out.println(Arrays.deepToString(grid)); // Works for multi-dimensional grids

5.2 ArrayList (Dynamic Array)

An ArrayList acts like Python's list — it resizes automatically as elements are added.

java

import java.util.ArrayList;
import java.util.Collections;

ArrayList<Integer> list = new ArrayList<>();

// 1. Modification
list.add(10); // Adds to end -> [10]
list.add(20); // [10, 20]
list.add(1, 15); // Insert at index 1 -> [10, 15, 20]
list.set(0, 99); // Updates index 0 -> [99, 15, 20]

// 2. Access & Check
int val = list.get(1); // 15
int size = list.size(); // 3 (method calls size())
boolean hasElement = list.contains(20); // true

// 3. Deletion
list.remove(0); // Removes by index -> [15, 20]
list.remove(Integer.valueOf(20)); // Removes by value -> [15]
list.clear(); // Empty the list -> []

Dynamic Array sorting

java

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4));
Collections.sort(numbers); // Sorts ascending [1, 3, 4]
Collections.sort(numbers, Collections.reverseOrder()); // Sorts descending [4, 3, 1]

5.3 HashMap (Key-Value Dictionary)

A HashMap stores key-value pairs. It provides $O(1)$ average time complexity for insertions, updates, and lookups.

java

import java.util.HashMap;
import java.util.Map;

HashMap<String, Integer> map = new HashMap<>();

// 1. Insertion & Updates
map.put("apple", 10);
map.put("banana", 20);
map.put("apple", 15); // Overwrites/updates key "apple"

// 2. Lookups & Checks
map.get("apple"); // 15
map.get("grape"); // null (returns null if key doesn't exist)
map.getOrDefault("grape", 0); // 0 (safely returns default if key is absent)

map.containsKey("apple"); // true
map.containsValue(20); // true

// 3. Deletion
map.remove("banana"); // removes "banana" and returns its value (20)

Iteration Patterns

java

// Iterate keys
for (String key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}

// Iterate entries (efficient, avoids multiple get lookups)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

⭐ The Frequency Counter Pattern

The single most common pattern in HashMaps. Used to count occurrences of characters or numbers.

java

int[] nums = {1, 2, 2, 3, 3, 3};
HashMap<Integer, Integer> counts = new HashMap<>();

for (int num : nums) {
    counts.put(num, counts.getOrDefault(num, 0) + 1);
}
// Result: {1=1, 2=2, 3=3}

5.4 HashSet (Unique Sets)

A HashSet contains unique elements (no duplicates). It provides $O(1)$ check and insert operations.

java

import java.util.HashSet;
import java.util.Arrays;

HashSet<Integer> set = new HashSet<>();

// 1. Operations
set.add(10);
set.add(20);
set.add(10); // Duplicate ignored, set remains [10, 20]

set.contains(20); // true
set.remove(10); // removes 10
set.size(); // 1

Set Operations (Union, Intersection, Difference)

java

HashSet<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3));
HashSet<Integer> setB = new HashSet<>(Arrays.asList(3, 4, 5));

// Union
setA.addAll(setB); // setA is now [1, 2, 3, 4, 5]

// Intersection
setA.retainAll(setB); // setA is now [3, 4, 5]

// Difference
setA.removeAll(setB); // setA is now [1, 2]

5.5 Comparison Summary

Container	Search / Access	Insertion	Deletion	Use Case
`Array`	$O(1)$ by index / $O(N)$ value search	N/A (Fixed size)	N/A	High-speed fixed records, matrices
`ArrayList`	$O(1)$ by index / $O(N)$ value search	$O(1)$ amortized to end	$O(N)$ (requires shifting values)	General lists, stacks, dynamic caches
`HashMap`	$O(1)$ by key average	$O(1)$ average	$O(1)$ average	Frequency count, memoization, key-value mappings
`HashSet`	$O(1)$ search average	$O(1)$ average	$O(1)$ average	Duplicate detection, tracking visited states

Practice Drill

java

// Try implementing these:
// 1. Find the largest element in an array.
// 2. Remove duplicates from an ArrayList while preserving the insertion order.
// 3. Find the first non-repeating character in a string using a HashMap.
// 4. Two Sum: Given an array of integers and a target, return indices of the two numbers that add up to target. (Use HashMap for O(n) time).

💡 Click for Solutions

java

import java.util.*;

public class ArraysCollectionsDrill {
    public static void main(String[] args) {
        // 1. Largest element
        int[] arr = {3, 7, 2, 9, 5};
        int maxVal = arr[0];
        for (int num : arr) {
            if (num > maxVal) maxVal = num;
        }
        System.out.println("Largest: " + maxVal); // 9

        // 2. Remove duplicates preserving order
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 1, 4));
        HashSet<Integer> seen = new HashSet<>();
        ArrayList<Integer> uniqueList = new ArrayList<>();
        for (int val : list) {
            if (!seen.contains(val)) {
                uniqueList.add(val);
                seen.add(val);
            }
        }
        System.out.println("Unique preserving order: " + uniqueList); // [1, 2, 3, 4]

        // 3. First non-repeating character
        String s = "swiss";
        char firstNonRepeat = firstUniqueChar(s);
        System.out.println("First unique char: " + firstNonRepeat); // 'w'

        // 4. Two Sum O(n)
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] indices = twoSum(nums, target);
        System.out.println("Two Sum indices: " + Arrays.toString(indices)); // [0, 1]
    }

    public static char firstUniqueChar(String s) {
        HashMap<Character, Integer> counts = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);
        }
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (counts.get(ch) == 1) {
                return ch;
            }
        }
        return '\0'; // None found
    }

    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[]{};
    }
}

← Functions | Next → Stack, Queue & Deque

5. Arrays & Collections

5.1 Fixed-Size Arrays

Essential Arrays Utility Methods

5.2 ArrayList (Dynamic Array)

Dynamic Array sorting

5.3 HashMap (Key-Value Dictionary)

Iteration Patterns

⭐ The Frequency Counter Pattern

5.4 HashSet (Unique Sets)

Set Operations (Union, Intersection, Difference)

5.5 Comparison Summary

Practice Drill

Essential `Arrays` Utility Methods