Frequency and counting

When values are integers in a small range [0, k), allocate int[] count = new int[k] and do count[x]++ for each value. Every update is O(1), the whole pass is O(n + k), and no hashing is involved.

The animation counts the values, tracks how many are distinct, and shows how many values occur more than once, all in the same pass. Counters that turn red have more than one occurrence.

1public static int[] frequency(int[] arr, int maxValue) {
2    int[] count = new int[maxValue + 1];
3    int distinct = 0, duplicated = 0;
4    for (int x : arr) {
5        if (count[x] == 0) distinct++;            // first time we see x
6        else if (count[x] == 1) duplicated++;     // second time: x is a duplicate
7        count[x]++;
8    }
9    return count;
10}

For large, negative or non-integer keys (strings, objects), use a HashMap<K, Integer>. merge(key, 1, Integer::sum) increments in one call, and getOrDefault(key, 0) reads a count safely.

Expected O(1) per update, O(n) per pass. Iteration order of a HashMap is unspecified; use TreeMap if you need keys in sorted order, or LinkedHashMap to keep first-seen order.

1Map<String, Integer> freq = new HashMap<>();
2for (String word : words) {
3    freq.merge(word, 1, Integer::sum);
4}
5int apples = freq.getOrDefault("apple", 0);
6
7// one-liner with streams
8Map<String, Long> counts = Arrays.stream(words)
9    .collect(Collectors.groupingBy(w -> w, Collectors.counting()));

A histogram is a frequency table drawn as bars. It answers questions such as “which value is most common?”, “how many values fall in each bucket?” and “what is the mode?”.

To bucket continuous data, map each value to a bucket index first, for example (score / 10) for scores 0-100, then count the bucket indices.

1static int mode(int[] arr, int maxValue) {
2    int[] count = new int[maxValue + 1];
3    for (int x : arr) count[x]++;
4    int best = 0;
5    for (int v = 1; v <= maxValue; v++) {
6        if (count[v] > count[best]) best = v;     // ties keep the smaller value
7    }
8    return best;
9}

For lowercase English letters, int[26] indexed by c - 'a' is the fastest counter. Two strings are anagrams exactly when their 26 counts match: increment for one string, decrement for the other, and check that everything is zero.

For general Unicode text, use a HashMap<Integer, Integer> over code points (str.codePoints()), because a char cannot represent every character.

1static boolean isAnagram(String s, String t) {
2    if (s.length() != t.length()) return false;
3    int[] count = new int[26];
4    for (int i = 0; i < s.length(); i++) {
5        count[s.charAt(i) - 'a']++;
6        count[t.charAt(i) - 'a']--;
7    }
8    for (int c : count) if (c != 0) return false;
9    return true;
10}

The number of distinct elements is the number of non-zero counters, or simply the size of a HashSet built from the values. Increment a distinct counter the first time a value's count goes from 0 to 1.

Arrays.stream(arr).distinct().count() does the same with a hash set internally. Sorting and counting value changes works too, in O(n log n) with O(1) extra space.

1static int countDistinct(int[] arr) {
2    Set<Integer> seen = new HashSet<>();
3    for (int x : arr) seen.add(x);
4    return seen.size();
5}

A value is duplicated when its count reaches 2. Detecting that moment (the count goes from 1 to 2) counts each duplicated value once, no matter how many copies it has. Counting every extra copy instead gives n - distinct.

To return early on the first duplicate, Set.add returns false when the value is already present.

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