Given an array arr[] of size N and a 2D array Q[][] consisting of queries of the following two types:
- 1 X Y: Update the array element at index X with Y.
- 2 K: Print the position of the first array element greater than or equal to K. If there is no such index, then print -1.
Examples:
Input : arr[] = { 1, 3, 2, 4, 6 }, Q[][] = {{2, 5}, {1, 3, 5}, {2, 4}, {2, 8}}
Output: 5 3 -1
Explanation:
Query1: Since arr[4] > 5, the position of arr[4] is 5.
Query2: Updating arr[2] with 5 modifies arr[] to {1, 3, 5, 4, 6}
Query3: Since arr[2] > 4, the position of arr[4] is 5.
Query4: No array element is greater than 8.Input : arr[] = {1, 2, 3}, N = 3, Q[][] = {{2, 2}, {1, 3, 5}, {2, 10}}
Output: 2 -1
Naive Approach: The simplest approach to solve this problem is as follows:
- For a query of type 1, then update arr[X – 1] to Y.
- Otherwise, traverse the array and print the position of the first array element which is greater than or equal to K.
Time Complexity: O(N * |Q|)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using segment tree. The idea is to build and update the tree using the concept of Range Maximum Query with Node Update. Follow the steps below to solve the problem:
- Build a segment tree with each node consisting of the maximum of its subtree.
- Update operation can be performed by using the concept of Range Maximum Query with Node Update
- Position of the first array element which is greater than or equal to K can be found by recursively checking for the following conditions:
- Check if the root of the left subtree is greater than or equal to K or not. If found to be true, then find the position from the left subtree. If no such array element is found in the left subtree, then recursively find the position in the right subtree.
- Otherwise, recursively find the position in the right subtree.
- Finally, print the position of an array element which is greater than or equal to K.
Below is the implementation of the above approach :
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the mid// of start and endint getMid(int s, int e) { return s + (e - s) / 2; }// Function to update nodes at position indexvoid updateValue(int arr[], int* st, int ss, int se, int index, int value, int node){ // If index is out of range if (index < ss || index > se) { cout << "Invalid Input" << endl; return; } // If a leaf node is found if (ss == se) { // update value in array arr[index] = value; // Update value in // the segment tree st[node] = value; } else { // Stores mid of ss and se int mid = getMid(ss, se); // If index is less than or // equal to mid if (index >= ss && index <= mid) { // Recursively call for left subtree updateValue(arr, st, ss, mid, index, value, 2 * node + 1); } else { // Recursively call for right subtree updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2); } // Update st[node] st[node] = max(st[2 * node + 1], st[2 * node + 2]); } return;}// Function to find the position of first element// which is greater than or equal to Xint findMinimumIndex(int* st, int ss, int se, int K, int si){ // If no such element found in current // subtree which is greater than or // equal to K if (st[si] < K) return 1e9; // If current node is leaf node if (ss == se) { // If value of current node // is greater than or equal to X if (st[si] >= K) { return ss; } return 1e9; } // Stores mid of ss and se int mid = getMid(ss, se); int l = 1e9; // If root of left subtree is // greater than or equal to K if (st[2 * si + 1] >= K) l = min(l, findMinimumIndex(st, ss, mid, K, 2 * si + 1)); // If no such array element is // found in the left subtree if (l == 1e9 && st[2 * si + 2] >= K) l = min(l, findMinimumIndex(st, mid + 1, se, K, 2 * si + 2)); return l;}// Function to build a segment treeint Build(int arr[], int ss, int se, int* st, int si){ // If current node is leaf node if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // store mid of ss and se int mid = getMid(ss, se); // Stores maximum of left subtree and rightsubtree st[si] = max(Build(arr, ss, mid, st, si * 2 + 1), Build(arr, mid + 1, se, st, si * 2 + 2)); return st[si];}// Function to initialize a segment tree// for the given arrayint* constructST(int arr[], int n){ // Height of segment tree int x = (int)(ceil(log2(n))); // Maximum size of segment tree int max_size = 2 * (int)pow(2, x) - 1; // Allocate memory int* st = new int[max_size]; // Fill the allocated memory st Build(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st;}// Function to perform the queries of// the given typevoid PerformQueries(int arr[], int N, vector<vector<int> > Q){ // Build segment tree for the given array int* st = constructST(arr, N); // Traverse the query array for (int i = 0; i < Q.size(); i++) { // If query of type 1 found if (Q[i][0] == 1) updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5, 0); else { // Stores index of first array element // which is greater than or equal // to Q[i][1] int f = findMinimumIndex(st, 0, N - 1, Q[i][1], 0); if (f < N) cout << f + 1 << " "; else cout << -1 << " "; } }}// Driver Codeint main(){ int arr[] = { 1, 3, 2, 4, 6 }; vector<vector<int> > Q{ { 2, 5 }, { 1, 3, 5 }, { 2, 4 }, { 2, 8 } }; int N = sizeof(arr) / sizeof(arr[0]); PerformQueries(arr, N, Q); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG { // Function to find the mid // of start and end static int getMid(int s, int e) { return s + (e - s) / 2; } static void updateValue(int arr[], int[] st, int ss, int se, int index, int value, int node) { // If index is out of range if (index < ss || index > se) { System.out.println("Invalid Input"); return; } // If a leaf node is found if (ss == se) { // update value in array arr[index] = value; // Update value in // the segment tree st[node] = value; } else { // Stores mid of ss and se int mid = getMid(ss, se); // If index is less than or // equal to mid if (index >= ss && index <= mid) { // Recursively call for left subtree updateValue(arr, st, ss, mid, index, value, 2 * node + 1); } else { // Recursively call for right subtree updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2); } // Update st[node] st[node] = Math.max(st[2 * node + 1], st[2 * node + 2]); } } // Function to find the position of first element // which is greater than or equal to X static int findMinimumIndex(int[] st, int ss, int se, int K, int si) { // If no such element found in current // subtree which is greater than or // equal to K if (st[si] < K) return 1000000000; // If current node is leaf node if (ss == se) { // If value of current node // is greater than or equal to X if (st[si] >= K) { return ss; } return 1000000000; } // Stores mid of ss and se int mid = getMid(ss, se); int l = 1000000000; // If root of left subtree is // greater than or equal to K if (st[2 * si + 1] >= K) l = Math.min(l, findMinimumIndex(st, ss, mid, K, 2 * si + 1)); // If no such array element is // found in the left subtree if (l == 1e9 && st[2 * si + 2] >= K) l = Math.min(l, findMinimumIndex(st, mid + 1, se, K, 2 * si + 2)); return l; } // Function to build a segment tree static int Build(int arr[], int ss, int se, int[] st, int si) { // If current node is leaf node if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // store mid of ss and se int mid = getMid(ss, se); // Stores maximum of left subtree and rightsubtree st[si] = Math.max( Build(arr, ss, mid, st, si * 2 + 1), Build(arr, mid + 1, se, st, si * 2 + 2)); return st[si]; } // Function to initialize a segment tree // for the given array static int[] constructST(int arr[], int n) { // Height of segment tree int x = (int)Math.ceil(Math.log(n) / Math.log(2)); // Maximum size of segment tree int max_size = 2 * (int)Math.pow(2, x) - 1; // Allocate memory int[] st = new int[max_size]; // Fill the allocated memory st Build(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st; } static void PerformQueries(int arr[], int N, int[][] Q) { // Build segment tree for the given array int[] st = constructST(arr, N); // Traverse the query array for (int i = 0; i < Q.length; i++) { // If query of type 1 found if (Q[i][0] == 1) updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5, 0); else { // Stores index of first array element // which is greater than or equal // to Q[i][1] int f = findMinimumIndex(st, 0, N - 1, Q[i][1], 0); if (f < N) System.out.print(f + 1 + " "); else System.out.print(-1 + " "); } } } // Driver Code public static void main(String[] args) { int arr[] = { 1, 3, 2, 4, 6 }; int[][] Q = { { 2, 5 }, { 1, 3, 5 }, { 2, 4 }, { 2, 8 } }; int N = arr.length; PerformQueries(arr, N, Q); }}// This code is contributed by hemanthsawarna1506 |
Python3
# Python3 program to implement# the above approachimport math# Function to find the mid# of start and enddef getMid(s,e): return s + math.floor((e - s) / 2) def updateValue(arr,st,ss,se,index,value,node): # If index is out of range if (index < ss or index > se): print("Invalid Input") return # If a leaf node is found if (ss == se): # update value in array arr[index] = value # Update value in # the segment tree st[node] = value else: # Stores mid of ss and se mid = getMid(ss, se) # If index is less than or # equal to mid if (index >= ss and index <= mid): # Recursively call for left subtree updateValue(arr, st, ss, mid, index, value, 2 * node + 1) else: # Recursively call for right subtree updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2) # Update st[node] st[node] = max(st[2 * node + 1], st[2 * node + 2]) # Function to find the position of first element# which is greater than or equal to Xdef findMinimumIndex(st, ss, se, K, si): # If no such element found in current # subtree which is greater than or # equal to K if (st[si] < K): return 1000000000 # If current node is leaf node if (ss == se): # If value of current node # is greater than or equal to X if (st[si] >= K): return ss return 1000000000 # Stores mid of ss and se mid = getMid(ss, se) l = 1000000000 # If root of left subtree is # greater than or equal to K if (st[2 * si + 1] >= K): l = min(l, findMinimumIndex(st, ss, mid, K, 2 * si + 1)) # If no such array element is # found in the left subtree if (l == 1e9 and st[2 * si + 2] >= K): l = min(l, findMinimumIndex(st, mid + 1, se, K, 2 * si + 2)) return l # Function to build a segment treedef Build(arr, ss, se, st, si): # If current node is leaf node if (ss == se): st[si] = arr[ss] return arr[ss] # store mid of ss and se mid = getMid(ss, se) # Stores maximum of left subtree and rightsubtree st[si] = max(Build(arr, ss, mid, st, si * 2 + 1), Build(arr, mid + 1, se, st, si * 2 + 2)) return st[si] # Function to initialize a segment tree# for the given arraydef constructST(arr,n): # Height of segment tree x = math.ceil(math.log(n) / math.log(2)) # Maximum size of segment tree max_size = 2 * pow(2, x) - 1 # Allocate memory st = [0]*(max_size) # Fill the allocated memory st Build(arr, 0, n - 1, st, 0) # Return the constructed segment tree return st def PerformQueries(arr, N, Q): # Build segment tree for the given array st = constructST(arr, N) # Traverse the query array for i in range(len(Q)): # If query of type 1 found if (Q[i][0] == 1): updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5, 0) else: # Stores index of first array element # which is greater than or equal # to Q[i][1] f = findMinimumIndex(st, 0, N - 1, Q[i][1], 0) if (f < N): print((f + 1 ), end = " ") else: print(-1, end = " ")# Driver codearr = [1, 3, 2, 4, 6 ]Q= [[ 2, 5 ], [ 1, 3, 5 ], [2, 4 ], [ 2, 8 ]]N = len(arr)PerformQueries(arr, N, Q)# This code is contributed by decode2207. |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the mid// of start and endstatic int getMid(int s, int e){ return s + (e - s) / 2;}static void updateValue(int[] arr, int[] st, int ss, int se, int index, int value, int node){ // If index is out of range if (index < ss || index > se) { Console.WriteLine("Invalid Input"); return; } // If a leaf node is found if (ss == se) { // Update value in array arr[index] = value; // Update value in // the segment tree st[node] = value; } else { // Stores mid of ss and se int mid = getMid(ss, se); // If index is less than or // equal to mid if (index >= ss && index <= mid) { // Recursively call for left subtree updateValue(arr, st, ss, mid, index, value, 2 * node + 1); } else { // Recursively call for right subtree updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2); } // Update st[node] st[node] = Math.Max(st[2 * node + 1], st[2 * node + 2]); }}// Function to find the position of first element// which is greater than or equal to Xstatic int findMinimumIndex(int[] st, int ss, int se, int K, int si){ // If no such element found in current // subtree which is greater than or // equal to K if (st[si] < K) return 1000000000; // If current node is leaf node if (ss == se) { // If value of current node // is greater than or equal to X if (st[si] >= K) { return ss; } return 1000000000; } // Stores mid of ss and se int mid = getMid(ss, se); int l = 1000000000; // If root of left subtree is // greater than or equal to K if (st[2 * si + 1] >= K) l = Math.Min(l, findMinimumIndex(st, ss, mid, K, 2 * si + 1)); // If no such array element is // found in the left subtree if (l == 1e9 && st[2 * si + 2] >= K) l = Math.Min(l, findMinimumIndex(st, mid + 1, se, K, 2 * si + 2)); return l;}// Function to build a segment treestatic int Build(int[] arr, int ss, int se, int[] st, int si){ // If current node is leaf node if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // Store mid of ss and se int mid = getMid(ss, se); // Stores maximum of left subtree and rightsubtree st[si] = Math.Max( Build(arr, ss, mid, st, si * 2 + 1), Build(arr, mid + 1, se, st, si * 2 + 2)); return st[si];}// Function to initialize a segment tree// for the given arraystatic int[] constructST(int[] arr, int n){ // Height of segment tree int x = (int)Math.Ceiling(Math.Log(n) / Math.Log(2)); // Maximum size of segment tree int max_size = 2 * (int)Math.Pow(2, x) - 1; // Allocate memory int[] st = new int[max_size]; // Fill the allocated memory st Build(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st;}static void PerformQueries(int[] arr, int N, int[][] Q){ // Build segment tree for the given array int[] st = constructST(arr, N); // Traverse the query array for(int i = 0; i < Q.Length; i++) { // If query of type 1 found if (Q[i][0] == 1) updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5, 0); else { // Stores index of first array element // which is greater than or equal // to Q[i][1] int f = findMinimumIndex(st, 0, N - 1, Q[i][1], 0); if (f < N) Console.Write(f + 1 + " "); else Console.Write(-1 + " "); } }}// Driver Codepublic static void Main(string[] args){ int[] arr = { 1, 3, 2, 4, 6 }; int[][] Q = new int[4][]; // Initialize the elements Q[0] = new int[] { 2, 5 }; Q[1] = new int[] { 1, 3, 5 }; Q[2] = new int[] { 2, 4 }; Q[3] = new int[] { 2, 8 }; int N = arr.Length; PerformQueries(arr, N, Q);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the mid// of start and endfunction getMid(s,e){ return s + Math.floor((e - s) / 2);}function updateValue(arr,st,ss,se,index,value,node){ // If index is out of range if (index < ss || index > se) { document.write("Invalid Input<br>"); return; } // If a leaf node is found if (ss == se) { // update value in array arr[index] = value; // Update value in // the segment tree st[node] = value; } else { // Stores mid of ss and se let mid = getMid(ss, se); // If index is less than or // equal to mid if (index >= ss && index <= mid) { // Recursively call for left subtree updateValue(arr, st, ss, mid, index, value, 2 * node + 1); } else { // Recursively call for right subtree updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2); } // Update st[node] st[node] = Math.max(st[2 * node + 1], st[2 * node + 2]); }}// Function to find the position of first element// which is greater than or equal to Xfunction findMinimumIndex(st,ss,se,K,si){ // If no such element found in current // subtree which is greater than or // equal to K if (st[si] < K) return 1000000000; // If current node is leaf node if (ss == se) { // If value of current node // is greater than or equal to X if (st[si] >= K) { return ss; } return 1000000000; } // Stores mid of ss and se let mid = getMid(ss, se); let l = 1000000000; // If root of left subtree is // greater than or equal to K if (st[2 * si + 1] >= K) l = Math.min(l, findMinimumIndex(st, ss, mid, K, 2 * si + 1)); // If no such array element is // found in the left subtree if (l == 1e9 && st[2 * si + 2] >= K) l = Math.min(l, findMinimumIndex(st, mid + 1, se, K, 2 * si + 2)); return l;}// Function to build a segment treefunction Build(arr,ss,se,st,si){ // If current node is leaf node if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // store mid of ss and se let mid = getMid(ss, se); // Stores maximum of left subtree and rightsubtree st[si] = Math.max( Build(arr, ss, mid, st, si * 2 + 1), Build(arr, mid + 1, se, st, si * 2 + 2)); return st[si];}// Function to initialize a segment tree // for the given arrayfunction constructST(arr,n){ // Height of segment tree let x = Math.ceil(Math.log(n) / Math.log(2)); // Maximum size of segment tree let max_size = 2 * Math.pow(2, x) - 1; // Allocate memory let st = new Array(max_size); // Fill the allocated memory st Build(arr, 0, n - 1, st, 0); // Return the constructed segment tree return st;}function PerformQueries(arr,N,Q){ // Build segment tree for the given array let st = constructST(arr, N); // Traverse the query array for (let i = 0; i < Q.length; i++) { // If query of type 1 found if (Q[i][0] == 1) updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5, 0); else { // Stores index of first array element // which is greater than or equal // to Q[i][1] let f = findMinimumIndex(st, 0, N - 1, Q[i][1], 0); if (f < N) document.write((f + 1 )+ " "); else document.write(-1 + " "); } }}// Driver Codelet arr=[1, 3, 2, 4, 6 ];let Q= [[ 2, 5 ], [ 1, 3, 5 ], [2, 4 ], [ 2, 8 ]];let N = arr.length;PerformQueries(arr, N, Q);// This code is contributed by avanitrachhadiya2155</script> |
Output:
5 3 -1
Time Complexity: O(n*log(n) + q*log(n))
Auxiliary Space: O(n*log(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!
