Javascript program for array element frequency range query

We get an array containing integers and another array containing queries, each query represents the range we give by the leftmost and rightmost index and one element in the array. For that range or subarray, we have to find the frequency of occurrence of a given element in that range.

The frequency of

elements means that we have to tell each integer present in the range how many times it occurs. For example -

If, the given array is: [5, 2, 5, 3, 1, 5, 2, 2, 5]

The query array is: [[0, 4, 5], [1, 7, 2]]

• For the first query, the subarrays are: 5, 2, 5, 3, 1, so the frequency of 5 is 2.

• For the second query, the subarrays are 2, 5, 3, 1, 5, 2, and 2, so the frequency of 2 is 3.

method

To resolve this issue we will follow the following steps -

• First, we will create a separate function to call each query and pass the query elements as parameters.

• Inside the function, we will get the length of the array to iterate and create a variable count to store the frequency of the given element.

• We will use a for loop to iterate over the given range and on each iteration, if the current array element is equal to the given element, we will increment the count.

• Finally, we will print the current count of the given element.

Example

Let’s see the correct code to implement the above steps for better understanding -

// function to answer their queries 
function findFre(arr, L, R, ele ){
   var n = arr.length 
   var count = 0
   // traversing over the array 
   for(var i = L; i <= R; i++){
      if(arr[i] == ele){
         count++;
      }
   }
   console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array 
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
   findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}

Time and space complexity

The time complexity of the above code is O(Q*N), where Q is the number of queries and N is the array size. The time complexity is a factor of N because for each query we iterate over the array within the given range.

The space complexity of the above code is O(1) because we are not using any extra space to store anything.

Special case

In the above code, we get the time complexity of O(Q*N). If the number of different elements present in a given array is less than the number of a separate array for each element, the space complexity can be calculated by to improve time complexity or maintain the mapping of prefix sums.

But this method consumes a lot of space, and its complexity is O(D*N), where D is the number of different elements present in the array and N is the length of the array.

By maintaining the prefix sum, the answer to any query can be given in O(1) time, and the overall time complexity will be O(Q), where Q is the number of queries.

Example

var store = null;
function lb(a, l, h, k){
   if (l > h){
      return l;
   }
   var m = l + parseInt((h - l) / 2);
   if (k <= a[m]) {
      return lb(a, l, m - 1, k);
   }
   return lb(a, m + 1, h, k);
}
function ub(a, l, h, k){
   if (l > h || l == a.length){
      return l;
   }
   var m = l + parseInt((h - l) / 2);
   if (k >= a[m]){
      return ub(a, m + 1, h, k);
   }
   return ub(a, l, m - 1, k);
}
function findFre(arr, L, R, ele){
   var n = arr.length
   var left_side = lb(store.get(ele), 0, store.get(ele).length, L);
   var right_side = ub(store.get(ele), 0, store.get(ele).length, R);
   var count = right_side - left_side;
   console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array 
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
// creating a map to store the elements 
store = new Map();
for (var i = 0; i < arr.length; i++){
   if (!store.has(arr[i])){
      store.set(arr[i],new Array());
   }
   store.get(arr[i]).push(i);
}
// creating map for the different elements
// defining queries array 
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
   findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}

in conclusion

In this tutorial, we implemented a JavaScript program to answer range queries to answer the frequency of a given element in the range provided in each query. We have iterated over the given range in the array and maintained a variable to get the count. The time complexity of the above code is O(Q*N), and the space complexity of the above code is O(1).

The above is the detailed content of Javascript program for array element frequency range query. For more information, please follow other related articles on the PHP Chinese website!