Arrays, strings and hashing

Arrays and dynamic arrays

Also called list, ArrayList, vector, resizable array, dynamic array

What

An array stores items side by side in memory, so reading or writing index i is O(1). A dynamic array grows by allocating a bigger block and copying, so appending is O(1) amortised, while inserting or removing in the middle is O(n).

Why

It is the default container for sequences and the backing store for strings, stacks and heaps. Its contiguous layout also makes it fast in practice thanks to the CPU cache.

List<Integer> nums = new ArrayList<>(List.of(3, 1, 4));
nums.add(1);         // amortised O(1)
nums.set(0, 9);      // O(1)
nums.add(0, 2);      // O(n): shifts every item
nums.removeLast();   // O(1) at the end (Java 21)
nums.remove(0);      // O(n) at the front

Strings

What

A string is a sequence of characters. In Python, Java and JavaScript strings are immutable, so every change builds a new string; C++ std::string is mutable. Taking a substring or slice copies it, costing O(k) for k characters.

Why

String problems are array problems with extra costs hidden in concatenation, slicing and comparison, and those costs decide whether a solution is O(n) or O(n^2).

StringBuilder sb = new StringBuilder();
for (String word : words) {
  sb.append(word.toUpperCase());
}
String result = sb.toString();
char[] chars = s.toCharArray();   // mutable copy
chars[0] = 'X';
String s2 = new String(chars);

Hash maps

Also called hash table, dictionary, dict, HashMap, unordered_map, Map

What

A hash map stores key-value pairs in buckets chosen by a hash of the key, giving O(1) average insert, lookup and delete. Collisions are handled by chaining or probing, and the table resizes as it fills.

Why

It is the first tool for counting, grouping, caching and checking whether you have seen something before in one pass, often turning an O(n^2) search into O(n).

Map<String, Integer> counts = new HashMap<>();
for (String w : words) {
  counts.merge(w, 1, Integer::sum);
}
int apples = counts.getOrDefault("apple", 0);
Map<Integer, List<String>> byLen = new HashMap<>();
for (String w : words) {
  byLen.computeIfAbsent(w.length(), k -> new ArrayList<>())
      .add(w);
}

Hash sets

Also called set, HashSet, unordered_set, Set

What

A hash set stores unique keys without values, with O(1) average add, remove and membership check.

Why

Use it for de-duplication, visited markers and membership checks. Checking membership in a list is O(n); in a set it is O(1) on average.

boolean hasDuplicate(int[] nums) {
  Set<Integer> seen = new HashSet<>();
  for (int x : nums) {
    if (!seen.add(x)) return true;   // add is false if present
  }
  return false;
}

Composite and custom keys

Also called tuple key, pair key, composite key

What

When a key is made of several values, like a grid cell or a sorted word, it must be hashable and compare by value. Each language has a safe choice: tuples, records, packed integers or joined strings.

Why

Visited sets on grids and grouping anagrams depend on it, and a wrong key type fails silently by never matching.

record Cell(int r, int c) {}    // equals and hashCode free
Set<Cell> visited = new HashSet<>();
visited.add(new Cell(r, c));
long packed = (long) r * cols + c; // fastest option
Map<String, List<String>> groups = new HashMap<>();
char[] letters = word.toCharArray();
Arrays.sort(letters);
groups.computeIfAbsent(new String(letters),
    k -> new ArrayList<>()).add(word);

Prefix sums

Also called cumulative sum, running total

What

A prefix sum array stores running totals, so prefix[i] is the sum of the first i items. The sum of any range i..j is prefix[j + 1] - prefix[i]: O(1) per query after an O(n) build.

Why

It answers many range-sum queries fast, and combined with a hash map of earlier prefix values it counts subarrays with a given sum in O(n), even with negative numbers.

long[] prefix = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
  prefix[i + 1] = prefix[i] + nums[i];
}
long rangeSum = prefix[j + 1] - prefix[i];  // nums[i..j]

Integer limits and overflow

Also called overflow, MAX_SAFE_INTEGER, INT_MAX, integer overflow

What

Java and C++ int holds up to about 2.1 billion (2^31 - 1); past that Java wraps around and C++ has undefined behaviour. JavaScript numbers are exact integers only up to 2^53 - 1. Python integers grow without limit.

Why

Sums, products and midpoints of large values overflow quietly and give wrong answers with no error, a common cause of failing hidden tests.

int mid = lo + (hi - lo) / 2;   // lo + hi can overflow
long area = (long) w * h;       // widen before multiplying
int max = Integer.MAX_VALUE;    // 2^31 - 1
int q = -7 / 2;                 // -3: truncates toward zero
int r = Math.floorMod(-7, 2);   // 1, while -7 % 2 is -1

Java collections

Also called Collections Framework, ArrayDeque, TreeMap, PriorityQueue

What

ArrayList is a dynamic array, HashMap and HashSet are hash tables, ArrayDeque is the stack and the queue, PriorityQueue is a binary min-heap, and TreeMap and TreeSet are red-black trees with O(log n) ordered lookups like ceilingKey.

Why

Matching each structure to the right class keeps solutions fast. Stack, Vector and LinkedList still exist but are slower legacy or niche choices.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);                    // O(1); avoid legacy Stack
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.poll();                     // O(1)
TreeMap<Integer, String> sorted = new TreeMap<>();
Integer atLeast5 = sorted.ceilingKey(5);   // O(log n)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Comparator.reverseOrder());