Sum of Min/Max Frequencies of the Arrays - Brute Force & Optimized Approaches

Java · DSA · Hashing

Add the lowest and highest frequency in an array. Solve it two ways, brute force and hashing, then watch both run step by step on your own input.

• 01Problem
• 02Brute force
• 03Hashing
• 04Tracer
• 05Comparison
• 06Revision
• 07Quiz

01 The problem

Given an array of N non-negative integers, find how often each value occurs. Print the minimum frequency + maximum frequency.

For [1, 2, 2, 3, 3, 3, 3], the frequencies are 1 → 1, 2 → 2 and 3 → 4. The lowest is 1 and the highest is 4, so the answer is 1 + 4 = 5.

Type an array to run both programs and see every frequency.

Array (spaces or commas)

02 Approach 1: Brute force

Walk the array with i. The first time a value appears, mark it in visited and count it with an inner j loop. Then update minFreq and maxFreq with that count.

import java.util.Scanner;

public class SumOfMinMaxFrequenciesBruteForce {
    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]);
        }
        int visited[] = new int[max + 1];
        int minFreq = Integer.MAX_VALUE;
        int maxFreq = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            if (visited[arr[i]] == 0) {
                visited[arr[i]] = 1;
                for (int j = 0; j < n; j++) {
                    if (arr[i] == arr[j]) {
                        count++;
                    }
                }
                minFreq = Math.min(minFreq, count);
                maxFreq = Math.max(maxFreq, count);
            }
        }
        System.out.println(minFreq + maxFreq);
    }
}

1

visited[] skips repeats

Each distinct value runs the inner loop only once, on its first appearance.

2

Start at the extremes

minFreq starts at MAX_VALUE and maxFreq at MIN_VALUE, so the first real count replaces both.

03 Approach 2: Hashing

Count every value in one pass with hash[arr[i]]++. Then scan hash from 0 to max, skip the zeros, and track the smallest and largest count. There's no inner loop.

import java.util.Scanner;

public class SumOfMinMaxFrequenciesByHashing {
    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]);
        }
        int minFreq = Integer.MAX_VALUE;
        int maxFreq = Integer.MIN_VALUE;
        int hash[] = new int[max + 1];
        for (int i = 0; i < n; i++) {
            hash[arr[i]]++;
        }
        for (int i=0;i<=max;i++){
            if(hash[i]!=0){
                minFreq = Math.min(minFreq, hash[i]);
                maxFreq = Math.max(maxFreq, hash[i]);
            }
        }
        System.out.println(minFreq + maxFreq);
    }
}

1

One pass to count

hash[v] holds how many times v appears, for every value at once.

2

Scan hash with i <= max

hash has max + 1 slots, so the last index is max. Skip zeros, because those values never appeared.

04 Live tracer

Pick an approach and step through it. Both use the same input, so you can compare how many steps each one takes.

🎬 Frequency tracer

Array (up to 10 values, 0–20)

i

j

arr[]

visited[]

phase = –

i = –

j = –

count = –

steps = 0

minFreq

MAX

Integer.MAX_VALUE

maxFreq

MIN

Integer.MIN_VALUE

Load an array, then press Step ▶ to begin.

0 / 00%

Program printed–

Frequencies–

Steps taken–

Speed

#	Phase	i	j	Action	minFreq	maxFreq

05 Brute force vs hashing

Let D be the number of distinct values. Brute force runs its inner loop once per distinct value, so it makes D × N comparisons. Hashing touches each element once to count, then scans max + 1 slots.

	Brute force	Hashing
Counting	Inner loop per distinct value	hash[arr[i]]++, one pass
Time	O(D × N + max), worst case O(N²)	O(N + max)
Extra space	O(max) for visited	O(max) for hash
Best when	Very few distinct values	Values are small, non-negative integers

Try [0 0 0 1 1 2] in the tracer: brute force makes 3 × 6 = 18 comparisons, while hashing makes 6 counts and 3 scans. Both need non-negative values, because the value is used as an array index. For negative or huge values, a HashMap<Integer, Integer> does the same job in O(N) average time.

06 Quick revision

1

Answer = min + max frequency

Find every frequency, then add the smallest and the largest.

2

Initialise to the opposite extreme

minFreq = MAX_VALUE, maxFreq = MIN_VALUE.

3

Brute force: count once per value

visited[] stops a repeated value from being counted again.

4

Hashing: count, then scan

Fill hash in one pass, then read hash[i] for i = 0 … max.

5

Skip zero counts

A zero in hash means that value never appeared, so it isn't a frequency.

6

One value counts twice

For [4 4 4 4], min = max = 4, so the answer is 8.

07 Check yourself

Interactive reference for the "sum of min and max frequencies" pattern in Java-based DSA practice.