Highest Element Occuring Approaches

DSA · Hashing · Interactive

Finding the Most Frequent Element: From O(N²) to O(N)

Three ways to solve a classic hashing warm-up, a bug that's easy to miss, and a complexity analysis that's often done wrongly. You can run every example on your own input.

September 28, 2026 · 8 min read

• Playground
• Brute force
• Array hashing
• The bug
• Complexity
• HashMap
• Quiz

The problem

Given an array of N integers, print the element that appears most often. For [1, 3, 2, 3, 1, 3] the answer is 3, which appears 3 times.

Try it below. Type any array, or pick one of the presets. Some presets are chosen to break one of the approaches.

Playground

Approach 1: Brute force

For every element, count how many times it appears by scanning the whole array again. Keep the element with the highest count.

HighestFrequencyElement.java

import java.util.Scanner;

public class HighestFrequencyElement {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int maxCount = 0;
        int element = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == arr[i]) {
                    count++;
                }
            }
            // compare once per element, after counting is done
            if (count > maxCount) {
                maxCount = count;
                element = arr[i];
            }
        }
        System.out.println(element);
    }
}

Time O(N²) Extra space O(1)

The inner loop runs N times for each of the N outer iterations. Nested loops multiply, so it is O(N) × O(N), not O(N) + O(N). Apart from the input array, it uses only a few variables.

Put the maxCount check after the inner loop, not inside it. Inside, the answer is still correct, but the comparison runs N² times instead of N.

Approach 2: Array hashing

Instead of recounting, count every value once. Use an array hash where hash[v] stores how many times v appears. Its size must be max + 1, where max is the largest value in the input. Then scan hash for the biggest count.

Step through it

Press Play or Step to begin.

Speed

Counting Scanning Current best

Uses the playground array. Values from 0 to 40 are shown.

HighestFrequencyElementByHashingPreCompute.java

import java.util.Scanner;

public class HighestFrequencyElementByHashingPreCompute {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            max = Math.max(max, arr[i]);
        }

        // precompute: one pass to count every value
        int[] hash = new int[max + 1];
        for (int i = 0; i < n; i++) {
            hash[arr[i]]++;
        }

        // scan the HASH array, not the input array
        int maxCount = 0;
        int element = 0;
        for (int i = 0; i <= max; i++) {
            if (hash[i] > maxCount) {
                maxCount = hash[i];
                element = i;
            }
        }
        System.out.println(element);
    }
}

The bug: looping over the wrong array

A common first draft scans the counts with for (int i = 0; i < arr.length; i++). That loop runs N times, but it indexes hash, which has max + 1 slots. The two sizes are unrelated, so the code can fail in either direction. Switch between the two versions to see what each one does with the playground array.

Buggy vs fixed

Rule of thumb: the loop bound should match the array you index.

Complexity of array hashing

Time O(N + max) Extra space O(max)

The three loops run one after another, so their costs add: O(N) to read input and find max, O(N) to fill hash, and O(max) to scan it. When max is at most around N, that is effectively O(N).

The space is O(max), not O(1). The hash array grows with the largest value, not with N. Move the sliders to see how quickly that matters.

Scaling explorer

N (elements)

Largest value

Bar lengths use a log scale. Time estimates assume about 10⁸ simple operations per second, which is a rough rule of thumb for judges.

• With max = 10⁹, the counts array needs about 4 GB, even for a 5-element input.
• A negative value crashes on hash[arr[i]], because array indices cannot be negative.

Approach 3: HashMap for any values

A HashMap stores counts only for values that actually appear. That makes it work for huge values and negatives too.

HighestFrequencyElementByHashMap.java

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

public class HighestFrequencyElementByHashMap {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        int maxCount = 0;
        int element = 0;
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            if (e.getValue() > maxCount) {
                maxCount = e.getValue();
                element = e.getKey();
            }
        }
        System.out.println(element);
    }
}

Time O(N) average Extra space O(N)

Each map operation is O(1) on average, so the whole thing is O(N). In the worst case, when every element is distinct, the map holds N entries.

HashMap iteration order is not guaranteed. If several values tie for the highest count, which one is printed may vary. To always print the smallest tied value, add || (e.getValue() == maxCount && e.getKey() < element) to the condition.

Which approach to use

Approach	Time	Extra space	Negatives / huge values
Brute force	O(N²)	O(1)	Yes
Array hashing	O(N + max)	O(max)	No
HashMap	O(N) avg	O(N)	Yes

Use array hashing when values are small and non-negative, such as ages or marks out of 100. Otherwise use a HashMap.

Check yourself

Thanks for reading. When analysing complexity, remember three things: nested loops multiply, loops in sequence add, and a counts array sized by value costs space.