Least Frequent Element in an Array

Problem Understanding

The least frequent element in an array is the item that occurs the fewest number of times. Consider the array below:

int arr[] = {1, 2, 3, 2, 4, 1, 5, 3, 6, 2, 7, 1};

In this array, the least frequent element is 4, as it only appears once. The task is to write a program that efficiently identifies and returns this least frequent element.

Algorithms

Brute Force Approach:

• Iterate through the array.
• For each element, count its occurrences in this array.
• Track the element with the minimum frequency.
• Return the least frequent element.

Sorting:

• Sort the array.
• Iterate through the sorted array and count the occurrences of each element.
• Find the element with the minimum frequency.

Hashing:

• Use a hash table to store the frequency of each element.
• Iterate through the array to build the frequency table.
• Find the element with the minimum frequency.

Code Implementation

Brute Force Approach:

#include <iostream>
#include <unordered_map>

int leastFrequentBF(int arr[], int n) {
    int minFrequency = n + 1; // Initialize with a value greater than the array size
    int leastFrequentElement = -1;

    for (int i = 0; i < n; ++i) {
        int currentElement = arr[i];
        int frequency = 0;

        for (int j = 0; j < n; ++j) {
            if (arr[j] == currentElement) {
                ++frequency;
            }
        }

        if (frequency < minFrequency) {
            minFrequency = frequency;
            leastFrequentElement = currentElement;
        }
    }

    return leastFrequentElement;
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 1, 5, 3, 6, 2, 7, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Least frequent element (Brute Force): " << leastFrequentBF(arr, n) << std::endl;

    return 0;
}

Sorting Approach:

#include <iostream>
#include <algorithm>

int leastFrequentSorting(int arr[], int n) {
    // Sort the array
    std::sort(arr, arr + n);

    int minFrequency = n + 1; // Initialize with a value greater than the array size
    int leastFrequentElement = -1;

    int currentElement, frequency;

    // Iterate through the sorted array and count occurrences
    for (int i = 0; i < n;) {
        currentElement = arr[i];
        frequency = 0;

        while (i < n && arr[i] == currentElement) {
            ++frequency;
            ++i;
        }

        if (frequency < minFrequency) {
            minFrequency = frequency;
            leastFrequentElement = currentElement;
        }
    }

    return leastFrequentElement;
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 1, 5, 3, 6, 2, 7, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Least frequent element (Sorting): " << leastFrequentSorting(arr, n) << std::endl;

    return 0;
}

Hashing Approach:

#include <iostream>
#include <unordered_map>

int leastFrequentHashing(int arr[], int n) {
    std::unordered_map<int, int> frequencyMap;

    // Count the frequency of each element
    for (int i = 0; i < n; ++i) {
        frequencyMap[arr[i]]++;
    }

    int minFrequency = n + 1; // Initialize with a value greater than the array size
    int leastFrequentElement = -1;

    // Find the element with the minimum frequency
    for (const auto& entry : frequencyMap) {
        if (entry.second < minFrequency) {
            minFrequency = entry.second;
            leastFrequentElement = entry.first;
        }
    }

    return leastFrequentElement;
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 1, 5, 3, 6, 2, 7, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Least frequent element (Hashing): " << leastFrequentHashing(arr, n) << std::endl;

    return 0;
}

Complexity Analysis

Brute Force Approach

• Time Complexity: O(n^2) - The nested loops result in a time complexity of O(n^2), where n is the size of the array.
• Space Complexity: O(1) - The brute force approach uses a constant amount of extra space, regardless of the input size.

Sorting Approach:

• Time Complexity: O(n log n) - The dominant factor here is the sorting operation, which has a time complexity of O(n log n) using standard sorting algorithms.
• Space Complexity: O(1) - The sorting approach typically doesn't require additional space proportional to the input size.

Hashing Approach:

• Time Complexity: O(n) - The time complexity is O(n) as we iterate through the array once to build the frequency map using a hash table (unordered_map).
• Space Complexity: O(k) - The space complexity is O(k), where k is the numer of distinct elements in the array. In the worst case, when all elements are distinct, it approaches O(n), but in scenarios with a limited range of elements, k would be smaller.