Given an array of n non-negative integers. The task is to find frequency of a particular element in the arbitrary range of array[]. The range is given as positions (not 0 based indexes) in array. There can be multiple queries of given type.
Examples:
Input : arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
left = 2, right = 8, element = 8
left = 2, right = 5, element = 6
Output : 3
1
The element 8 appears 3 times in arr[left-1..right-1]
The element 6 appears 1 time in arr[left-1..right-1]
Naive approach: is to traverse from left to right and update count variable whenever we find the element.
Below is the code of Naive approach:-
PHP
<?php // PHP program to find total count of // an element in a range // Returns count of element in // arr[left-1..right-1] function findFrequency(&$arr, $n, $left, $right, $element) { $count = 0; for ($i = $left - 1; $i <= $right; ++$i) if ($arr[$i] == $element) ++$count; return $count; } // Driver Code $arr = array(2, 8, 6, 9, 8, 6, 8, 2, 11); $n = sizeof($arr); // Print frequency of 2 from position 1 to 6 echo "Frequency of 2 from 1 to 6 = ". findFrequency($arr, $n, 1, 6, 2) ." "; // Print frequency of 8 from position 4 to 9 echo "Frequency of 8 from 4 to 9 = ". findFrequency($arr, $n, 4, 9, 8); // This code is contributed by ita_c ?> |
Output:
Frequency of 2 from 1 to 6 = 1 Frequency of 8 from 4 to 9 = 2
Time complexity of this approach is O(right – left + 1) or O(n)
Auxiliary space: O(1)
Please refer complete article on Range Queries for Frequencies of array elements for more details!
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
