☕ DSA Java Articles

Topics › Basics › Learn Basic Hashing

Highest Occurring Element in an Array

Easy TUF ID 344 A2Z

Java source ↗ Edit this article ↗

Problem

Given a non-empty array of N integers, return the element that occurs the most times. If several elements share the highest frequency, return the smallest of them.

The problem is “count frequencies, then take a maximum”. The counting part is the basic hashing pattern; the new ingredient is the tie-break rule, which is easy to get wrong in every approach and is where most of the discussion below goes.

Constraints: 1 ≤ N ≤ 10^5, values fit in a 32-bit signed integer and may be negative.

Example 1

arr = [1, 2, 2, 3, 3, 3]
answer = 3                // 3 occurs three times, more than any other value

Example 2

arr = [1, 1, 2, 2]
answer = 1                // 1 and 2 both occur twice; the smaller one wins

Example 3

arr = [4, 4, -1, -1, -1]
answer = -1               // negative values are ordinary values

Approach 1: Brute force

Intuition. For each element, count how many times it appears by scanning the whole array, and keep the best candidate seen so far. A candidate replaces the current best if it has a strictly larger count, or the same count and a smaller value. Starting with bestCount = 0 guarantees the first element (count at least 1) becomes the initial best.

Algorithm.

  1. Set best = arr[0], bestCount = 0.
  2. For each index i: count occurrences of arr[i] in the whole array.
  3. If count > bestCount, or count == bestCount and arr[i] < best, update best and bestCount.
  4. Return best.
static int bruteForce(int[] arr) {
    int n = arr.length;
    int best = arr[0], bestCount = 0;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) if (arr[j] == arr[i]) count++;
        if (count > bestCount || (count == bestCount && arr[i] < best)) {
            best = arr[i];
            bestCount = count;
        }
    }
    return best;
}

Complexity. Time O(n^2): every element triggers a full scan. Space O(1).

For n = 10^5 that is 10^10 comparisons, so we need the counting to be cheaper.

Approach 2: Better, sort and measure runs

Intuition. After sorting, equal values are adjacent, so the frequency of a value is the length of its run of consecutive equal entries. Walk the sorted array with two indices: i marks the start of a run and j advances until the value changes; j - i is the count. Because the runs are visited in increasing order of value, the first run that achieves the maximum count is also the smallest such value, so a strict > when updating the best automatically implements the tie-break. We sort a copy so the input is not reordered.

Algorithm.

  1. Copy and sort the array.
  2. Set best = a[0], bestCount = 0, i = 0.
  3. While i < n: move j forward while a[j] == a[i]; let count = j - i.
  4. If count > bestCount, set best = a[i], bestCount = count. Then set i = j.
  5. Return best.
static int better(int[] arr) {
    int[] a = arr.clone();
    Arrays.sort(a);
    int best = a[0], bestCount = 0;
    int i = 0;
    while (i < a.length) {
        int j = i;
        while (j < a.length && a[j] == a[i]) j++;         // a[i..j-1] is one run of equal values
        int count = j - i;
        if (count > bestCount) {                          // strict >, so an earlier (smaller) value keeps a tie
            best = a[i];
            bestCount = count;
        }
        i = j;
    }
    return best;
}

Complexity. Time O(n log n) for the sort; the run scan is O(n). Space O(n) for the sorted copy (O(1) if sorting in place is allowed).

This is also the right approach when you are not allowed extra hashing structures, or when you additionally need the answer for every frequency in sorted order.

Approach 3: Optimal, hash map

Intuition. Count every value in one pass with a HashMap<Integer, Integer>; then one pass over the map’s entries finds the entry with the largest count. The map’s iteration order is arbitrary, so unlike the sorted approach we cannot rely on seeing smaller values first, and the update rule must spell out the tie-break explicitly: replace the best on a strictly larger count, or on an equal count with a smaller value.

Algorithm.

  1. For each v in arr, freq.merge(v, 1, Integer::sum).
  2. Set best = arr[0], bestCount = 0.
  3. For each entry (value, count): if count > bestCount, or count == bestCount and value < best, update.
  4. Return best.
static int optimal(int[] arr) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int v : arr) freq.merge(v, 1, Integer::sum);
    int best = arr[0], bestCount = 0;
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        int value = e.getKey(), count = e.getValue();
        if (count > bestCount || (count == bestCount && value < best)) {
            best = value;
            bestCount = count;
        }
    }
    return best;
}

Dry run on arr = [1, 2, 2, 3, 3, 3]. After counting, freq = {1: 1, 2: 2, 3: 3}. Suppose the map iterates in the order 2, 1, 3:

entry count > bestCount? tie and smaller? best, bestCount
start     1, 0
2 → 2 2 > 0, yes   2, 2
1 → 1 1 > 2, no 1 == 2, no 2, 2
3 → 3 3 > 2, yes   3, 3

Return 3. Any other iteration order gives the same result because the update rule is a total order on (count desc, value asc).

Complexity. Time O(n) on average: n map updates plus at most n entries to scan. Space O(d) for d distinct values.

If the values are known to be small non-negative integers (say at most 10^6), replace the map with an int[] counting array: same algorithm, no boxing, and the scan over the array in index order visits values smallest first, so the strict > tie-break of Approach 2 applies.

Edge cases and pitfalls