Find array elements with frequencies in range [l , r]

0 0 7 minutes read

Given an array of integers, find the elements from the array whose frequency lies in the range [l, r].

Examples:

Input : arr[] = { 1, 2, 3, 3, 2, 2, 5 }
        l = 2, r = 3
Output : 2 3 3 2 2

Approach :

Take a hash map, which will store the frequency of all the elements in the array.
Now, traverse once again.
Print the elements whose frequency lies between the range [l, r].

C++

// C++ program to find the elements whose
// frequency lies in the range [l, r]
#include "iostream"
#include "unordered_map"
using namespace std;
 
void findElements(int arr[], int n, int l, int r)
{
    // Hash map which will store the
    // frequency of the elements of the array.
    unordered_map<int, int> mp;
 
    for (int i = 0; i < n; ++i) {
 
        // Increment the frequency
        // of the element by 1.
        mp[arr[i]]++;
    }
 
    for (int i = 0; i < n; ++i) {
 
        // Print the element whose frequency
        // lies in the range [l, r]
        if (l <= mp[arr[i]] && mp[arr[i] <= r]) {
            cout << arr[i] << " ";
        }
    }
}
 
int main()
{
    int arr[] = { 1, 2, 3, 3, 2, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int l = 2, r = 3;
    findElements(arr, n, l, r);
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
 
// Java program to find the elements whose
// frequency lies in the range [l, r]
public class GFG {
 
    static void findElements(int arr[], int n, int l, int r) {
        // Hash map which will store the
        // frequency of the elements of the array.
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
 
        for (int i = 0; i < n; ++i) {
 
            // Increment the frequency
            // of the element by 1.
            int a=0;
            if(mp.get(arr[i])==null){
                a=1;
            }
            else{
                a = mp.get(arr[i])+1;
            }
            mp.put(arr[i], a);
        }
 
        for (int i = 0; i < n; ++i) {
 
            // Print the element whose frequency
            // lies in the range [l, r]
            if (l <= mp.get(arr[i]) && (mp.get(arr[i]) <= r)) {
                System.out.print(arr[i] + " ");
            }
        }
    }
 
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 3, 2, 2, 5};
        int n = arr.length;
        int l = 2, r = 3;
        findElements(arr, n, l, r);
 
    }
}
/*This code is contributed by PrinciRaj1992*/

Python3

# Python 3 program to find the elements whose
# frequency lies in the range [l, r]
 
def findElements(arr, n, l, r):
     
    # Hash map which will store the
    # frequency of the elements of the array.
    mp = {i:0 for i in range(len(arr))}
 
    for i in range(n):
         
        # Increment the frequency
        # of the element by 1.
        mp[arr[i]] += 1
 
    for i in range(n):
         
        # Print the element whose frequency
        # lies in the range [l, r]
        if (l <= mp[arr[i]] and mp[arr[i] <= r]):
            print(arr[i], end = " ")
     
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 3, 2, 2, 5]
    n = len(arr)
    l = 2
    r = 3
    findElements(arr, n, l, r)
     
# This code is contributed by
# Shashank_Sharma

C#

// C# program to find the elements whose
// frequency lies in the range [l, r]
using System;
using System.Collections.Generic;
 
class GFG 
{
 
    static void findElements(int []arr, int n, int l, int r)
    {
        // Hash map which will store the
        // frequency of the elements of the array.
        Dictionary<int, int> mp = new Dictionary<int, int>();
 
        for (int i = 0; i < n; ++i) 
        {
 
            // Increment the frequency
            // of the element by 1.
            int a = 0;
            if(!mp.ContainsKey(arr[i]))
            {
                a = 1;
            }
            else
            {
                a = mp[arr[i]]+1;
            }
             
            if(!mp.ContainsKey(arr[i]))
            {
                mp.Add(arr[i], a); 
            }
            else
            {
                mp.Remove(arr[i]);
                mp.Add(arr[i], a);
            }
        }
 
        for (int i = 0; i < n; ++i)
        {
 
            // Print the element whose frequency
            // lies in the range [l, r]
            if (mp.ContainsKey(arr[i]) && 
                        l <= mp[arr[i]] &&
                        (mp[arr[i]] <= r)) 
            {
                Console.Write(arr[i] + " ");
            }
        }
    }
     
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = {1, 2, 3, 3, 2, 2, 5};
        int n = arr.Length;
        int l = 2, r = 3;
        findElements(arr, n, l, r);
 
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to find the elements whose
// frequency lies in the range [l, r]
function findElements(arr, n, l, r) 
{
     
    // Hash map which will store the
    // frequency of the elements of the array.
    let mp = new Map();
 
    for(let i = 0; i < n; ++i) 
    {
         
        // Increment the frequency
        // of the element by 1.
        let a = 0;
        if (mp.get(arr[i]) == null)
        {
            a = 1;
        }
        else
        {
            a = mp.get(arr[i]) + 1;
        }
        mp.set(arr[i], a);
    }
 
    for(let i = 0; i < n; ++i) 
    {
         
        // Print the element whose frequency
        // lies in the range [l, r]
        if (l <= mp.get(arr[i]) && 
                (mp.get(arr[i]) <= r))
        {
            document.write(arr[i] + " ");
        }
    }
}
     
// Driver Code
let arr = [ 1, 2, 3, 3, 2, 2, 5 ];
let n = arr.length;
let l = 2, r = 3;
 
findElements(arr, n, l, r);
 
// This code is contributed by code_hunt
 
</script>

Output

2 3 3 2 2

Time Complexity: O(N)
Auxiliary space: O(N)

Efficient Approach( Space optimization): we can use binary search . First sort the whole array for binary search function and then find frequency of all array element . Then check if the frequency of array element lies in the range [L,R]. If lies , then print that element .

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print elements that frequency 
// lies in the range [L,R]
void findElements(int *arr, int n , int l , int r)
{   
    sort(arr,arr+n);//sort array for binary search
    
    for(int i = 0 ; i < n ;i++)
    { 
      //index of first and last occ of arr[i] using binary 
      //search Upper and lower bound function
      int first_index = lower_bound(arr,arr+n,arr[i])- arr;
      int last_index = upper_bound(arr,arr+n,arr[i])- arr-1;
       
      int fre = last_index-first_index+1;//finding frequency
       
      if(fre >= l and fre <=r)
      { //printing element if its frequency lies in the range [L,R]
        cout << arr[i] <<" ";
      }
    } 
}
 
// Drive code
int main()
{    
    int arr[] = { 1, 2, 3, 3, 2, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    int l = 2, r = 3;
     
    // Function call
    findElements( arr, n, l , r );
    return 0;
}
 
// This Approach is contributed by nikhilsainiofficial546

Java

// Java implementation of the above approach
 
import java.util.*;
 
public class FrequencyRange {
 
    // Function to print elements that frequency
    // lies in the range [L,R]
    static void findElements(int[] arr, int n, int l, int r)
    {
        Arrays.sort(arr);
        // sort array for binary search
 
        for (int i = 0; i < n; i++) {
            // index of first and last occ of arr[i] using
            // binary search Upper and lower bound function
            int first_index
                = Arrays.binarySearch(arr, arr[i]);
            int last_index
                = Arrays.binarySearch(arr, arr[i]);
 
            while (first_index > 0
                   && arr[first_index - 1] == arr[i]) {
                first_index--;
            }
 
            while (last_index < n - 1
                   && arr[last_index + 1] == arr[i]) {
                last_index++;
            }
 
            int fre = last_index - first_index + 1;
            // finding frequency
 
            if (fre >= l && fre <= r) {
                // printing element if its
                // frequency lies in the
                // range [L,R]
                System.out.print(arr[i] + " ");
            }
        }
    }
 
    // Driver's code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 3, 2, 2, 5 };
        int n = arr.length;
 
        int l = 2, r = 3;
 
        // Function call
        findElements(arr, n, l, r);
    }
}

Python3

import bisect
 
# Function to print elements whose frequency
# lies in the range [L,R]
 
def findElements(arr, n, l, r):
    arr.sort() # sort array for binary search
     
    for i in range(n):
         
        # index of first and last occ of arr[i] using binary 
        # search Upper and lower bound function
        first_index = bisect.bisect_left(arr, arr[i])
        last_index = bisect.bisect_right(arr, arr[i])
         
         
     
        fre = last_index - first_index   # finding frequency
         
 
        if fre >= l and fre <= r: # printing element if its frequency lies in the range [L,R]
            print(str(arr[i]), end = " ")
    print()
     
 
# Driver code
 
arr = [1, 2, 3, 3, 2, 2, 5]
n = len(arr)
l = 2
r = 3
# Function call
 
findElements(arr, n, l , r)

C#

using System;
 
class Program {
    static void findElements(int[] arr, int n, int l, int r) {
        Array.Sort(arr); // sort array for binary search
 
        for (int i = 0; i < n; i++) {
            // index of first and last occ of arr[i] using binary
            // search Upper and lower bound function
            int first_index = Array.BinarySearch(arr, arr[i]);
            while (first_index > 0 && arr[first_index - 1] == arr[i]) {
                first_index--;
            }
            int last_index = Array.BinarySearch(arr, arr[i]);
            while (last_index < n - 1 && arr[last_index + 1] == arr[i]) {
                last_index++;
            }
 
            int fre = last_index - first_index + 1; // finding frequency
 
            if (fre >= l && fre <= r) { // printing element if its frequency lies in the range [L,R]
                Console.Write(arr[i] + " ");
            }
        }
    }
 
    static void Main() {
        int[] arr = { 1, 2, 3, 3, 2, 2, 5 };
        int n = arr.Length;
 
        int l = 2, r = 3;
 
        // Function call
        findElements(arr, n, l, r);
    }
}

Javascript

// Function to print elements that frequency 
// lies in the range [L,R]
function findElements(arr, n, l, r) {   
  arr.sort(); // sort array for binary search
 
  for (let i = 0; i < n; i++) {
    // index of first and last occ of arr[i] using binary 
    // search Upper and lower bound function
    const first_index = arr.indexOf(arr[i]);
    const last_index = arr.lastIndexOf(arr[i]);
 
    const fre = last_index - first_index + 1; // finding frequency
 
    if (fre >= l && fre <= r) { // printing element if its frequency lies in the range [L,R]
      console.log(arr[i] + " ");
    }
  } 
}
 
// Drive code
const arr = [1, 2, 3, 3, 2, 2, 5];
const n = arr.length;
const l = 2;
const r = 3;
 
// Function call
findElements(arr, n, l , r);

Output

2 2 2 3 3

Time Complexity: O(N*Log₂N)
Auxiliary space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!