easyArray ProblemsJava

Count the Frequency of Each Element in an Array

Count how many times each distinct value appears in an array using a map.

Quick Answer

Use a map from value to count. Walk the array once and, for each element, increment its count in the map with getOrDefault(element, 0) + 1. When the loop ends, every distinct value maps to the number of times it appeared. This is O(n) time using O(k) space for k distinct values.

Problem Statement

Given an array of integers, count how many times each distinct value appears. The result is a mapping from each value to its frequency.

Return (or print) the frequencies. A hash map keyed by the value, with the running count as the mapped value, does this in a single pass.

Input: An array arr of length n.

Output: A mapping of each distinct value to its number of occurrences.

Examples

Example 1
Input:  [1, 2, 2, 3, 3, 3]
Output: {1=1, 2=2, 3=3}

1 appears once, 2 appears twice, and 3 appears three times.

Example 2
Input:  [5, 5, 5, 5]
Output: {5=4}

The only distinct value 5 occurs four times.

Constraints

  • 0 <= n <= 10^6
  • Elements may be negative, zero, or repeated

Think Before You Code

Reveal the questions to ask yourself first
  • What structure lets you look up and update a value's running count quickly?
  • What should the count be the first time you see a value?
  • How would you present the counts in a predictable order?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
You need to associate each value with a count you can increment.
Hint 2
A `Map<Integer, Integer>` keyed by the element works; `getOrDefault(x, 0)` handles first sightings.
Hint 3
For each element do `map.put(x, map.getOrDefault(x, 0) + 1)`. A `TreeMap` prints the keys in sorted order.

Approach

Reveal the step-by-step approach

Tally occurrences into a map in one pass.

  1. Create a Map<Integer, Integer> (a TreeMap if you want sorted-key output).
  2. For each element x, do map.put(x, map.getOrDefault(x, 0) + 1).
  3. After the loop, each key maps to its frequency — return or print the map.

getOrDefault(x, 0) returns 0 the first time a value appears, so the very first increment stores a count of 1 without any special-casing.

Dry Run

Walk through the example step by step

Counting [1, 2, 2, 3, 3, 3] with a TreeMap:

element | getOrDefault + 1 | map
--------+------------------+-----------------
1       | 0 + 1            | {1=1}
2       | 0 + 1            | {1=1, 2=1}
2       | 1 + 1            | {1=1, 2=2}
3       | 0 + 1            | {1=1, 2=2, 3=1}
3       | 1 + 1            | {1=1, 2=2, 3=2}
3       | 2 + 1            | {1=1, 2=2, 3=3}
------------------------ result {1=1, 2=2, 3=3}

Solution

Reveal the full Java solution
import java.util.Map;
import java.util.TreeMap;

public class ElementFrequency {
    public static Map<Integer, Integer> frequency(int[] arr) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int x : arr) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        return map;
    }

    public static void main(String[] args) {
        System.out.println(frequency(new int[]{1, 2, 2, 3, 3, 3})); // {1=1, 2=2, 3=3}
        System.out.println(frequency(new int[]{5, 5, 5, 5}));       // {5=4}
    }
}

Each element is looked up and incremented in the map in average O(1), so the whole count is a single O(n) pass. getOrDefault(x, 0) cleanly handles the first appearance of a value by treating a missing key as count 0. A TreeMap keeps the keys sorted so the printed output is deterministic; a HashMap would be faster but unordered.

Time: O(n log k) with a TreeMap (O(n) average with a HashMap), where k is the distinct countSpace: O(k) for k distinct values

Common Mistakes

  • Calling `map.get(x) + 1` on a first sighting, which throws a NullPointerException on the null value.
  • Using a `HashMap` and then expecting the printed order to be sorted or stable.
  • Comparing every pair of elements in nested loops, which is O(n^2).

Edge Cases to Test

  • Empty array [] returns an empty map.
  • All elements distinct, so every value maps to 1.
  • Negative values and zero, which are valid map keys.

Interview Follow-Ups

  • How would you find the element with the highest frequency from this map?
  • How would you print the entries sorted by frequency instead of by key?
  • How would you use `merge` instead of `getOrDefault` to update counts?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us