Given a 2D array arr[][] where each array element denotes a point in the X axis and the number of elements on that point. A query array queries[] of size Q is given where each element is of type {l, r}. The task is to find the count of elements in the given range for each query.
Examples:
Input: arr[][]={ {1, 2}, {3, 2}, {4, 5}, {7, 1}, {10, 4} }, queries[] = { {0, 12}, {4, 6}, {2, 8} }
Output: 14, 5, 8
Explanation:
queries[0]: we’ll take score all elements i.e. 2 + 2 + 5 + 1 + 4 = 14
queries[1]: Only the 3rd element can be considered so the score will be 5.
queries[2]: we’ll take elements from 2nd, 3rd and 4th position i.e. 2 + 5 + 1 = 8Input: arr[][]={ {1, 6}, {12, 5}, {3, 4, }, {14, 3}, {5, 2} }, queries[] = { {10, 12}, {1, 5}, {10, 15} }
Output: 5, 12, 8
Explanation:
queries[0] : only 2nd element will be considered so the score will be 5
queries[1]: we’ll take score of elements from 1st, 3rd and 5th position i.e. 6 + 4 + 2 = 12
queries[2]: we’ll take score of elements from 2nd and 4th position i.e. 5 + 3 = 8
Approach:
This problem can be solved using the concepts of Prefix Sum Array, Sorting, and Binary Search.
The idea is to sort the array first and calculate the prefix sum of the array and perform binary search to find elements in array.
Follow the below steps to Implement the idea:
- Sort the given array arr[] so that we can choose the elements easily.
- Create a prefix sum array prefixArr[] where prefixArr[i] represents the total elements that are present from position 0 to i-1.
- Create two variables start and end where:
- The start represents the position such that it is greater or equal to queries[i][0] and it is closest to queries[i][0] and
- The end represents the position such that it is lesser or equal to queries[i][1] and it is closest to queries[i][1].
- Find the start and end pointers using Binary Search technique.
- The answer will be the sum of the elements that occur between positions start and end which is prefixArr[end+1] – prefixArr[start].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum of elementsvector<long long> MaximumValue(int n, int q, vector<vector<int> > arr, vector<vector<int> > queries){ sort(arr.begin(), arr.end()); vector<long long> prefixArr(n + 1); vector<long long> ans(q); for (int i = 0; i < n; i++) { prefixArr[i + 1] = prefixArr[i] + arr[i][1]; } // Binary search for start for (int i = 0; i < q; i++) { int start = INT_MAX, end = INT_MIN; int l = 0, h = n - 1; while (l <= h) { int mid = l + (h - l) / 2; if (arr[mid][0] >= queries[i][0]) { start = min(start, mid); h = mid - 1; } else l = mid + 1; } // Binary search for end l = 0, h = n - 1; while (l <= h) { int mid = l + (h - l) / 2; if (arr[mid][0] <= queries[i][1]) { end = max(end, mid); l = mid + 1; } else h = mid - 1; } if (end + 1 < 0 || start >= prefixArr.size()) { ans[i] = 0; } else ans[i] = prefixArr[end + 1] - prefixArr[start]; } // Return the answers for all the queries return ans;}// Driver codeint main(){ int N = 5, Q = 3; vector<vector<int> > arr = { { 1, 2 }, { 3, 2 }, { 4, 5 }, { 7, 1 }, { 10, 4 } }; vector<vector<int> > queries = { { 0, 12 }, { 4, 6 }, { 2, 8 } }; // Function call vector<long long> ans = MaximumValue(N, Q, arr, queries); for (int x : ans) cout << x << " "; return 0;} |
Java
// java code to implement the approachimport java.io.*;import java.util.*;import java.util.Arrays;class GFG { // Function to calculate the sum of elements public static int[] MaximumValue(int n, int q, int[][] arr, int[][] queries) { Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0])); int[] prefixArr = new int[n + 1]; int[] ans = new int[q]; for (int i = 0; i < n; i++) { prefixArr[i + 1] = prefixArr[i] + arr[i][1]; } // Binary search for start for (int i = 0; i < q; i++) { int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE; int l = 0, h = n - 1; while (l <= h) { int mid = l + (h - l) / 2; if (arr[mid][0] >= queries[i][0]) { start = Math.min(start, mid); h = mid - 1; } else l = mid + 1; } // Binary search for end l = 0; h = n - 1; while (l <= h) { int mid = l + (h - l) / 2; if (arr[mid][0] <= queries[i][1]) { end = Math.max(end, mid); l = mid + 1; } else h = mid - 1; } if (end + 1 < 0 || start >= prefixArr.length) { ans[i] = 0; } else ans[i] = prefixArr[end + 1] - prefixArr[start]; } // Return the answers for all the queries return ans; } public static void main(String[] args) { int N = 5, Q = 3; int[][] arr = { { 1, 2 }, { 3, 2 }, { 4, 5 }, { 7, 1 }, { 10, 4 } }; int[][] queries = { { 0, 12 }, { 4, 6 }, { 2, 8 } }; // Function call int[] ans = MaximumValue(N, Q, arr, queries); for (int x : ans) System.out.print(x + " "); }}// This code is contributed by ksam24000 |
Python3
# python3 code to implement the approachINT_MAX = +2147483647INT_MIN = -2147483648# Function to calculate the sum of elementsdef MaximumValue(n, q, arr, queries): arr.sort() prefixArr = [0 for _ in range(n + 1)] ans = [0 for _ in range(q)] for i in range(0, n): prefixArr[i + 1] = prefixArr[i] + arr[i][1] # Binary search for start for i in range(0, q): start = INT_MAX end = INT_MIN l = 0 h = n - 1 while (l <= h): mid = l + (h - l) // 2 if (arr[mid][0] >= queries[i][0]): start = min(start, mid) h = mid - 1 else: l = mid + 1 # Binary search for end l = 0 h = n - 1 while (l <= h): mid = l + (h - l) // 2 if (arr[mid][0] <= queries[i][1]): end = max(end, mid) l = mid + 1 else: h = mid - 1 if (end + 1 < 0 or start >= len(prefixArr)): ans[i] = 0 else: ans[i] = prefixArr[end + 1] - prefixArr[start] # Return the answers for all the queries return ans# Driver codeif __name__ == "__main__": N = 5 Q = 3 arr = [ [1, 2], [3, 2], [4, 5], [7, 1], [10, 4] ] queries = [[0, 12], [4, 6], [2, 8]] # Function call ans = MaximumValue(N, Q, arr, queries) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class HelloWorld { public static int cmp(List<int> arr, List<int> b) { if (arr[0] == b[0]) { return 0; } else { return (arr[0] < b[0]) ? -1 : 1; } } // Function to calculate the sum of elements public static List<long> MaximumValue(int n, int q, List<List<int> > arr, List<List<int> > queries) { arr.Sort(cmp); List<long> prefixArr = new List<long>(); for (int i = 0; i < n + 1; i++) { prefixArr.Add(0); } List<long> ans = new List<long>(); for (int i = 0; i < q; i++) { ans.Add(0); } for (int i = 0; i < n; i++) { prefixArr[i + 1] = prefixArr[i] + arr[i][1]; } // Binary search for start for (int i = 0; i < q; i++) { int start = Int32.MaxValue, end = Int32.MinValue; int l = 0; int h = n - 1; while (l <= h) { int mid = l + (h - l) / 2; if (arr[mid][0] >= queries[i][0]) { start = Math.Min(start, mid); h = mid - 1; } else l = mid + 1; } // Binary search for end l = 0; h = n - 1; while (l <= h) { int mid = l + (h - l) / 2; if (arr[mid][0] <= queries[i][1]) { end = Math.Max(end, mid); l = mid + 1; } else h = mid - 1; } if (end + 1 < 0 || start >= prefixArr.Count) { ans[i] = 0; } else ans[i] = prefixArr[end + 1] - prefixArr[start]; } // Return the answers for all the queries return ans; } // Driver code public static void Main(string[] args) { int N = 5, Q = 3; List<List<int> > arr = new List<List<int> >(); List<int> a1 = new List<int>(); a1.Add(1); a1.Add(2); arr.Add(a1); List<int> a2 = new List<int>(); a2.Add(3); a2.Add(2); arr.Add(a2); List<int> a3 = new List<int>(); a3.Add(4); a3.Add(5); arr.Add(a3); List<int> a4 = new List<int>(); a4.Add(7); a4.Add(1); arr.Add(a4); List<int> a5 = new List<int>(); a5.Add(10); a5.Add(4); arr.Add(a5); List<List<int> > queries = new List<List<int> >(); List<int> m1 = new List<int>(); m1.Add(0); m1.Add(12); queries.Add(m1); List<int> m2 = new List<int>(); m2.Add(4); m2.Add(6); queries.Add(m2); List<int> m3 = new List<int>(); m3.Add(2); m3.Add(8); queries.Add(m3); // Function call List<long> ans = MaximumValue(N, Q, arr, queries); for (int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + " "); } }}// This code is contributed by adityamaharshi21 |
Javascript
// JS code to implement the approachfunction sortFunction(arr, b) { if (arr[0] === b[0]) { return 0; } else { return (arr[0] < b[0]) ? -1 : 1; }}// Function to calculate the sum of elementsfunction MaximumValue(n,q,arr,queries){ arr.sort(sortFunction); let prefixArr= Array(n+1).fill(0); //(n + 1); let ans= Array(q).fill(0); for (let i = 0; i < n; i++) { prefixArr[i + 1] = prefixArr[i] + arr[i][1]; } // Binary search for start for (let i = 0; i < q; i++) { let start = Number.MAX_VALUE, end = Number.MIN_VALUE; let l = 0, h = n - 1; while (l <= h) { let mid = l + Math.floor((h - l) / 2); if (arr[mid][0] >= queries[i][0]) { start = Math.min(start, mid); h = mid - 1; } else l = mid + 1; } // Binary search for end l = 0, h = n - 1; while (l <= h) { let mid = l + Math.floor((h - l) / 2); if (arr[mid][0] <= queries[i][1]) { end = Math.max(end, mid); l = mid + 1; } else h = mid - 1; } if (end + 1 < 0 || start >= prefixArr.length) { ans[i] = 0; } else ans[i] = prefixArr[end + 1] - prefixArr[start]; } // Return the answers for all the queries return ans;}// Driver code let N = 5, Q = 3; let arr = [ [ 1, 2 ], [ 3, 2 ], [ 4, 5 ], [ 7, 1 ], [ 10, 4 ] ]; let queries = [ [0, 12 ], [ 4, 6 ], [ 2, 8 ] ]; // Function call let ans = MaximumValue(N, Q, arr, queries); for (let x=0;x<ans.length;x++){ console.log(ans[x]); } // This code is contributed by ksam24000 |
Output
14 5 8
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
