Problem

Given an integer array arr of length n, return the frequency of each distinct element. Output the pairs in ascending order of the element value.

Input / Output

• Input: integer array arr.
• Output: list of (value, count) pairs sorted by value.

Examples

Example 1 Input: arr = [10, 5, 10, 15, 10, 5] Output: 5:2, 10:3, 15:1

Example 2 Input: arr = [1, 1, 1, 1] Output: 1:4

Constraints

• 1 <= n <= 10^5
• -10^9 <= arr[i] <= 10^9

Approach

Hash map (general case). Iterate the array and increment freq[arr[i]]. Then collect the keys, sort them, and print. O(n) to count plus O(k log k) to sort the k distinct keys.

Sorting (no extra map). Sort the array, then scan: whenever the value changes, emit the previous value and the run length. O(n log n) time, O(1) extra space if in-place sorting is allowed.

Counting array (bounded values). If the elements are known to lie in a small range [0, MAX], use cnt[MAX+1] for O(n + MAX) time — the fastest approach when it applies.

In-place trick (values 1..n). If every element lies in [1, n], you can store the counts inside the array itself: for each element v = arr[i] % (n+1) (original value), add n+1 to arr[v-1]. Afterwards arr[j] / (n+1) is the frequency of j+1. This is O(n) time and O(1) space and is a favourite follow-up question.

Complexity

• Hash map: O(n) average time, O(k) space.
• Sorting: O(n log n) time, O(1) extra space.

Related

Majority element, top-K frequent elements, first repeating element, and "count distinct elements in every window" all start from this counting step.

Reference solution (Python)

from collections import Counter

def element_frequencies(arr):
    c = Counter(arr)
    return sorted(c.items())

# O(1)-space variant when all values are in 1..n
def frequencies_in_place(arr):
    n = len(arr)
    for i in range(n):
        v = arr[i] % (n + 1)
        arr[v - 1] += n + 1
    return [(i + 1, arr[i] // (n + 1)) for i in range(n) if arr[i] // (n + 1)]

Test cases

Input	Expected
[10,5,10,15,10,5]	[(5,2),(10,3),(15,1)]
[1,1,1,1]	[(1,4)]
[3,1,2] (in-place variant)	[(1,1),(2,1),(3,1)]
[2,2,1] (in-place variant)	[(1,1),(2,2)]