Count repeated numbers in an array

import java.util.*;
import java.util.stream.Collectors;

public class RepeatedNumbers {
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 3, 3, 4, 5, 5};

        System.out.println("Using Streams:");
        countRepeatedWithStreams(arr);

        System.out.println("\nWithout Using Streams:");
        countRepeatedWithoutStreams(arr);

        System.out.println("\nOptimized for Sorted Array:");
        countRepeatedInSortedArray(arr);
    }

    // 1. Using Java Streams
    // Approach: 
    // - Convert array to a stream of Integer values.
    // - Use groupingBy to calculate frequency of each number.
    // - Filter entries with a count greater than 1 (repeated numbers).
    // - Count the number of repeated numbers.
    // Time Complexity: O(n) - One pass for grouping, one for filtering.
    // Space Complexity: O(n) - Space required for the frequency map.
    private static void countRepeatedWithStreams(int[] arr) {
        Map<Integer, Long> frequencyMap = Arrays.stream(arr)
                .boxed()
                .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

        long repeatedCount = frequencyMap.values().stream()
                .filter(count -> count > 1)
                .count();

        System.out.println("Total repeated numbers: " + repeatedCount);
    }

    // 2. Without Using Streams
    // Approach: 
    // - Traverse the array and store frequencies in a HashMap.
    // - Iterate over the map and count entries with frequency > 1.
    // Time Complexity: O(n) - Two passes (one for map, one for counting).
    // Space Complexity: O(n) - Space required for the frequency map.
    private static void countRepeatedWithoutStreams(int[] arr) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        int repeatedCount = 0;
        for (int count : frequencyMap.values()) {
            if (count > 1) repeatedCount++;
        }

        System.out.println("Total repeated numbers: " + repeatedCount);
    }

    // 3. Optimized Approach (If Input is Sorted)
    // Approach:
    // - Use a two-pointer approach to find duplicate ranges.
    // - Increment the repeated count for every range with length > 1.
    // Time Complexity: O(n) - Single pass through the array.
    // Space Complexity: O(1) - No additional space required.
    private static void countRepeatedInSortedArray(int[] arr) {
        int repeatedCount = 0;
        int i = 0;

        while (i < arr.length) {
            int j = i;
            while (j < arr.length && arr[j] == arr[i]) {
                j++;
            }
            if (j - i > 1) repeatedCount++;  // Check if number repeats
            i = j; // Move to next unique number
        }

        System.out.println("Total repeated numbers: " + repeatedCount);
    }
}

/*
Output:
Using Streams:
Total repeated numbers: 3

Without Using Streams:
Total repeated numbers: 3

Optimized for Sorted Array:
Total repeated numbers: 3

Explanation:
- The program implements three different approaches to count how many numbers are repeated in an array.
- It handles both unsorted and sorted arrays efficiently.

Approach Summary:
1. Using Streams: Leverages Java Streams for functional-style processing.
2. Without Streams: Uses traditional iteration and a HashMap.
3. Optimized for Sorted Arrays: Uses a two-pointer technique with O(1) space.

Complexities:
1. Using Streams: O(n) time, O(n) space.
2. Without Streams: O(n) time, O(n) space.
3. Optimized for Sorted Array: O(n) time, O(1) space.
*/