How to use Map In Javascript

Using Sorting

In this approach, we will reduce the space complexity by using map data structure and traversing the array only once. We initialize an empty map to store frequency of each element of array. Now, we will iterate through array and check if element exist in the map, increment its count by 1. Now, iterate through map and print those element that appear more than n/k times.

Example: The below code implements JavaScript Map to find all elements that appear more than n/k times.

JavaScript

function findElements(arr, n, k) {
    let comp = Math.floor(n / k);
    let mp = new Map();
    for (let i = 0; i < n; i++) {
        if (mp.has(arr[i])) {
            mp.set(arr[i], mp.get(arr[i]) + 1);
        } else {
            mp.set(arr[i], 1);
        }
    }

    for (let [key, value] of mp) {
        if (value > comp) {
            console.log(key);
        }
    }
}

function main() {
    findElements([1, 4, 2, 4, 4], 5, 2);
    findElements([1, 1, 1, 1, 1], 5, 3);
}
main();

Output

4
1

Time Complexity : O(n), as we are traversing the array.

Space Complexity : O(n), as we are using map data structure.

JavaScript Program to Find all Elements that Appear More than n/k Times

We are given an array that has n number of elements and an integer k, we have to return all the elements which will appear more than n/k times in the array using JavaScript.

Examples:

Input: arr = {4, 2, 4, 1, 4, 5, 5, 5}, k=3
Output: {4 , 5}
Explanation: The elements {4, 5} appears more than n/k i.e. 8/3=2 times.

Input: arr = {1, 2, 1, 4, 1}, k=2
Output: {1}
Explanation: The element {1} appears 3 times which is greater than n/k i.e. 5/2=2 times.