Count of locations between X and Y having rainfall more than K cms for Q queries
Given an array arr[][] consisting of N triplets ( start, end, rainfall in cms), defining rain will fall from the start location to the end location with the given intensity of rainfall in cms. Also given an integer K and Q queries in the form of array query[][] ( In each query X and Y is given ). For each query, the task is to find the number of locations between X and Y ( inclusive ) having rainfall more than K cms.
Examples:
Input: arr[][] = {{1, 3, 5}, {2, 8, 3}, {5, 8, 2}, {7, 9, 6}}, K = 5, query[][] ={{1, 5}, {5, 9}, {2, 9}, {1, 9}}
Output: 4, 5, 7, 8
Explanation: The aggregate array for given locations will be:
5 8 8 3 5 5 11 11 6 1 2 3 4 5 6 7 8 9 The aggregate array tells about the amount of rainfall in each location.
From locations 1 to 5, { 1, 2, 3, 5 } have rainfall >= 5 cms, Therefore answer is 4.
From locations 5 to 9, { 5, 6, 7, 8, 9 } have rainfall >= 5 cms, Therefore answer is 5.
From locations 2 to 9, { 2, 3, 5, 6, 7, 8, 9 } have rainfall >= 5 cms, Therefore answer is 7.
From locations 1 to 9, { 1, 2, 3, 5, 6, 7, 8, 9 } have rainfall >= 5 cms, Therefore answer is 9.Input: arr[][] = {{2, 4, 1 }, {3, 9, 3}}, K = 5, query[][] ={{2, 5}, {4, 6}}
Output: 3, 3
Naive approach: Traverse array arr[][] and find the maximum value of location. Create an array with size equals to the maximum location found. Then for each range of rainfall update the array to get the aggregated array. Now for each query traverse the formed array and count the number of locations with rainfall greater than K cms.
Below is the code for the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find number of locations // with rainfall more than K cms vector< int > count(vector< int > arr, vector<vector< int > > Q, int q, int k) { vector< int > ans; for ( int i = 0; i < q; i++) { int temp = 0; for ( int j = Q[i][0]; j <= Q[i][1]; j++) { if (arr[j] >= k) temp++; } ans.push_back(temp); } return ans; } // Function to find aggregate array vector< int > aggregateArray(vector<vector< int > > arr, int n) { // To store the maximum location int m = 0; for ( int i = 0; i < n; i++) m = max(m, arr[i][1]); // Array to store the aggregate values vector< int > agg(m + 1); for ( int i = 0; i < n; i++) { for ( int j = arr[i][0]; j <= arr[i][1]; j++) { agg[j] += arr[i][2]; } } return agg; } // Driver Code int main() { int N = 4; vector<vector< int > > arr = { { 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 } }; // Storing aggregate array vector< int > agg = aggregateArray(arr, N); int Q = 4; vector<vector< int > > queries = { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } }; int K = 5; vector< int > ans = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0; i < N; i++) { cout << ans[i] << endl; } } |
Java
// Java program for above approach public class GFG { // Function to find number of locations // with rainfall more than K cms static int [] count( int arr[], int Q[][], int q, int k) { int ans[] = new int [q]; for ( int i = 0 ; i < q; i++) { int temp = 0 ; for ( int j = Q[i][ 0 ]; j <= Q[i][ 1 ]; j++) { if (arr[j] >= k) temp++; } ans[i] = temp; } return ans; } // Function to find aggregate array static int [] aggregateArray( int arr[][], int n) { // To store the maximum location int m = 0 ; for ( int i = 0 ; i < n; i++) m = Math.max(m, arr[i][ 1 ]); // Array to store the aggregate values int agg[] = new int [m + 1 ]; for ( int i = 0 ; i < n; i++) { for ( int j = arr[i][ 0 ]; j <= arr[i][ 1 ]; j++) { agg[j] += arr[i][ 2 ]; } } return agg; } // Driver code public static void main(String[] args) { int N = 4 ; int arr[][] = { { 1 , 3 , 5 }, { 2 , 8 , 3 }, { 5 , 8 , 2 }, { 7 , 9 , 6 } }; // Storing aggregate array int agg[] = aggregateArray(arr, N); int Q = 4 ; int queries[][] = { { 1 , 5 }, { 5 , 9 }, { 2 , 9 }, { 1 , 9 } }; int K = 5 ; int ans[] = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0 ; i < N; i++) { System.out.println(ans[i]); } } } // This code is contributed by phasing17 |
Python3
# python program for above approach # Function to find number of locations # with rainfall more than K cms def count(arr, Q, q, k): ans = [] for i in range ( 0 , q): temp = 0 for j in range (Q[i][ 0 ], Q[i][ 1 ] + 1 ): if (arr[j] > = k): temp + = 1 ans.append(temp) return ans # Function to find aggregate array def aggregateArray(arr, n): # To store the maximum location m = 0 for i in range ( 0 , n): m = max (m, arr[i][ 1 ]) # Array to store the aggregate values agg = [ 0 for _ in range (m + 1 )] for i in range ( 0 , n): for j in range (arr[i][ 0 ], arr[i][ 1 ] + 1 ): agg[j] + = arr[i][ 2 ] return agg # Driver Code if __name__ = = "__main__" : N = 4 arr = [ [ 1 , 3 , 5 ], [ 2 , 8 , 3 ], [ 5 , 8 , 2 ], [ 7 , 9 , 6 ] ] # Storing aggregate array agg = aggregateArray(arr, N) Q = 4 queries = [[ 1 , 5 ], [ 5 , 9 ], [ 2 , 9 ], [ 1 , 9 ]] K = 5 ans = count(agg, queries, Q, K) # Printing answer to each query for i in range ( 0 , N): print (ans[i]) # This code is contributed by rakeshsahni |
C#
// C# program for above approach using System; public class GFG { // Function to find number of locations // with rainfall more than K cms static int [] count( int [] arr, int [, ] Q, int q, int k) { int [] ans = new int [q]; for ( int i = 0; i < q; i++) { int temp = 0; for ( int j = Q[i, 0]; j <= Q[i, 1]; j++) { if (arr[j] >= k) temp++; } ans[i] = temp; } return ans; } // Function to find aggregate array static int [] aggregateArray( int [, ] arr, int n) { // To store the maximum location int m = 0; for ( int i = 0; i < n; i++) m = Math.Max(m, arr[i, 1]); // Array to store the aggregate values int [] agg = new int [m + 1]; for ( int i = 0; i < n; i++) { for ( int j = arr[i, 0]; j <= arr[i, 1]; j++) { agg[j] += arr[i, 2]; } } return agg; } // Driver code public static void Main( string [] args) { int N = 4; int [, ] arr = { { 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 } }; // Storing aggregate array int [] agg = aggregateArray(arr, N); int Q = 4; int [, ] queries = { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } }; int K = 5; int [] ans = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0; i < N; i++) { Console.WriteLine(ans[i]); } } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find number of locations // with rainfall more than K cms function count(arr, Q, q, k) { let ans = []; for (let i = 0; i < q; i++) { let temp = 0; for (let j = Q[i][0]; j <= Q[i][1]; j++) { if (arr[j] >= k) temp++; } ans.push(temp); } return ans; } // Function to find aggregate array function aggregateArray( arr, n) { // To store the maximum location let m = 0; for (let i = 0; i < n; i++) m = Math.max(m, arr[i][1]); // Array to store the aggregate values let agg = new Array(m + 1).fill(0); for (let i = 0; i < n; i++) { for (let j = arr[i][0]; j <= arr[i][1]; j++) { agg[j] += arr[i][2]; } } return agg; } // Driver Code let N = 4; let arr = [ [1, 3, 5], [2, 8, 3], [5, 8, 2], [7, 9, 6] ]; // Storing aggregate array let agg = aggregateArray(arr, N); let Q = 4; let queries = [[1, 5], [5, 9], [2, 9], [1, 9]]; let K = 5; let ans = count(agg, queries, Q, K); // Printing answer to each query for (let i = 0; i < N; i++) { document.write(ans[i] + "<br>" ); } // This code is contributed by Potta Lokesh </script> |
4 5 7 8
Time Complexity: O(max(O(N*M), O(Q*M))).
Auxiliary space: O(M).
Where N is number of inputs, Q is number of queries, and M is max location.
Efficient Approach: The given problem can be solved by using the Weighted job scheduling approach and with Prefix Sum. This problem can be solved in two parts, forming aggregated array and then apply prefix sum for answering queries efficiently. Follow the steps below to solve the given problem.
- Sort arr[][] on the basis of end location.
- Use map data structure to store the start location and overlap count.
- For each end location, update the aggregate array, by doing rainfall data + overlap.
- Use Hashmaps for decrementing overlap, after the start location is crossed.
- For each triplet update the Hashmap with the start time.
- Traverse and fill overlap in the array until the end location of the next triplet is reached.
- Once the aggregate array is found, use prefix sum to find the answer to each query.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Comparator function to sort // the array in specific order static bool comp(vector< int > a, vector< int > b) { return (a[1] > b[1]); } // Function to find number of locations // with rainfall more than K cms vector< int > count(vector< int > arr, vector<vector< int > > Q, int q, int k) { // Prefix sum array, // of count of locations having // rainfall greater than k cms int n = arr.size(); vector< int > arrPre(n); if (arr[0] >= k) arrPre[0] = 1; else arrPre[0] = 0; for ( int i = 1; i < n; i++) { if (arr[i] >= k) arrPre[i] = arrPre[i - 1] + 1; else arrPre[i] = arrPre[i - 1]; } // evaluating the queries vector< int > ans; for ( int i = 0; i < q; i++) { ans.push_back(arrPre[Q[i][1]] - arrPre[Q[i][0] - 1]); } return ans; } // Function to find aggregate array vector< int > aggregateArray(vector<vector< int > > N, int n) { // To store the maximum location int m = 0; for ( int i = 0; i < n; i++) m = max(m, N[i][1]); // Array to store rainfall // of m locations sorting // input array based on end time, // in descending order vector< int > arr(m + 1); sort(N.begin(), N.end(), comp); // To store start locn and // rainfall corresponding to it unordered_map< int , int > start; int overlap = 0; for ( int i = 0; i < n; i++) { // If two inputs have same end time, // we need to reposition them if (m < N[i][1]) m++; else // Fill m with overlap, // till we reach current end location, // and keep checking if we've crossed // start time of previously recorded data // and decrement overlap(map) while (m > 0 && m != N[i][1]) overlap -= start[m], arr[m--] = overlap; // To check if start time is crossed // of previously recorded data // and decrement overlap(map) overlap -= start[m]; // Input data + previous recorded data arr[m] = overlap + N[i][2]; // updating overlap with current data overlap += N[i][2]; // storing start location with // corresponding rainfall data start[N[i][0] - 1] = N[i][2]; // update m m--; } while (m >= N[n - 1][0]) // fill out the left out indexes overlap -= start[m], arr[m--] = overlap; return arr; } // Driver Code int main() { int N = 4; vector<vector< int > > arr = { { 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 } }; vector< int > agg = aggregateArray(arr, N); int Q = 4; vector<vector< int > > queries = { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } }; int K = 5; vector< int > ans = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0; i < N; i++) { cout << ans[i] << endl; } } |
Java
// Java program for above approach import java.util.Arrays; import java.util.HashMap; public class GFG { // Function to find number of locations // with rainfall more than K cms static int [] count( int arr[], int Q[][], int q, int k) { // Prefix sum array, // of count of locations having // rainfall greater than k cms int n = arr.length; int [] arrPre = new int [n]; if (arr[ 0 ] >= k) arrPre[ 0 ] = 1 ; else arrPre[ 0 ] = 0 ; for ( int i = 1 ; i < n; i++) { if (arr[i] >= k) arrPre[i] = arrPre[i - 1 ] + 1 ; else arrPre[i] = arrPre[i - 1 ]; } // evaluating the queries int ans[] = new int [q]; for ( int i = 0 ; i < q; i++) { ans[i] = (arrPre[Q[i][ 1 ]] - arrPre[Q[i][ 0 ] - 1 ]); } return ans; } // Function to find aggregate array static int [] aggregateArray( int N[][], int n) { // To store the maximum location int m = 0 ; for ( int i = 0 ; i < n; i++) m = Math.max(m, N[i][ 1 ]); // Array to store rainfall // of m locations sorting // input array based on end time, // in descending order int [] arr = new int [m + 1 ]; Arrays.sort(N, (a, b) -> - a[ 1 ] + b[ 1 ]); // To store start locn and // rainfall corresponding to it HashMap<Integer, Integer> start = new HashMap<Integer, Integer>(); int overlap = 0 ; for ( int i = 0 ; i < n; i++) { // If two inputs have same end time, // we need to reposition them if (m < N[i][ 1 ]) m++; else // Fill m with overlap, // till we reach current end location, // and keep checking if we've crossed // start time of previously recorded data // and decrement overlap(map) while (m > 0 && m != N[i][ 1 ]) { overlap -= start.getOrDefault(m, 0 ); arr[m--] = overlap; } // To check if start time is crossed // of previously recorded data // and decrement overlap(map) overlap -= start.getOrDefault(m, 0 ); // Input data + previous recorded data arr[m] = overlap + N[i][ 2 ]; // updating overlap with current data overlap += N[i][ 2 ]; // storing start location with // corresponding rainfall data start.put(N[i][ 0 ] - 1 , N[i][ 2 ]); // update m m--; } while (m >= N[n - 1 ][ 0 ]) { // fill out the left out indexes overlap -= start.getOrDefault(m, 0 ); arr[m--] = overlap; } return arr; } // Driver code public static void main(String[] args) { int N = 4 ; int arr[][] = { { 1 , 3 , 5 }, { 2 , 8 , 3 }, { 5 , 8 , 2 }, { 7 , 9 , 6 } }; // Storing aggregate array int agg[] = aggregateArray(arr, N); int Q = 4 ; int queries[][] = { { 1 , 5 }, { 5 , 9 }, { 2 , 9 }, { 1 , 9 } }; int K = 5 ; int ans[] = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0 ; i < N; i++) { System.out.println(ans[i]); } } } // This code is contributed by Lovely Jain |
Python3
# Python program for above approach # Function to find number of locations # with rainfall more than K cms from functools import cmp_to_key def mycmp(a, b): return b[ 1 ] - a[ 1 ] def count(arr, Q, q, k): # Prefix sum array, # of count of locations having # rainfall greater than k cms n = len (arr) arrPre = [ 0 for i in range (n)] if (arr[ 0 ] > = k): arrPre[ 0 ] = 1 else : arrPre[ 0 ] = 0 for i in range ( 1 ,n): if (arr[i] > = k): arrPre[i] = arrPre[i - 1 ] + 1 else : arrPre[i] = arrPre[i - 1 ] # evaluating the queries ans = [] for i in range (q): ans.append(arrPre[Q[i][ 1 ]] - arrPre[Q[i][ 0 ] - 1 ]) return ans # Function to find aggregate array def aggregateArray(N, n): # To store the maximum location m = 0 for i in range (n): m = max (m, N[i][ 1 ]) # Array to store rainfall # of m locations sorting # input array based on end time, # in descending order arr = [ 0 for i in range (m + 1 )] N.sort(key = cmp_to_key(mycmp)) # To store start locn and # rainfall corresponding to it start = {} overlap = 0 for i in range (n): # If two inputs have same end time, # we need to reposition them if (m < N[i][ 1 ]): m + = 1 else : # Fill m with overlap, # till we reach current end location, # and keep checking if we've crossed # start time of previously recorded data # and decrement overlap(map) while (m > 0 and m ! = N[i][ 1 ]): overlap - = start[m] if m in start else 0 arr[m] = overlap m - = 1 # To check if start time is crossed # of previously recorded data # and decrement overlap(map) overlap - = start[m] if m in start else 0 # Input data + previous recorded data arr[m] = overlap + N[i][ 2 ] # updating overlap with current data overlap + = N[i][ 2 ] # storing start location with # corresponding rainfall data start[N[i][ 0 ] - 1 ] = N[i][ 2 ] # update m m - = 1 while (m > = N[n - 1 ][ 0 ]): # fill out the left out indexes overlap - = start[m] if m in start else 0 arr[m] = overlap m - = 1 return arr # Driver Code N = 4 arr = [ [ 1 , 3 , 5 ], [ 2 , 8 , 3 ], [ 5 , 8 , 2 ], [ 7 , 9 , 6 ] ] agg = aggregateArray(arr, N) Q = 4 queries = [ [ 1 , 5 ], [ 5 , 9 ], [ 2 , 9 ], [ 1 , 9 ] ] K = 5 ans = count(agg, queries, Q, K) # Printing answer to each query for i in range (N): print (ans[i]) # This code is contributed by shinjanpatra |
C#
using System; using System.Collections; using System.Collections.Generic; using System.Linq; // C# program for above approach class HelloWorld { public static void Sort<T>(T[][] data, int col) { Comparer<T> comparer = Comparer<T>.Default; Array.Sort<T[]>(data, (x,y) => comparer.Compare(y[col],x[col])); } // Function to find number of locations // with rainfall more than K cms public static List< int > count( int [] arr, int [][] Q, int q, int k) { // Prefix sum array, // of count of locations having // rainfall greater than k cms int n = arr.Length; int [] arrPre = new int [n]; if (arr[0] >= k) arrPre[0] = 1; else arrPre[0] = 0; for ( int i = 1; i < n; i++) { if (arr[i] >= k) arrPre[i] = arrPre[i - 1] + 1; else arrPre[i] = arrPre[i - 1]; } // evaluating the queries List< int > ans = new List< int >(); for ( int i = 0; i < q; i++) { ans.Add(arrPre[Q[i][1]] - arrPre[Q[i][0] - 1]); } return ans; } // Function to find aggregate array public static int [] aggregateArray( int [][] N, int n) { // To store the maximum location int m = 0; for ( int i = 0; i < n; i++) m = Math.Max(m, N[i][1]); // Array to store rainfall // of m locations sorting // input array based on end time, // in descending order int [] arr = new int [m+1]; Sort< int >(N, 1); // To store start locn and // rainfall corresponding to it var start = new Dictionary< int , int >(); int overlap = 0; for ( int i = 0; i < n; i++) { // If two inputs have same end time, // we need to reposition them if (m < N[i][1]) m++; else // Fill m with overlap, // till we reach current end location, // and keep checking if we've crossed // start time of previously recorded data // and decrement overlap(map) while (m > 0 && m != N[i][1]){ if (start.ContainsKey(m)){ overlap -= start[m]; } arr[m--] = overlap; } // To check if start time is crossed // of previously recorded data // and decrement overlap(map) if (start.ContainsKey(m)){ overlap -= start[m]; } // Input data + previous recorded data arr[m] = overlap + N[i][2]; // updating overlap with current data overlap += N[i][2]; // storing start location with // corresponding rainfall data start[N[i][0] - 1] = N[i][2]; // update m m--; } while (m >= N[n - 1][0]){ // fill out the left out indexes if (start.ContainsKey(m)){ overlap -= start[m]; } arr[m--] = overlap; } return arr; } static void Main() { int N = 4; int [][] arr = new int [][] { new int [] { 1, 3, 5 }, new int [] { 2, 8, 3 }, new int [] { 5, 8, 2 }, new int [] { 7, 9, 6} }; int [] agg = aggregateArray(arr, N); int Q = 4; int [][] queries = new int [][] { new int [] {1, 5}, new int [] {5, 9}, new int [] {2, 9}, new int [] {1, 9} }; int K = 5; List< int > ans = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0; i < N; i++) { Console.WriteLine(ans[i]); } } } // The code is contributed by Nidhi goel. |
Javascript
<script> // Javascript program for above approach // Function to find number of locations // with rainfall more than K cms function count(arr, Q, q, k) { // Prefix sum array, // of count of locations having // rainfall greater than k cms var n = arr.length; var arrPre = Array(n).fill(0); if (arr[0] >= k) arrPre[0] = 1; else arrPre[0] = 0; for ( var i = 1; i < n; i++) { if (arr[i] >= k) arrPre[i] = arrPre[i - 1] + 1; else arrPre[i] = arrPre[i - 1]; } // evaluating the queries var ans = []; for ( var i = 0; i < q; i++) { ans.push( arrPre[Q[i][1]] - arrPre[Q[i][0] - 1]); } return ans; } // Function to find aggregate array function aggregateArray(N, n) { // To store the maximum location var m = 0; for ( var i = 0; i < n; i++) m = Math.max(m, N[i][1]); // Array to store rainfall // of m locations sorting // input array based on end time, // in descending order var arr = Array(m + 1).fill(0); N.sort((a,b)=>b[1] - a[1]); // To store start locn and // rainfall corresponding to it var start = new Map(); var overlap = 0; for ( var i = 0; i < n; i++) { // If two inputs have same end time, // we need to reposition them if (m < N[i][1]) m++; else { // Fill m with overlap, // till we reach current end location, // and keep checking if we've crossed // start time of previously recorded data // and decrement overlap(map) while (m > 0 && m != N[i][1]) { overlap -= start.has(m)?start.get(m):0; arr[m--] = overlap; } } // To check if start time is crossed // of previously recorded data // and decrement overlap(map) overlap -= start.has(m)?start.get(m):0; // Input data + previous recorded data arr[m] = overlap + N[i][2]; // updating overlap with current data overlap += N[i][2]; // storing start location with // corresponding rainfall data start.set(N[i][0] - 1, N[i][2]); // update m m--; } while (m >= N[n - 1][0]) { // fill out the left out indexes overlap -= start.has(m)?start.get(m):0; arr[m--] = overlap; } return arr; } // Driver Code var N = 4; var arr = [ [ 1, 3, 5 ], [ 2, 8, 3 ], [ 5, 8, 2 ], [ 7, 9, 6 ] ]; var agg = aggregateArray(arr, N); var Q = 4; var queries = [ [ 1, 5 ], [ 5, 9 ], [ 2, 9 ], [ 1, 9 ] ]; var K = 5; var ans = count(agg, queries, Q, K); // Printing answer to each query for ( var i = 0; i < N; i++) { document.write(ans[i] + "<br>" ); } // This code is contributed by rrrtnx. </script> |
4 5 7 8
Time Complexity: O(max(NlogN, M)).
Auxiliary Space: O(M).
Where N is number of inputs and M is maximum location.
Efficient Approach 2: In the above approach, we are first sorting the array on the basis of end time and then calculating the aggregate array which takes O(NLogN) time. We can improve this time by calculating the aggregate array as follows:
Let the aggregate array be agg[].
We first iterate over each of the rainfall data. For each data (start, end, and val), add val to agg[start] and subtract val from agg[end+1] because the rainfall starts from position start and continue till end (inclusive).
Then, we iterate second time over the agg array and keep track of current rainfall currRain (initialized to 0) by adding the value of agg[index] to it and updating agg[index] as currRain.
Once the aggregate array is created, use prefix sum to find the answer each query.
Below is the implementation of the above approach:
C++14
// C++ program for above approach #include<bits/stdc++.h> using namespace std; // Function to find number of locations // with rainfall more than K cms vector< int > count(vector< int > arr, vector<vector< int >> Q, int q, int k) { int n = arr.size(); // prefix sum array vector< int > prefix(n); if (arr[0] >= k) { prefix[0] = 1; } else { prefix[0] = 0; } for ( int i = 1; i < n - 1; i++) { if (arr[i] >= k) { prefix[i] = prefix[i - 1] + 1; } else { prefix[i] = prefix[i - 1]; } } // evaluate the queries using prefix sum array vector< int > ans(q); for ( int i = 0; i < q; i++) { int start = Q[i][0] - 1; int end = Q[i][1] - 1; // if start is the minimum location possible, // store prefix[end] if (start == 0) { ans[i] = prefix[end]; } else { ans[i] = prefix[end] - prefix[start - 1]; } } return ans; } // Function to find aggregate array vector< int > aggregateArray(vector<vector< int >> arr, int n) { // find maximum location possible int m = -1; for ( auto data : arr) { m = max(m, data[1]); } // Array to store the aggregate values vector< int > agg(m+1); // update aggregate array at index start-1 and end // locations for ( auto data : arr) { int start = data[0]; int end = data[1]; int val = data[2]; agg[start - 1] += val; agg[end] -= val; } // iterate second time to fill the complete // aggregate array currRain holds amount of rainfall // till current index int currRain = 0; for ( int i = 0; i <= m; i++) { currRain += agg[i]; agg[i] = currRain; } return agg; } int main() { int N = 4; vector<vector< int >> arr = { { 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 } }; // Storing aggregate array vector< int > agg; agg = aggregateArray(arr, N); int Q = 4; vector<vector< int >> queries = { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } }; int K = 5; vector< int > ans; ans = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0; i < N; i++) { cout<<ans[i]<<endl; } } |
Java
// Java program for above approach import java.io.*; import java.util.*; class GFG { // Function to find number of locations // with rainfall more than K cms static int [] count( int [] arr, int [][] Q, int q, int k) { int n = arr.length; // prefix sum array int [] prefix = new int [n]; if (arr[ 0 ] >= k) { prefix[ 0 ] = 1 ; } else { prefix[ 0 ] = 0 ; } for ( int i = 1 ; i < n - 1 ; i++) { if (arr[i] >= k) { prefix[i] = prefix[i - 1 ] + 1 ; } else { prefix[i] = prefix[i - 1 ]; } } // evaluate the queries using prefix sum array int [] ans = new int [q]; for ( int i = 0 ; i < q; i++) { int start = Q[i][ 0 ] - 1 ; int end = Q[i][ 1 ] - 1 ; // if start is the minimum location possible, // store prefix[end] if (start == 0 ) { ans[i] = prefix[end]; } else { ans[i] = prefix[end] - prefix[start - 1 ]; } } return ans; } // Function to find aggregate array static int [] aggregateArray( int [][] arr, int n) { // find maximum location possible int m = - 1 ; for ( int [] data : arr) { m = Math.max(m, data[ 1 ]); } // Array to store the aggregate values int [] agg = new int [m + 1 ]; // update aggregate array at index start-1 and end // locations for ( int [] data : arr) { int start = data[ 0 ]; int end = data[ 1 ]; int val = data[ 2 ]; agg[start - 1 ] += val; agg[end] -= val; } // iterate second time to fill the complete // aggregate array currRain holds amount of rainfall // till current index int currRain = 0 ; for ( int i = 0 ; i <= m; i++) { currRain += agg[i]; agg[i] = currRain; } return agg; } public static void main(String[] args) { int N = 4 ; int [][] arr = { { 1 , 3 , 5 }, { 2 , 8 , 3 }, { 5 , 8 , 2 }, { 7 , 9 , 6 } }; // Storing aggregate array int [] agg = aggregateArray(arr, N); int Q = 4 ; int [][] queries = { { 1 , 5 }, { 5 , 9 }, { 2 , 9 }, { 1 , 9 } }; int K = 5 ; int [] ans = count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0 ; i < N; i++) { System.out.println(ans[i]); } } } // This code is contributed by lokesh. |
Python3
# Python3 program for above approach # Function to find number of locations with rainfall more than K cms def count(arr, Q, q, k): n = len (arr) # prefix sum array prefix = [ 0 for _ in range (n)] if arr[ 0 ] > = k: prefix[ 0 ] = 1 else : prefix[ 0 ] = 0 for i in range ( 1 , n - 1 ): if arr[i] > = k: prefix[i] = prefix[i - 1 ] + 1 else : prefix[i] = prefix[i - 1 ] # evaluate the queries using prefix sum array ans = [] for i in range ( 0 , q): start, end = Q[i][ 0 ] - 1 , Q[i][ 1 ] - 1 # if start is the minimum location possible, store prefix[end] if start = = 0 : count = prefix[end] else : count = prefix[end] - prefix[start - 1 ] ans.append(count) return ans # Function to find aggregate array def aggregateArray(arr, n): # find maximum location possible m = - 1 for data in arr: m = max (m, data[ 1 ]) # Array to store the aggregate values agg = [ 0 for _ in range (m + 1 )] # update aggregate array at index start-1 and end locations for start, end, val in arr: agg[start - 1 ] + = val agg[end] - = val # iterate second time to fill the complete aggregate array # currRain holds amount of rainfall till current index currRain = 0 for i in range (m + 1 ): currRain + = agg[i] agg[i] = currRain return agg # Driver Code if __name__ = = "__main__" : N = 4 arr = [ [ 1 , 3 , 5 ], [ 2 , 8 , 3 ], [ 5 , 8 , 2 ], [ 7 , 9 , 6 ] ] # Storing aggregate array agg = aggregateArray(arr, N) Q = 4 queries = [[ 1 , 5 ], [ 5 , 9 ], [ 2 , 9 ], [ 1 , 9 ]] K = 5 ans = count(agg, queries, Q, K) # Printing answer to each query for i in range ( 0 , N): print (ans[i]) # This code is contributed by ultrainstinct |
C#
// C# program for above approach using System; public class GFG { // Function to find number of locations with rainfall // more than K cms static int [] Count( int [] arr, int [, ] Q, int q, int k) { int n = arr.Length; // prefix sum array int [] prefix = new int [n]; if (arr[0] >= k) { prefix[0] = 1; } else { prefix[0] = 0; } for ( int i = 1; i < n - 1; i++) { if (arr[i] >= k) { prefix[i] = prefix[i - 1] + 1; } else { prefix[i] = prefix[i - 1]; } } // evaluate the queries using prefix sum array int [] ans = new int [q]; for ( int i = 0; i < q; i++) { int start = Q[i, 0] - 1; int end = Q[i, 1] - 1; // if start is the minimum location possible, // store prefix[end] if (start == 0) { ans[i] = prefix[end]; } else { ans[i] = prefix[end] - prefix[start - 1]; } } return ans; } // Function to find aggregate array static int [] AggregateArray( int [, ] arr, int n) { // find maximum location possible int m = -1; for ( int i = 0; i < arr.GetLength(0); i++) { int data = arr[i, 1]; m = Math.Max(m, data); } // Array to store the aggregate values int [] agg = new int [m + 1]; // update aggregate array at index start-1 and end // locations for ( int i = 0; i < arr.GetLength(0); i++) { int start = arr[i, 0]; int end = arr[i, 1]; int val = arr[i, 2]; agg[start - 1] += val; agg[end] -= val; } // iterate second time to fill the complete // aggregate array currRain holds amount of rainfall // till current index int currRain = 0; for ( int i = 0; i <= m; i++) { currRain += agg[i]; agg[i] = currRain; } return agg; } static public void Main() { // Code int N = 4; int [, ] arr = { { 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 } }; // Storing aggregate array int [] agg = AggregateArray(arr, N); int Q = 4; int [, ] queries = { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } }; int K = 5; int [] ans = Count(agg, queries, Q, K); // Printing answer to each query for ( int i = 0; i < N; i++) { Console.WriteLine(ans[i]); } } } // This code is contributed by karthik. |
Javascript
// Javascript program for above approach // Function to find number of locations // with rainfall more than K cms function count(arr, Q, q, k) { let n = arr.length; // prefix sum array let prefix= new Array(n); if (arr[0] >= k) { prefix[0] = 1; } else { prefix[0] = 0; } for (let i = 1; i < n - 1; i++) { if (arr[i] >= k) { prefix[i] = prefix[i - 1] + 1; } else { prefix[i] = prefix[i - 1]; } } // evaluate the queries using prefix sum array let ans= new Array(q); for (let i = 0; i < q; i++) { let start = Q[i][0] - 1; let end = Q[i][1] - 1; // if start is the minimum location possible, // store prefix[end] if (start == 0) { ans[i] = prefix[end]; } else { ans[i] = prefix[end] - prefix[start - 1]; } } return ans; } // Function to find aggregate array function aggregateArray(arr, n) { // find maximum location possible let m = -1; for (let i = 0; i < arr.length; i++){ let data = arr[i][1] m = Math.max(m, data); } // Array to store the aggregate values let agg= new Array(m+1).fill(0); // update aggregate array at index start-1 and end // locations for (let i=0; i<arr.length; i++){ let start = arr[i][0]; let end = arr[i][1]; let val = arr[i][2]; agg[start - 1] += val; agg[end] -= val; } // iterate second time to fill the complete // aggregate array currRain holds amount of rainfall // till current index let currRain = 0; for (let i = 0; i <= m; i++) { currRain += agg[i]; agg[i] = currRain; } return agg; } let N = 4; let arr = [ [ 1, 3, 5 ], [ 2, 8, 3 ], [ 5, 8, 2 ], [ 7, 9, 6 ] ]; // Storing aggregate array let agg = new Array(); agg = aggregateArray(arr, N); let Q = 4; let queries = [ [ 1, 5 ], [ 5, 9 ], [ 2, 9 ], [ 1, 9 ] ]; let K = 5; let ans; ans = count(agg, queries, Q, K); // Printing answer to each query for (let i = 0; i < N; i++) { console.log(ans[i]); } // This code is contributed by poojaagarwal2. |
4 5 7 8
Time Complexity: O(M).
Auxiliary Space: O(M).
Where M is maximum location.
Contact Us