CodingGyan

Frequency of Each Element

easy Arrays

Problem

Print each different value and how often it appears, in the form value count, in ascending order of the value. Zero and negative values are allowed.

Constraints

  • 1 <= n <= 10^5

Examples

Input

6
3 1 3 0 1 3

Output

0 1
1 2
3 3

Solutions

Best approachTime O(n log n)Space O(n)

A map from value to count handles every integer, including 0 and negative numbers. Some solutions that mark visited values with 0 fail when the input contains a real 0.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process an array.
 * Input   : n, then n integers.
 * Output  : One line per value.
 * Approach: Count with a map.
 * Time    : O(n log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[] a) {
        // Step 1: A TreeMap keeps the keys sorted. Count each value.
        java.util.TreeMap<Integer, Integer> counts = new java.util.TreeMap<>();
        for (int value : a) {
            counts.merge(value, 1, Integer::sum);
        }

        // Step 2: Make one line for each different value. (A real 0 in the input is counted like every other value.)
        String[] output = new String[counts.size()];
        int index = 0;
        for (java.util.Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            output[index++] = entry.getKey() + " " + entry.getValue();
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(String.join("\n", solve(a)));
    }
}
Hints (1)
  1. Why is 0 a bad marker value?

Try these next