Count number of smallest elements in given range
Given an array of N numbers and Q queries, each query consists of L and R. We need to write a program that prints the number of occurrence of the smallest element in the range L-R.
Examples:
Input: a[] = {1, 1, 2, 4, 3, 3}
Q = 2
L = 1 R = 4
L = 3 R = 6
Output: 2
1
Explanation: The smallest element in range 1-4
is 1 which occurs 2 times. The smallest element
in the range 3-6 is 2 which occurs once.
Input : a[] = {1, 2, 3, 3, 1}
Q = 2
L = 1 R = 5
L = 3 R = 4
Output : 2
2
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
A normal approach will be to iterate from L-R and find out the smallest element in the range. Iterate again in the range L-R and count the number of times the smallest element occurs in the range L-R. In the worst case, the complexity will be O(N) if L=1 and R=N.
An efficient approach will be to use Segment Trees to solve the above problem. At each node of the segment tree, smallest element and count of smallest element is stored. At leaf nodes, the array element is stored in the minimum and count stores 1. For all other nodes except the leaf nodes, we merge the right and left nodes following the given conditions:
- min(left_subtree) < min(right_subtree): node.min=min(left_subtree), node.count = left_subtree.count
- min(left_subtree) > min(right_subtree): node.min=min(right_subtree), node.count=right_subtree.count
- min(left_subtree) = min(right_subtree): node.min=min(left_subtree) or min(right_subtree), node.count=left_subtree.count + right_subtree.count
Given below is the implementation of the above approach:
C++
// CPP program to Count number of occurrence of // smallest element in range L-R #include <bits/stdc++.h> using namespace std; #define N 100005 // predefines the tree with nodes // storing min and count struct node { int min; int cnt; } tree[5 * N]; // function to construct the tree void buildtree( int low, int high, int pos, int a[]) { // base condition if (low == high) { // leaf node has a single element tree[pos].min = a[low]; tree[pos].cnt = 1; return ; } int mid = (low + high) >> 1; // left-subtree buildtree(low, mid, 2 * pos + 1, a); // right-subtree buildtree(mid + 1, high, 2 * pos + 2, a); // left subtree has the minimum element if (tree[2 * pos + 1].min < tree[2 * pos + 2].min) { tree[pos].min = tree[2 * pos + 1].min; tree[pos].cnt = tree[2 * pos + 1].cnt; } // right subtree has the minimum element else if (tree[2 * pos + 1].min > tree[2 * pos + 2].min) { tree[pos].min = tree[2 * pos + 2].min; tree[pos].cnt = tree[2 * pos + 2].cnt; } // both subtree has the same minimum element else { tree[pos].min = tree[2 * pos + 1].min; tree[pos].cnt = tree[2 * pos + 1].cnt + tree[2 * pos + 2].cnt; } } // function that answers every query node query( int s, int e, int low, int high, int pos) { node dummy; // out of range if (e < low or s > high) { dummy.min = dummy.cnt = INT_MAX; return dummy; } // in range if (s >= low and e <= high) { return tree[pos]; } int mid = (s + e) >> 1; // left-subtree node ans1 = query(s, mid, low, high, 2 * pos + 1); // right-subtree node ans2 = query(mid + 1, e, low, high, 2 * pos + 2); node ans; ans.min = min(ans1.min, ans2.min); // add count when min is same of both subtree if (ans1.min == ans2.min) ans.cnt = ans2.cnt + ans1.cnt; // store the minimal's count else if (ans1.min < ans2.min) ans.cnt = ans1.cnt; else ans.cnt = ans2.cnt; return ans; } // function to answer query in range l-r int answerQuery( int a[], int n, int l, int r) { // calls the function which returns a node // this function returns the count which // will be the answer return query(0, n - 1, l - 1, r - 1, 0).cnt; } // Driver Code int main() { int a[] = { 1, 1, 2, 4, 3, 3 }; int n = sizeof (a) / sizeof (a[0]); buildtree(0, n - 1, 0, a); int l = 1, r = 4; // answers 1-st query cout << answerQuery(a, n, l, r) << endl; l = 2, r = 6; // answers 2nd query cout << answerQuery(a, n, l, r) << endl; return 0; } |
Java
import java.util.*; public class SegmentTree { static final int MAX = 100005 ; static HashMap<Integer, Integer> map = new HashMap<>(); static Node[] tree = new Node[ 5 * MAX]; public static void main(String[] args) { int [] a = { 1 , 1 , 2 , 4 , 3 , 3 }; int n = a.length; buildtree( 0 , n - 1 , 0 , a); int l = 1 , r = 4 ; // answers 1-st query System.out.println(answerQuery(a, n, l, r)); l = 2 ; r = 6 ; // answers 2nd query System.out.println(answerQuery(a, n, l, r)); } // function to construct the tree static void buildtree( int low, int high, int pos, int [] a) { // base condition if (low == high) { // leaf node has a single element tree[pos] = new Node(a[low], 1 ); return ; } int mid = (low + high) / 2 ; // left-subtree buildtree(low, mid, 2 * pos + 1 , a); // right-subtree buildtree(mid + 1 , high, 2 * pos + 2 , a); // left subtree has the minimum element if (tree[ 2 * pos + 1 ].min < tree[ 2 * pos + 2 ].min) { tree[pos] = new Node(tree[ 2 * pos + 1 ].min, tree[ 2 * pos + 1 ].cnt); } // right subtree has the minimum element else if (tree[ 2 * pos + 1 ].min > tree[ 2 * pos + 2 ].min) { tree[pos] = new Node(tree[ 2 * pos + 2 ].min, tree[ 2 * pos + 2 ].cnt); } // both subtree has the same minimum element else { tree[pos] = new Node(tree[ 2 * pos + 1 ].min, tree[ 2 * pos + 1 ].cnt + tree[ 2 * pos + 2 ].cnt); } } // function that answers every query static Node query( int s, int e, int low, int high, int pos) { Node dummy = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE); // out of range if (e < low || s > high) { return dummy; } // in range if (s >= low && e <= high) { return tree[pos]; } int mid = (s + e) / 2 ; // left-subtree Node ans1 = query(s, mid, low, high, 2 * pos + 1 ); // right-subtree Node ans2 = query(mid + 1 , e, low, high, 2 * pos + 2 ); Node ans = new Node( 0 , 0 ); ans.min = Math.min(ans1.min, ans2.min); // add count when min is same of both subtree if (ans1.min == ans2.min) { ans.cnt = ans2.cnt + ans1.cnt; } // store the minimal's count else if (ans1.min < ans2.min) { ans.cnt = ans1.cnt; } // store the minimal's count else { ans.cnt = ans2.cnt; } return ans; } // helper function to answer each query static int answerQuery( int [] a, int n, int l, int r) { // initialize the map for ( int i = 0 ; i < n; i++) { map.put(a[i], i); } // find the minimum element in the given range Node ans = query( 0 , n - 1 , l - 1 , r - 1 , 0 ); // return the count of the minimum element in the // given range return ans.cnt; } // class to represent the node of the tree static class Node { int min; // minimum element int cnt; // count of the minimum element Node( int min, int cnt) { this .min = min; this .cnt = cnt; } } } |
Python3
# CPP program to Count number of occurrence of # smallest element in range L-R MAX = 100005 # defines the tree with nodes # storing min and count tree = [ None ] * ( 5 * MAX ) # function to construct the tree def buildtree(low, high, pos, a): # base condition if low = = high: # leaf node has a single element tree[pos] = { 'min' : a[low], 'cnt' : 1 } return mid = (low + high) / / 2 # left-subtree buildtree(low, mid, 2 * pos + 1 , a) # right-subtree buildtree(mid + 1 , high, 2 * pos + 2 , a) # left subtree has the minimum element if tree[ 2 * pos + 1 ][ 'min' ] < tree[ 2 * pos + 2 ][ 'min' ]: tree[pos] = { 'min' : tree[ 2 * pos + 1 ][ 'min' ], 'cnt' : tree[ 2 * pos + 1 ][ 'cnt' ]} # right subtree has the minimum element elif tree[ 2 * pos + 1 ][ 'min' ] > tree[ 2 * pos + 2 ][ 'min' ]: tree[pos] = { 'min' : tree[ 2 * pos + 2 ][ 'min' ], 'cnt' : tree[ 2 * pos + 2 ][ 'cnt' ]} # both subtree has the same minimum element else : tree[pos] = { 'min' : tree[ 2 * pos + 1 ][ 'min' ], 'cnt' : tree[ 2 * pos + 1 ][ 'cnt' ] + tree[ 2 * pos + 2 ][ 'cnt' ]} # function that answers every query def query(s, e, low, high, pos): dummy = { 'min' : float ( 'inf' ), 'cnt' : float ( 'inf' )} # out of range if e < low or s > high: return dummy # in range if s > = low and e < = high: return tree[pos] mid = (s + e) / / 2 # left-subtree ans1 = query(s, mid, low, high, 2 * pos + 1 ) # right-subtree ans2 = query(mid + 1 , e, low, high, 2 * pos + 2 ) ans = {} ans[ 'min' ] = min (ans1[ 'min' ], ans2[ 'min' ]) # add count when min is same of both subtree if ans1[ 'min' ] = = ans2[ 'min' ]: ans[ 'cnt' ] = ans2[ 'cnt' ] + ans1[ 'cnt' ] # store the minimal's count elif ans1[ 'min' ] < ans2[ 'min' ]: ans[ 'cnt' ] = ans1[ 'cnt' ] else : ans[ 'cnt' ] = ans2[ 'cnt' ] return ans # function to answer query in range l-r def answerQuery(a, n, l, r): # calls the function which returns a node # this function returns the count which # will be the answer return query( 0 , n - 1 , l - 1 , r - 1 , 0 )[ 'cnt' ] # Driver Code if __name__ = = '__main__' : a = [ 1 , 1 , 2 , 4 , 3 , 3 ] n = len (a) buildtree( 0 , n - 1 , 0 , a) l, r = 1 , 4 # answers 1-st query print (answerQuery(a, n, l, r)) l, r = 2 , 6 # answers 2nd query print (answerQuery(a, n, l, r)) |
C#
using System; using System.Collections.Generic; class Program { static readonly int MAX = 100005; static Dictionary< int , int > map = new Dictionary< int , int >(); static Node[] tree = new Node[5 * MAX]; static void Main() { int [] a = { 1, 1, 2, 4, 3, 3 }; int n = a.Length; BuildTree(0, n - 1, 0, a); int l = 1, r = 4; // Answer 1st query Console.WriteLine(AnswerQuery(a, n, l, r)); l = 2; r = 6; // Answer 2nd query Console.WriteLine(AnswerQuery(a, n, l, r)); } // Function to construct the tree static void BuildTree( int low, int high, int pos, int [] a) { // Base condition if (low == high) { // Leaf node has a single element tree[pos] = new Node(a[low], 1); return ; } int mid = (low + high) / 2; // Left-subtree BuildTree(low, mid, 2 * pos + 1, a); // Right-subtree BuildTree(mid + 1, high, 2 * pos + 2, a); // Left subtree has the minimum element if (tree[2 * pos + 1].min < tree[2 * pos + 2].min) { tree[pos] = new Node(tree[2 * pos + 1].min, tree[2 * pos + 1].cnt); } // Right subtree has the minimum element else if (tree[2 * pos + 1].min > tree[2 * pos + 2].min) { tree[pos] = new Node(tree[2 * pos + 2].min, tree[2 * pos + 2].cnt); } // Both subtrees have the same minimum element else { tree[pos] = new Node(tree[2 * pos + 1].min, tree[2 * pos + 1].cnt + tree[2 * pos + 2].cnt); } } // Function that answers every query static Node Query( int s, int e, int low, int high, int pos) { Node dummy = new Node( int .MaxValue, int .MaxValue); // Out of range if (e < low || s > high) { return dummy; } // In range if (s >= low && e <= high) { return tree[pos]; } int mid = (s + e) / 2; // Left-subtree Node ans1 = Query(s, mid, low, high, 2 * pos + 1); // Right-subtree Node ans2 = Query(mid + 1, e, low, high, 2 * pos + 2); Node ans = new Node(0, 0); ans.min = Math.Min(ans1.min, ans2.min); // Add count when min is the same in both subtrees if (ans1.min == ans2.min) { ans.cnt = ans2.cnt + ans1.cnt; } // Store the minimal's count else if (ans1.min < ans2.min) { ans.cnt = ans1.cnt; } // Store the minimal's count else { ans.cnt = ans2.cnt; } return ans; } // Helper function to answer each query static int AnswerQuery( int [] a, int n, int l, int r) { // Initialize the map for ( int i = 0; i < n; i++) { map[a[i]] = i; } // Find the minimum element in the given range Node ans = Query(0, n - 1, l - 1, r - 1, 0); // Return the count of the minimum element in the given range return ans.cnt; } // Class to represent the node of the tree class Node { public int min; // Minimum element public int cnt; // Count of the minimum element public Node( int min, int cnt) { this .min = min; this .cnt = cnt; } } } |
Javascript
const MAX = 100005; // defines the tree with nodes // storing min and count const tree = Array(5 * MAX).fill( null ); // function to construct the tree function buildtree(low, high, pos, a) { // base condition if (low == high) { // leaf node has a single element tree[pos] = {min: a[low], cnt: 1}; return ; } const mid = Math.floor((low + high) / 2); // left-subtree buildtree(low, mid, 2 * pos + 1, a); // right-subtree buildtree(mid + 1, high, 2 * pos + 2, a); // left subtree has the minimum element if (tree[2 * pos + 1].min < tree[2 * pos + 2].min) { tree[pos] = {min: tree[2 * pos + 1].min, cnt: tree[2 * pos + 1].cnt}; } // right subtree has the minimum element else if (tree[2 * pos + 1].min > tree[2 * pos + 2].min) { tree[pos] = {min: tree[2 * pos + 2].min, cnt: tree[2 * pos + 2].cnt}; } // both subtree has the same minimum element else { tree[pos] = {min: tree[2 * pos + 1].min, cnt: tree[2 * pos + 1].cnt + tree[2 * pos + 2].cnt}; } } // function that answers every query function query(s, e, low, high, pos) { const dummy = {min: Infinity, cnt: Infinity}; // out of range if (e < low || s > high) { return dummy; } // in range if (s >= low && e <= high) { return tree[pos]; } const mid = Math.floor((s + e) / 2); // left-subtree const ans1 = query(s, mid, low, high, 2 * pos + 1); // right-subtree const ans2 = query(mid + 1, e, low, high, 2 * pos + 2); const ans = {}; ans.min = Math.min(ans1.min, ans2.min); // add count when min is same of both subtree if (ans1.min === ans2.min) { ans.cnt = ans2.cnt + ans1.cnt; } // store the minimal's count else if (ans1.min < ans2.min) { ans.cnt = ans1.cnt; } else { ans.cnt = ans2.cnt; } return ans; } // function to answer query in range l-r function answerQuery(a, n, l, r) { // calls the function which returns a node // this function returns the count which // will be the answer return query(0, n - 1, l - 1, r - 1, 0).cnt; } // Driver Code const a = [1, 1, 2, 4, 3, 3]; const n = a.length; buildtree(0, n - 1, 0, a); let l = 1, r = 4; // answers 1-st query console.log(answerQuery(a, n, l, r)) l = 2; r = 6; // answers 2nd query console.log(answerQuery(a, n, l, r)) |
2 1
Time Complexity: O(n) for the construction of tree. O(log n) for every query.
Auxiliary Space: O(N) where N=100005
Approach:
In this approach, we first precompute the minimum and count arrays for the given array. The minimum array stores the minimum value seen so far from the left and right ends of the array, and the count array stores the count of the minimum value seen so far. We then answer each query by first finding the minimum value in the given range, and then iterating over the range again to count the occurrences of the minimum value using the count array.
Note that this approach has a time complexity of O(n) for preprocessing and O(q * k) for answering q queries, where k is the maximum range size in the queries. This is less efficient than the segment tree approach, which has a time complexity of O(n log n) for preprocessing and O(q log n) for answering q queries. However, this approach is simpler and easier to understand, and may be sufficient for small problem sizes or simpler applications.
C++
#include <bits/stdc++.h> using namespace std; const int N = 100005; int a[N], cnt[N]; // function to precompute the minimum and count arrays void preprocess( int n) { int min_val = INT_MAX; // iterate over the array from left to right for ( int i = 0; i < n; i++) { min_val = min(min_val, a[i]); cnt[i] = (min_val == a[i]) ? 1 : 0; } min_val = INT_MAX; // iterate over the array from right to left for ( int i = n - 1; i >= 0; i--) { min_val = min(min_val, a[i]); cnt[i] += (min_val == a[i]) ? 1 : 0; } } // function to answer query in range l-r int answerQuery( int n, int l, int r) { int min_val = INT_MAX, ans = 0; // iterate over the given range for ( int i = l - 1; i < r; i++) { min_val = min(min_val, a[i]); } // iterate over the given range again to count the occurrences for ( int i = l - 1; i < r; i++) { if (a[i] == min_val) { ans += cnt[i]; } } return ans; } // Driver Code int main() { int a[] = { 1, 1, 2, 4, 3, 3 }; int n = sizeof (a) / sizeof (a[0]); memcpy (::a, a, n * sizeof ( int )); // precompute the minimum and count arrays preprocess(n); int l = 1, r = 4; // answers 1-st query cout << answerQuery(n, l, r) << endl; l = 2, r = 6; // answers 2nd query cout << answerQuery(n, l, r) << endl; return 0; } |
Java
import java.util.Arrays; public class MinimumCount { static final int N = 100005 ; static int [] a = new int [N]; static int [] cnt = new int [N]; // Function to precompute the minimum and count arrays public static void preprocess( int n) { int min_val = Integer.MAX_VALUE; // Iterate over the array from left to right for ( int i = 0 ; i < n; i++) { min_val = Math.min(min_val, a[i]); cnt[i] = (min_val == a[i]) ? 1 : 0 ; } min_val = Integer.MAX_VALUE; // Iterate over the array from right to left for ( int i = n - 1 ; i >= 0 ; i--) { min_val = Math.min(min_val, a[i]); cnt[i] += (min_val == a[i]) ? 1 : 0 ; } } // Function to answer query in range l-r public static int answerQuery( int n, int l, int r) { int min_val = Integer.MAX_VALUE; int ans = 0 ; // Iterate over the given range for ( int i = l - 1 ; i < r; i++) { min_val = Math.min(min_val, a[i]); } // Iterate over the given range again to count the occurrences for ( int i = l - 1 ; i < r; i++) { if (a[i] == min_val) { ans += cnt[i]; } } return ans; } // Driver Code public static void main(String[] args) { int [] a = { 1 , 1 , 2 , 4 , 3 , 3 }; int n = a.length; System.arraycopy(a, 0 , MinimumCount.a, 0 , n); // Precompute the minimum and count arrays preprocess(n); int l = 1 , r = 4 ; // Answer the first query System.out.println(answerQuery(n, l, r)); l = 2 ; r = 6 ; // Answer the second query System.out.println(answerQuery(n, l, r)); } } |
Python3
def preprocess(n, a, cnt): min_val = float ( 'inf' ) # Iterate over the array from left to right for i in range (n): min_val = min (min_val, a[i]) cnt[i] = 1 if min_val = = a[i] else 0 min_val = float ( 'inf' ) # Iterate over the array from right to left for i in range (n - 1 , - 1 , - 1 ): min_val = min (min_val, a[i]) cnt[i] + = 1 if min_val = = a[i] else 0 def answerQuery(n, l, r, a, cnt): min_val = float ( 'inf' ) ans = 0 # Iterate over the given range for i in range (l - 1 , r): min_val = min (min_val, a[i]) # Iterate over the given range again to count the occurrences for i in range (l - 1 , r): if a[i] = = min_val: ans + = cnt[i] return ans if __name__ = = "__main__" : a = [ 1 , 1 , 2 , 4 , 3 , 3 ] n = len (a) a_copy = a.copy() cnt = [ 0 ] * n # Precompute the minimum and count arrays preprocess(n, a_copy, cnt) l = 1 r = 4 # Answer the first query print (answerQuery(n, l, r, a_copy, cnt)) l = 2 r = 6 # Answer the second query print (answerQuery(n, l, r, a_copy, cnt)) |
C#
using System; class GFG { const int N = 100005; static int [] a = new int [N]; static int [] cnt = new int [N]; // function to precompute the minimum and count arrays static void Preprocess( int n) { int min_val = int .MaxValue; // iterate over the array from left to right for ( int i = 0; i < n; i++) { min_val = Math.Min(min_val, a[i]); cnt[i] = (min_val == a[i]) ? 1 : 0; } min_val = int .MaxValue; // iterate over the array from right to left for ( int i = n - 1; i >= 0; i--) { min_val = Math.Min(min_val, a[i]); cnt[i] += (min_val == a[i]) ? 1 : 0; } } // function to answer query in range l-r static int AnswerQuery( int n, int l, int r) { int min_val = int .MaxValue, ans = 0; // iterate over the given range for ( int i = l - 1; i < r; i++) { min_val = Math.Min(min_val, a[i]); } // iterate over the given range again to count the occurrences for ( int i = l - 1; i < r; i++) { if (a[i] == min_val) { ans += cnt[i]; } } return ans; } // Driver Code static void Main() { int [] a = { 1, 1, 2, 4, 3, 3 }; int n = a.Length; Array.Copy(a, GFG.a, n); // precompute the minimum and count arrays Preprocess(n); int l = 1, r = 4; // answers 1st query Console.WriteLine(AnswerQuery(n, l, r)); l = 2; r = 6; // answers 2nd query Console.WriteLine(AnswerQuery(n, l, r)); } } |
Javascript
// Define the constants const N = 100005; const INT_MAX = 1 << 30; // Approximating INT_MAX for JavaScript // Declare global arrays and variables let a = new Array(N); let cnt = new Array(N); // Function to precompute the minimum and count arrays function preprocess(n) { let min_val = INT_MAX; // Iterate over the array from left to right for (let i = 0; i < n; i++) { min_val = Math.min(min_val, a[i]); cnt[i] = (min_val === a[i]) ? 1 : 0; } min_val = INT_MAX; // Iterate over the array from right to left for (let i = n - 1; i >= 0; i--) { min_val = Math.min(min_val, a[i]); cnt[i] += (min_val === a[i]) ? 1 : 0; } } // Function to answer a query in the range [l, r] function answerQuery(n, l, r) { let min_val = INT_MAX; let ans = 0; // Iterate over the given range for (let i = l - 1; i < r; i++) { min_val = Math.min(min_val, a[i]); } // Iterate over the given range again to count the occurrences for (let i = l - 1; i < r; i++) { if (a[i] === min_val) { ans += cnt[i]; } } return ans; } // Driver Code let inputArray = [1, 1, 2, 4, 3, 3]; let n = inputArray.length; a = [...inputArray]; // Copy the input array to 'a' // Precompute the minimum and count arrays preprocess(n); let l = 1, r = 4; // Answer the 1st query console.log(answerQuery(n, l, r)); l = 2, r = 6; // Answer the 2nd query console.log(answerQuery(n, l, r)); |
4 2
Time complexity: O(nlog(n))
Auxiliary Space: O(n*log(n))