Frequencies of Array By Hashing Technique (Optimized Approach)

Java · DSA · Hashing

Counting frequencies by hashing — and where the array should live

A working int[] hash-array solution, traced against three inputs, plus the actual reason people move big arrays outside main(). Play with the bucket hasher below before you read a line of code.

🪣 The bucket hasher

Type an array — watch it drop into indexed buckets, live.

Array (space separated)

Queries (space separated)

Every value becomes an index. hash[value]++ drops a ball in that bucket — no comparisons, no searching, just direct addressing. That's the whole trick.

01 The working solution

This is a correct, minimal frequency counter. It sizes hash to n + 1, which works cleanly as long as every value fits within that range.

import java.util.Scanner;
public class FrequenciesByHashing {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] hash = new int[n + 1];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            hash[arr[i]]++;
        }
        int q = sc.nextInt();
        while (q != 0) {
            int num = sc.nextInt();
            if (num > 0 && num <= n) System.out.print(hash[num] + " ");
            else System.out.print(0 + " ");
            q--;
        }
    }
}

import java.util.Scanner;
public class FrequenciesByHashing {
    // declared OUTSIDE main — fixed size, decoupled from n
    static int[] hash = new int[(int) 1e7 + 1];
    // static boolean[] visited = new boolean[(int) 1e8 + 1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n]; // fine locally, size ~10^6 max
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            hash[arr[i]]++;
        }
        int q = sc.nextInt();
        while (q != 0) {
            int num = sc.nextInt();
            System.out.print((num >= 0 && num < hash.length ? hash[num] : 0) + " ");
            q--;
        }
    }
}

02 Traced test cases

Click through each one — the input, and the resulting output.

Array (n = 6)

6 5 4 2 1 6

Queries

6 4 8

Output

2 1 0

Array (n = 5)

1 2 3 4 5

Queries

1 3 5 2 4

Output

1 1 1 1 1

Array (n = 8)

2 2 2 3 3 5 5 5

Queries

2 3 5 1 8 4

Output

3 2 3 0 0 0

03 Why placement even matters

All Java arrays live on the heap — local or not — so this was never a stack-overflow question. The real reasons to lift big hash arrays out of main() and make them static:

1. Value range ≠ input size

The working example sizes hash as n + 1, which only holds up because query values are guaranteed ≤ n. The moment values can range up to 10⁶–10⁷ independent of n, you need a fixed-size array sized to the value range — naturally a static field with a constant size.

2. Memory footprint

Drag the slider — watch what a full-range hash array actually costs in memory, for int[] vs boolean[].

📦 Memory footprint at scale

Java boolean takes a full byte, not a bit — that's why it scales differently.

10⁵ Range: 10⁶ 10⁸

4.0 MB

int[range]

1.0 MB

boolean[range]

✓ Comfortably fine as a local array inside main().

3. Decoupling size from user input

A static array declared with a fixed constant (e.g. new int[(int) 1e7 + 1]) never depends on what the user types. That closes off an entire class of bugs where the array is sized off n but indexed by a value that can exceed it.

Array type	Range	Where to declare
int[]	≤ 10⁶	Inside main() is fine
int[]	> 10⁶ (up to ~10⁷)	Outside main(), as static
boolean[]	up to ~10⁸	Outside main(), as static

Reference notes on the "frequencies by hashing" pattern for Java-based DSA practice.