Print modified array after performing queries to add (i β L + 1) to each element present in the range [L, R]
Given an array arr[] consisting of N 0s (1-based indexing) and another array query[], with each row of the form {L, R}, the task for each query (L, R) is to add a value of (i β L + 1) over the range [L, R] and print the array arr[] obtained after performing all the queries.
Examples:
Input: arr[] = {0, 0, 0}, query[][] = {{1, 3}, {2, 3}}
Output: 1 3 5
Explanation: Initially the array is {0, 0, 0}.
Query 1: Range of indices involved: [1, 3]. The value (i β 1 + 1) for each index i in the range is {1, 2, 3}. Adding these values modifies the array to {1, 2, 3}.
Query 2: Range of indices involved: [2, 3]. The value (i β 2 + 1) for each index i in the range is {0, 1, 2}. Adding these values modifies the array to {1, 3, 5}.
Therefore, the modified array is {1, 3, 5}.Input: arr[] = {0, 0, 0, 0, 0, 0, 0}, query[][] = {{1, 7}, {3, 6}, {4, 5}}
Output: 1 2 4 7 10 10 7
Naive Approach: The simplest approach to solve the given problem is to traverse the given array over the range [L, R] and add the value (i β L + 1) to each element in the range for every query. After completing all the queries, print the modified array obtained arr[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to perform the given queries // in the given empty array of size N void updateQuery(vector<vector< int > > queries, int N) { // Initialize an array a[] vector< int > a(N + 1, 0); // Stores the size of the array int n = N + 1; int q = queries.size(); // Traverse the queries for ( int i = 0; i < q; i++) { // Starting index int l = queries[i][0]; // Ending index int r = queries[i][1]; // Increment each index from L to // R in a[] by (j - l + 1) for ( int j = l; j <= r; j++) { a[j] += (j - l + 1); } } // Print the modified array for ( int i = 1; i <= N; i++) { cout << a[i] << " " ; } } // Driver Code int main() { int N = 7; vector<vector< int > > queries = { { 1, 7 }, { 3, 6 }, { 4, 5 } }; // Function Call updateQuery(queries, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to perform the given queries // in the given empty array of size N static void updateQuery( int [][]queries, int N) { // Initialize an array a[] ArrayList<Integer> a = new ArrayList<Integer>(); for ( int i = 0 ; i < N + 1 ; i++) a.add( 0 ); // Stores the size of the array int q = 3 ; // Traverse the queries for ( int i = 0 ; i < q; i++) { // Starting index int l = queries[i][ 0 ]; // Ending index int r = queries[i][ 1 ]; // Increment each index from L to // R in a[] by (j - l + 1) for ( int j = l; j <= r; j++) { a.set(j, a.get(j)+(j - l + 1 )); } } // Print the modified array for ( int i = 1 ; i < a.size(); i++) { System.out.print(a.get(i) + " " ); } } // Driver code public static void main(String[] args) { int N = 7 ; int [][] queries = { { 1 , 7 }, { 3 , 6 }, { 4 , 5 } }; // Function Call updateQuery(queries, N); } } // This code is contributed by offbeat |
Python3
# Python 3 program for the above approach # Function to perform the given queries # in the given empty array of size N def updateQuery(queries, N): # Initialize an array a[] a = [ 0 for i in range (N + 1 )] # Stores the size of the array n = N + 1 q = len (queries) # Traverse the queries for i in range (q): # Starting index l = queries[i][ 0 ] # Ending index r = queries[i][ 1 ] # Increment each index from L to # R in a[] by (j - l + 1) for j in range (l, r + 1 , 1 ): a[j] + = (j - l + 1 ) # Print the modified array for i in range ( 1 , N + 1 , 1 ): print (a[i], end = " " ) # Driver Code if __name__ = = '__main__' : N = 7 queries = [[ 1 , 7 ],[ 3 , 6 ],[ 4 , 5 ]] # Function Call updateQuery(queries, N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to perform the given queries // in the given empty array of size N static void updateQuery( int [,]queries, int N) { // Initialize an array a[] List< int > a = new List< int >(); for ( int i = 0; i < N + 1; i++) a.Add(0); // Stores the size of the array int q = 3; // Traverse the queries for ( int i = 0; i < q; i++) { // Starting index int l = queries[i, 0]; // Ending index int r = queries[i, 1]; // Increment each index from L to // R in a[] by (j - l + 1) for ( int j = l; j <= r; j++) { a[j] += (j - l + 1); } } // Print the modified array for ( int i = 1; i < a.Count; i++) { Console.Write(a[i] + " " ); } } // Driver Code public static void Main() { int N = 7; int [,] queries = new int [3, 2] { { 1, 7 }, { 3, 6 }, { 4, 5 } }; // Function Call updateQuery(queries, N); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // JavaScript program for the above approach // Function to perform the given queries // in the given empty array of size N function updateQuery(queries, N) { // Initialize an array a[] let a = new Array(N + 1).fill(0); // Stores the size of the array let n = N + 1; let q = queries.length; // Traverse the queries for (let i = 0; i < q; i++) { // Starting index let l = queries[i][0]; // Ending index let r = queries[i][1]; // Increment each index from L to // R in a[] by (j - l + 1) for (let j = l; j <= r; j++) { a[j] += (j - l + 1); } } // Print the modified array for (let i = 1; i <= N; i++) { document.write(a[i], " " ); } } // Driver Code let N = 7; let queries = [ [ 1, 7 ], [ 3, 6 ], [ 4, 5 ] ]; // Function Call updateQuery(queries, N); // This code is contributed by </script> |
1 2 4 7 10 10 7
Time Complexity: O(N*Q)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by using the Prefix Sum. Follow the steps below to solve this problem:
- Initialize an array ans[] with all elements as 0 to stores the number of times the current index is affected by the queries.
- Initialize an array res[] with all elements as 0 to stores the value to be deleted after the end of a certain query range is reached.
- Traverse the given array of queries query[] and perform the following steps:
- Add the 1 to ans[query[i][0]] and subtract 1 from ans[query[i][1] + 1].
- Subtract (query[i][1] β query[i][0] + 1) from res[query[i][1] + 1].
- Find the prefix sum of the array ans[].
- Traverse the array res[] and update each element res[i] as res[i] + res[i β 1] + ans[i].
- After completing the above steps, print the array res[] as the modified array after performing the given queries.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to perform the given queries // in the given empty array of size N void updateQuery(vector<vector< int > > queries, int N) { // Stores the resultant array // and the difference array vector< int > ans(N + 2, 0), res(N + 2, 0); int q = queries.size(); // Traverse the given queries for ( int i = 0; i < q; i++) { // Starting index int l = queries[i][0]; // Ending index int r = queries[i][1]; // Increment l-th index by 1 ans[l]++; // Decrease r-th index by 1 ans[r + 1]--; // Decrease (r + 1)th index by // the length of each query res[r + 1] -= (r - l + 1); } // Find the prefix sum of ans[] for ( int i = 1; i <= N; i++) ans[i] += ans[i - 1]; // Find the final array for ( int i = 1; i <= N; i++) res[i] += res[i - 1] + ans[i]; // Printing the modified array for ( int i = 1; i <= N; i++) { cout << res[i] << " " ; } cout << "\n" ; } // Driver Code int main() { int N = 7; vector<vector< int > > queries = { { 1, 7 }, { 3, 6 }, { 4, 5 } }; updateQuery(queries, N); return 0; } |
Java
// JAVA program for the above approach import java.util.*; class GFG { // Function to perform the given queries // in the given empty array of size N public static void updateQuery(ArrayList<ArrayList<Integer> > queries, int N) { // Stores the resultant array // and the difference array int ans[] = new int [N + 2 ]; int res[] = new int [N + 2 ]; for ( int i = 0 ; i < N + 2 ; i++) { ans[i] = 0 ; res[i] = 0 ; } int q = queries.size(); // Traverse the given queries for ( int i = 0 ; i < q; i++) { // Starting index int l = queries.get(i).get( 0 ); // Ending index int r = queries.get(i).get( 1 ); // Increment l-th index by 1 ans[l]++; // Decrease r-th index by 1 ans[r + 1 ]--; // Decrease (r + 1)th index by // the length of each query res[r + 1 ] -= (r - l + 1 ); } // Find the prefix sum of ans[] for ( int i = 1 ; i <= N; i++) ans[i] += ans[i - 1 ]; // Find the final array for ( int i = 1 ; i <= N; i++) res[i] += res[i - 1 ] + ans[i]; // Printing the modified array for ( int i = 1 ; i <= N; i++) { System.out.print(res[i] + " " ); } System.out.println(); } // Driver Code public static void main(String[] args) { int N = 7 ; ArrayList<ArrayList<Integer> > queries = new ArrayList<ArrayList<Integer> >(); ArrayList<Integer> temp1 = new ArrayList<Integer>(Arrays.asList( 1 , 7 )); ArrayList<Integer> temp2 = new ArrayList<Integer>(Arrays.asList( 3 , 6 )); ArrayList<Integer> temp3 = new ArrayList<Integer>(Arrays.asList( 4 , 5 )); queries.add(temp1); queries.add(temp2); queries.add(temp3); updateQuery(queries, N); } } // This code is contributed by Taranpreet. |
Python3
# Python 3 program for the above approach # Function to perform the given queries # in the given empty array of size N def updateQuery(queries, N): # Stores the resultant array # and the difference array ans = [ 0 ] * (N + 2 ) res = [ 0 ] * (N + 2 ) q = len (queries) # Traverse the given queries for i in range (q): # Starting index l = queries[i][ 0 ] # Ending index r = queries[i][ 1 ] # Increment l-th index by 1 ans[l] + = 1 # Decrease r-th index by 1 ans[r + 1 ] - = 1 # Decrease (r + 1)th index by # the length of each query res[r + 1 ] - = (r - l + 1 ) # Find the prefix sum of ans[] for i in range ( 1 , N + 1 ): ans[i] + = ans[i - 1 ] # Find the final array for i in range ( 1 , N + 1 ): res[i] + = res[i - 1 ] + ans[i] # Printing the modified array for i in range ( 1 , N + 1 ): print (res[i], end = " " ) print ( "\n" ) # Driver Code if __name__ = = '__main__' : N = 7 queries = [[ 1 , 7 ], [ 3 , 6 ], [ 4 , 5 ]] updateQuery(queries, N) # This code is contributed by Anvesh Govind Saxena |
C#
using System; using System.Collections.Generic; class GFG { static void UpdateQuery(List<List< int >> queries, int N) { int [] ans = new int [N + 2]; int [] res = new int [N + 2]; for ( int i = 0; i < N + 2; i++) { ans[i] = 0; res[i] = 0; } int q = queries.Count; for ( int i = 0; i < q; i++) { int l = queries[i][0]; int r = queries[i][1]; ans[l]++; ans[r + 1]--; res[r + 1] -= (r - l + 1); } for ( int i = 1; i <= N; i++) ans[i] += ans[i - 1]; for ( int i = 1; i <= N; i++) res[i] += res[i - 1] + ans[i]; for ( int i = 1; i <= N; i++) { Console.Write(res[i] + " " ); } Console.WriteLine(); } static void Main( string [] args) { int N = 7; List<List< int >> queries = new List<List< int >>(); List< int > temp1 = new List< int >( new int [] { 1, 7 }); List< int > temp2 = new List< int >( new int [] { 3, 6 }); List< int > temp3 = new List< int >( new int [] { 4, 5 }); queries.Add(temp1); queries.Add(temp2); queries.Add(temp3); UpdateQuery(queries, N); } } // This code is contributed by aadityaburujwale. |
Javascript
// Javascript program for the above approach // Function to perform the given queries // in the given empty array of size N function updateQuery(queries, N) { // Stores the resultant array // and the difference array let ans = Array(N + 2).fill(0), res = Array(N + 2).fill(0); let q = queries.length; // Traverse the given queries for (let i = 0; i < q; i++) { // Starting index let l = queries[i][0]; // Ending index let r = queries[i][1]; // Increment l-th index by 1 ans[l]++; // Decrease r-th index by 1 ans[r + 1]--; // Decrease (r + 1)th index by // the length of each query res[r + 1] -= r - l + 1; } // Find the prefix sum of ans[] for (let i = 1; i <= N; i++) ans[i] += ans[i - 1]; // Find the final array for (let i = 1; i <= N; i++) res[i] += res[i - 1] + ans[i]; // Printing the modified array console.log(res.slice(1, N + 1).join( " " )); } // Testing the function let N = 7; let queries = [ [1, 7], [3, 6], [4, 5], ]; updateQuery(queries, N); // Contributed by prajwalkandekar123 |
1 2 4 7 10 10 7
Time Complexity: O(N)
Auxiliary Space: O(N)