DSA 450 Notes

Problem Statement

Given an array of size n and a number k, find all elements that appear more than n/k times in the array.

Example:

Input: arr = [3, 1, 2, 2, 1, 2, 3, 3], k = 4
Output: [2, 3]
Explanation: n = 8, n/k = 2. Elements 2 and 3 appear 3 times each, which is more than 2.

Approach 1: Brute Force

Intuition

For each unique element, count its occurrences and check if it exceeds n/k.

Algorithm

For each element in the array
Count its total occurrences
If count > n/k, add to result (if not already added)

java

import java.util.*;

public class Solution {
    public List<Integer> findElements(int[] arr, int k) {
        int n = arr.length;
        int threshold = n / k;
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            // Skip if already processed
            boolean alreadyProcessed = false;
            for (int j = 0; j < i; j++) {
                if (arr[j] == arr[i]) {
                    alreadyProcessed = true;
                    break;
                }
            }
            if (alreadyProcessed) continue;
            
            // Count occurrences
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == arr[i]) {
                    count++;
                }
            }
            
            if (count > threshold) {
                result.add(arr[i]);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²) - For each element, we traverse the entire array
Space Complexity: O(1) - Only using result array (not counting output)

Approach 2: Optimal - Boyer-Moore Voting Algorithm Extension

Intuition

Extend Boyer-Moore voting algorithm. Since we need elements appearing more than n/k times, there can be at most k-1 such elements. We maintain k-1 candidates and their counts.

Algorithm

Maintain at most k-1 potential candidates with their counts
First pass: Find potential candidates
Second pass: Verify actual counts of candidates

java

import java.util.*;

public class Solution {
    public List<Integer> findElements(int[] arr, int k) {
        int n = arr.length;
        int threshold = n / k;
        Map<Integer, Integer> candidates = new HashMap<>();
        
        // First pass: Find potential candidates
        for (int num : arr) {
            if (candidates.containsKey(num)) {
                candidates.put(num, candidates.get(num) + 1);
            } else if (candidates.size() < k - 1) {
                candidates.put(num, 1);
            } else {
                // Decrease all counts
                List<Integer> toRemove = new ArrayList<>();
                for (Map.Entry<Integer, Integer> entry : candidates.entrySet()) {
                    entry.setValue(entry.getValue() - 1);
                    if (entry.getValue() == 0) {
                        toRemove.add(entry.getKey());
                    }
                }
                for (int key : toRemove) {
                    candidates.remove(key);
                }
            }
        }
        
        // Second pass: Verify counts
        for (int key : candidates.keySet()) {
            candidates.put(key, 0);
        }
        
        for (int num : arr) {
            if (candidates.containsKey(num)) {
                candidates.put(num, candidates.get(num) + 1);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : candidates.entrySet()) {
            if (entry.getValue() > threshold) {
                result.add(entry.getKey());
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n * k) - Two passes through array, each operation on candidates takes O(k)
Space Complexity: O(k) - At most k-1 candidates stored

Key Takeaways

Boyer-Moore Extension - The voting algorithm can be extended for finding elements appearing more than n/k times
At most k-1 candidates - There can be at most k-1 elements appearing more than n/k times
Two-pass verification - First pass finds candidates, second pass verifies counts
HashMap alternative - Using a HashMap with count tracking achieves O(n) time with O(n) space