Consider an array of size n with initial 0 values. How many indices will contain a value at least x after performing m range updates? In each of their queries, you are given a range from L to R and you have to add 1 to each index starting from L to R (both inclusive). Now, you are given q queries and in each query, a number x. Your task is to find out how many array indices are greater than or equal to x. (the value of n, m, q can be up to 10^6)
Examples:
Input : n = 4
l[] = {1, 1, 3};
r[] = {3, 2, 4};
x[] = {1, 4, 2};
Output :
Number of indexes with atleast 1 is 4
Number of indexes with atleast 4 is 0
Number of indexes with atleast 2 is 3
Explanation :
Initial array is {0, 0, 0, 0}
After first update : {1, 1, 1, 0}
After second update : {2, 2, 1, 0}
After third update : {2, 2, 2, 1}
Naive Approach: The trivial solution that comes to mind is to create an array of size n and for each update [L, R] add 1 to each array index within this range. Then, for each x, count by traversing the whole array, the number of indices with a value greater than or equal to x. However, we are given that the value of n and q is very large (up to 10^6), so for every query, we cannot simply traverse the array and find out how many indices have at least x as their value. In the worst-case time, complexity is O(nq), which is quite inefficient.
Efficient Approach: The idea is to first compute values of the array by accumulating all increments (We use the same technique as this post). After finding elements, we find the frequency of every element. Then we compute frequencies of greater elements by traversing from right to left. Finally, we can answer all queries in O(1) time.
Implementation:
C++
// C++ code to count element // with values at least x.#include<bits/stdc++.h>using namespace std;// For every query in x[0..q-1], count of values// greater than or equal to query value are printed.void coutIndices(int n, int l[], int r[], int m, int x[], int q){ // Start and end store frequencies of all // starting and ending points int start[n+1] = {0}; int End[n+1] = {0}; for (int i = 0; i < m; i++) { start[l[i]] += 1; End[r[i]] += 1; } // Find actual array values after m queries int compute[n+1] = {0}; compute[1] = start[1]; for (int i = 1; i <= n; i++) compute[i] = compute[i - 1] + start[i] - End[i - 1]; // Find frequency of every element in compute[] int max = *max_element(compute, compute+n+1); int freq[max+1] = {0}; for (int i=1; i<=n; i++) freq[compute[i]]++; // reverse cumulative sum of the freq array // because of atleast value of array // indices for each possible x for (int i = max-1; i >= 0; i--) freq[i] += freq[i + 1]; // Solving queries for (int i = 0; i < q; i++) { cout << "number of indexes with atleast " << x[i] << " is "; if (x[i] > max) cout << 0 << "\n"; else cout << freq[x[i]] << endl; }}// Driver codeint main(){ // Number of elements in an array // with all initial 0 values int n = 7; // Subarrays that need to be incremented int l[] = {1, 2, 1, 5}; int r[] = {3, 5, 2, 6}; // Query values int x[] = {1, 7, 4, 2}; int m = sizeof(l)/sizeof(l[0]); int q = sizeof(x)/sizeof(x[0]); coutIndices(n, l, r, m, x, q); return 0;} |
Java
// Java code to count element // with values at least x.import java.io.*;import java.util.*;class GFG { // For every query in x[0..q-1], // count of values greater than // or equal to query value are // printed.static void coutIndices(int n, int l[], int r[], int m, int x[], int q){ // Start and end store // frequencies of all // starting and ending points int []start = new int[n + 1]; int End[] = new int[n + 1]; for (int i = 0; i < m; i++) { start[l[i]] += 1; End[r[i]] += 1; } // Find actual array // values after m queries int compute[] = new int[n + 1]; compute[1] = start[1]; for (int i = 1; i <= n; i++) compute[i] = compute[i - 1] + start[i] - End[i - 1]; // Find frequency of every // element in compute[] Arrays.sort(compute); int max = compute[n]; int freq[] = new int[max + 1]; for (int i = 1; i <= n; i++) freq[compute[i]]++; // reverse cumulative sum of // the freq array because of // atleast value of array // indices for each possible x for (int i = max - 1; i >= 0; i--) freq[i] += freq[i + 1]; // Solving queries for (int i = 0; i < q; i++) { System.out.print("number of indexes " + "with atleast " + x[i] + " is "); if (x[i] > max) System.out.println("0"); else System.out.println(freq[x[i]]); }}// Driver codepublic static void main (String[] args) { // Number of elements in // an array with all // initial 0 valuesint n = 7;// Subarrays that need// to be incrementedint l[] = {1, 2, 1, 5};int r[] = {3, 5, 2, 6};// Query valuesint x[] = {1, 7, 4, 2};int m = l.length;int q = x.length;coutIndices(n, l, r, m, x, q);}}// This code has been // contributed by anuj_67. |
Python3
# Python 3 code to count element with # values at least x.# For every query in x[0..q-1], count # of values greater than or equal to # query value are printed.def coutIndices(n, l, r, m, x, q): # Start and end store frequencies # of all starting and ending points start = [0 for i in range(n + 1)] End = [0 for i in range(n + 1)] for i in range(0, m, 1): start[l[i]] += 1 End[r[i]] += 1 # Find actual array values # after m queries compute = [0 for i in range(n + 1)] compute[1] = start[1] for i in range(1, n + 1, 1): compute[i] = (compute[i - 1] + start[i] - End[i - 1]) # Find frequency of every # element in compute[] max = compute[0] for i in range(len(compute)): if(compute[i] > max): max = compute[i] freq = [0 for i in range(max + 1)] for i in range(1, n + 1, 1): freq[compute[i]] += 1 # reverse cumulative sum of the freq # array because of atleast value of # array indices for each possible x i = max - 1 while(i >= 0): freq[i] += freq[i + 1] i -= 1 # Solving queries for i in range(0, q, 1): print("number of indexes with atleast", x[i], "is", end = " ") if (x[i] > max): print(0) else: print(freq[x[i]])# Driver codeif __name__ == '__main__': # Number of elements in an array # with all initial 0 values n = 7 # Subarrays that need to be incremented l = [1, 2, 1, 5] r = [3, 5, 2, 6] # Query values x= [1, 7, 4, 2] m = len(l) q = len(x) coutIndices(n, l, r, m, x, q);# This code is contributed by# Sahil_Shelangia |
C#
// C# code to count element // with values at least x.using System;class GFG { // For every query in x[0..q-1], // count of values greater than // or equal to query value are // printed.static void coutIndices(int n, int []l, int []r, int m, int []x, int q){ // Start and end store // frequencies of all // starting and ending points int []start = new int[n + 1]; int []End = new int[n + 1]; for (int i = 0; i < m; i++) { start[l[i]] += 1; End[r[i]] += 1; } // Find actual array // values after m queries int []compute = new int[n + 1]; compute[1] = start[1]; for (int i = 1; i <= n; i++) compute[i] = compute[i - 1] + start[i] - End[i - 1]; // Find frequency of every // element in compute[] Array.Sort(compute); int max = compute[n]; int []freq = new int[max + 1]; for (int i = 1; i <= n; i++) freq[compute[i]]++; // reverse cumulative sum of // the freq array because of // atleast value of array // indices for each possible x for (int i = max - 1; i >= 0; i--) freq[i] += freq[i + 1]; // Solving queries for (int i = 0; i < q; i++) { Console.Write("number of indexes " + "with atleast " + x[i] + " is "); if (x[i] > max) Console.WriteLine("0"); else Console.WriteLine(freq[x[i]]); }}// Driver codepublic static void Main () { // Number of elements in // an array with all // initial 0 valuesint n = 7;// Subarrays that need// to be incrementedint []l = {1, 2, 1, 5};int []r = {3, 5, 2, 6};// Query valuesint []x = {1, 7, 4, 2};int m = l.Length;int q = x.Length;coutIndices(n, l, r, m, x, q);}}// This code has been // contributed by anuj_67. |
Javascript
<script> // Javascript code to count element with values at least x. // For every query in x[0..q-1], // count of values greater than // or equal to query value are // printed. function coutIndices(n, l, r, m, x, q) { // Start and end store // frequencies of all // starting and ending points let start = new Array(n + 1); start.fill(0); let End = new Array(n + 1); End.fill(0); for (let i = 0; i < m; i++) { start[l[i]] += 1; End[r[i]] += 1; } // Find actual array // values after m queries let compute = new Array(n + 1); compute.fill(0); compute[1] = start[1]; for (let i = 1; i <= n; i++) compute[i] = compute[i - 1] + start[i] - End[i - 1]; // Find frequency of every // element in compute[] compute.sort(); let max = compute[n]; let freq = new Array(max + 1); freq.fill(0); for (let i = 1; i <= n; i++) freq[compute[i]]++; // reverse cumulative sum of // the freq array because of // atleast value of array // indices for each possible x for (let i = max - 1; i >= 0; i--) freq[i] += freq[i + 1]; // Solving queries for (let i = 0; i < q; i++) { document.write("number of indexes " + "with atleast " + x[i] + " is "); if (x[i] > max) document.write("0" + "</br>"); else document.write(freq[x[i]] + "</br>"); } } // Number of elements in // an array with all // initial 0 values let n = 7; // Subarrays that need // to be incremented let l = [1, 2, 1, 5]; let r = [3, 5, 2, 6]; // Query values let x = [1, 7, 4, 2]; let m = l.length; let q = x.length; coutIndices(n, l, r, m, x, q);</script> |
Output
number of indexes with atleast 1 is 6 number of indexes with atleast 7 is 0 number of indexes with atleast 4 is 0 number of indexes with atleast 2 is 4
Time Complexity: O(n+m+q+max) where max is the maximum element in compute array.
Auxiliary Space: O(n+max)
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!
