Counting patterns

The **frequency map** (Map<T, Integer>) is the most common hash-table pattern: loop once, counts.merge(x, 1, Integer::sum), and then ask questions of the counts. It replaces nested loops that would otherwise compare every pair (O(n²)) with a single O(n) pass.

When the keys are small dense integers or letters, an int[] count array is faster and smaller; use a map when keys are strings, large numbers or objects. Run the animation with “Count with merge”.

1static Map<Character, Integer> letterCounts(String s) {
2    Map<Character, Integer> counts = new HashMap<>();
3    for (char c : s.toCharArray()) counts.merge(c, 1, Integer::sum);
4    return counts;
5}

1Map<String, Integer> counts = new HashMap<>();
2for (String w : words) counts.put(w, counts.getOrDefault(w, 0) + 1);              // option 0: a default for a missing key
3for (String w : words) counts.merge(w, 1, Integer::sum);                           // option 1: insert 1, or combine with the old value
4Map<Integer, List<String>> byLength = new HashMap<>();
5for (String w : words) byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);   // option 2: create the list on first use

A majority element appears **more than n/2 times**. Count with a map and return as soon as a count passes n/2. At most one value can exceed half the array, so the first one that does is the answer.

Exactly half is not enough: in [1, 1, 2, 2] no value exceeds 2, so there is no majority. The Boyer-Moore voting algorithm finds the majority in O(1) space, but the map version is simpler and also handles variants such as “more than n/3”.

1static int majority(int[] nums) {
2    Map<Integer, Integer> counts = new HashMap<>();
3    for (int x : nums) {
4        int c = counts.merge(x, 1, Integer::sum);
5        if (c > nums.length / 2) return x;          // strictly more than half of all elements
6    }
7    return -1;                                       // no majority
8}

1static int majority(int[] nums) {
2    Map<Integer, Integer> counts = new HashMap<>();
3    for (int x : nums) {
4        int c = counts.merge(x, 1, Integer::sum);
5        if (c > nums.length / 2) return x;          // strictly more than half of all elements
6    }
7    return -1;                                       // no majority
8}

Anagrams share exactly the same letters, so sorting the letters of a word gives a **canonical key**: eat, tea and ate all become aet. Put each word into the list stored under its key. The values of the map are the groups.

Sorting a word of length k costs O(k log k), so n words cost O(n · k log k). If words only use a–z, a 26-count signature is an alternative key that avoids the sort. A LinkedHashMap keeps groups in first-seen order, which makes the output reproducible: [[eat, tea, ate], [tan, nat], [bat]] for the classic input.

1static List<List<String>> groupAnagrams(String[] words) {
2    Map<String, List<String>> groups = new LinkedHashMap<>();
3    for (String w : words) {
4        char[] cs = w.toCharArray(); Arrays.sort(cs);
5        groups.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);   // anagrams share the sorted key
6    }
7    return new ArrayList<>(groups.values());
8}

1static List<List<String>> groupAnagrams(String[] words) {
2    Map<String, List<String>> groups = new LinkedHashMap<>();
3    for (String w : words) {
4        char[] cs = w.toCharArray(); Arrays.sort(cs);
5        groups.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);   // anagrams share the sorted key
6    }
7    return new ArrayList<>(groups.values());
8}

To find the first element that appears exactly once, count everything in a first pass, then scan the array again in order and return the first index whose count is 1. Two passes are needed because you cannot know an element is unique until you have seen the whole array.

The array order, not the map order, decides which unique element comes first, which is why the second pass walks the array and not the map.

1static int firstUnique(int[] a) {
2    Map<Integer, Integer> count = new HashMap<>();
3    for (int x : a) count.merge(x, 1, Integer::sum);          // pass 1: count every value
4    for (int i = 0; i < a.length; i++)
5        if (count.get(a[i]) == 1) return i;                    // pass 2: first value with count 1
6    return -1;
7}

1static int firstUnique(int[] a) {
2    Map<Integer, Integer> count = new HashMap<>();
3    for (int x : a) count.merge(x, 1, Integer::sum);          // pass 1: count every value
4    for (int i = 0; i < a.length; i++)
5        if (count.get(a[i]) == 1) return i;                    // pass 2: first value with count 1
6    return -1;
7}

To detect a duplicate, remember what you have seen. Set.add returns false when the value was already present, so the check and the insertion happen in one expression. The scan stops at the first duplicate, so the work done is proportional to the position of that duplicate, not to n.

Alternatives: sorting first (O(n log n), no extra space beyond the sort) and, for values in a small range, a boolean array. The hash set is the O(n) general answer.

1static boolean containsDuplicate(int[] a) {
2    Set<Integer> seen = new HashSet<>();
3    for (int x : a)
4        if (!seen.add(x)) return true;      // add returns false when x was already in the set
5    return false;
6}

1static boolean containsDuplicate(int[] a) {
2    Set<Integer> seen = new HashSet<>();
3    for (int x : a)
4        if (!seen.add(x)) return true;      // add returns false when x was already in the set
5    return false;
6}

Count the contiguous subarrays whose sum is k. With prefix sums, the sum of a[i..j] is prefix[j+1] - prefix[i], so a subarray ending at j has sum k exactly when an earlier prefix equals current - k. Keep a map from prefix sum to how many times it has occurred, and add map[current - k] to the answer at every step.

Seed the map with {0: 1} so subarrays that start at index 0 are counted. This handles negative numbers and zeros, which break the sliding window technique. The animation marks every element that ends a matching subarray.

1static int countSubarraysWithSum(int[] a, int k) {
2    Map<Integer, Integer> seen = new HashMap<>();
3    seen.put(0, 1);                              // the empty prefix
4    int prefix = 0, count = 0;
5    for (int x : a) {
6        prefix += x;
7        count += seen.getOrDefault(prefix - k, 0);   // earlier prefixes that leave sum k
8        seen.merge(prefix, 1, Integer::sum);
9    }
10    return count;
11}