Given an array arr[] consisting of N integers and an array Queries[] consisting of Q queries of the type {X, L, R} to perform following operations:
- If the value of X is 1, then update the array element at Xth index to L.
- Otherwise, find the minimum index j in the range [L, R] such that arr[j] ? X. If no such j exists, then print “-1”.
Examples:
Input: arr[] = {1, 3, 2, 4, 6}, Queries[][] = {{2, 0, 4}, {1, 2, 5}, {4, 0, 4}, {0, 0, 4}}
Output: 1 2 0
Explanation:
Query 1: find(2, 0, 4) => First element which is at least 2 is 3. So, its index is 1.
Query 2: update(2, 5) => arr[] = {1, 3, 5, 4, 6}.
Query 3: find(4, 0, 4) => First element which is at least 4 is 5. So, its index is 2.
Query 4: find(0, 0, 4) => First element which is at least 0 is 1. So, its index is 0.Input: arr[] = {1}, Queries[][] = {{2, 0, 0}};
Output: 1 2 0
Explanation:
Query 1: find(2, 0, 0) => No element is greater than 2. Therefore, print -1.
Naive Approach: The simplest approach is to traverse the array for each query. For the queries of Type 1, update A[X] to L. For the query of Type 2, traverse the array arr[] over the range [L, R] and find the minimum index j satisfying the condition. If no such index is found, then print “-1”.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// index j in the range [L, R]// such that arr[j] ? Xint find(vector<int>& arr, int X, int L, int R){ for (int j = L; j <= R; j++) { if (arr[j] >= X) { return j; } } return -1;}// Function to update the array// element at Xth index to Lvoid update(vector<int>& arr, int X, int L) { arr[X] = L; }// Driver Codeint main(){ vector<int> arr = { 1, 3, 2, 4, 6 }; vector<vector<int> > queries = { { 2, 0, 4 }, { 1, 2, 5 }, { 4, 0, 4 }, { 0, 0, 4 } }; // Iterating on queries for (auto query : queries) { int x = query[0], l = query[1], r = query[2]; if (x == 1) { // Function call for update update(arr, l, r); } else { // Function call for finding // the minimum int j = find(arr, x, l, r); cout << j << endl; } } return 0;} |
Java
// Java program for the above approachimport java.util.ArrayList;import java.util.List;public class Main { // Function to find the minimum // index j in the range [L, R] // such that arr[j] >= X static int find(List<Integer> arr, int X, int L, int R) { for (int j = L; j <= R; j++) { if (arr.get(j) >= X) { return j; } } return -1; } // Function to update the array // element at Xth index to L static void update(List<Integer> arr, int X, int L) { arr.set(X, L); } // Driver Code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add(1); arr.add(3); arr.add(2); arr.add(4); arr.add(6); List<List<Integer>> queries = new ArrayList<>(); queries.add(List.of(2, 0, 4)); queries.add(List.of(1, 2, 5)); queries.add(List.of(4, 0, 4)); queries.add(List.of(0, 0, 4)); // Iterating on queries for (List<Integer> query : queries) { int x = query.get(0); int l = query.get(1); int r = query.get(2); if (x == 1) { // Function call for update update(arr, l, r); } else { // Function call for finding the minimum int j = find(arr, x, l, r); System.out.println(j); } } }} |
Python3
# Python program for the above approach# Function to find the minimum# index j in the range [L, R]# such that arr[j] >= Xdef find(arr, X, L, R): for j in range(L, R + 1): if arr[j] >= X: return j return -1# Function to update the array# element at Xth index to Ldef update(arr, X, L): arr[X] = L# Driver Codeif __name__ == "__main__": arr = [1, 3, 2, 4, 6] queries = [ [2, 0, 4], [1, 2, 5], [4, 0, 4], [0, 0, 4] ] # Iterating on queries for query in queries: x, l, r = query if x == 1: # Function call for update update(arr, l, r) else: # Function call for finding # the minimum j = find(arr, x, l, r) print(j) |
Output
1 2 0
Time Complexity: O(N*Q)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Segment Tree in order to perform queries efficiently. Follow the steps below to solve the problem:
- Construct a Segment Tree where each node will represent the maximum value in the range of that node. For example, for any given range [i, j], its corresponding node will contain the maximum value in that range.
- Initialize a variable, say ans.
- Now, for queries of type 2, if the current range does not lie inside the range [L, R], then traverse its left subtree.
- Now, in the left subtree, if the maximum exceeds X and the current range lies inside the range [L, R], then go to the mid-point of that range and check if its value is greater than X or not. If found to be true, visit its left part. Otherwise, visit its right part.
- Update the variable ans as the minimum index between the given range if it exists.
- Continue the above steps, until the left part of the range becomes equal to the right part.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define maxN 100using namespace std;// Stores nodes value of the Treeint Tree[4 * maxN];// Function to build segment treevoid build(int arr[], int index, int s, int e){ // Base Case if (s == e) Tree[index] = arr[s]; else { // Find the value of mid int m = (s + e) / 2; // Update for left subtree build(arr, 2 * index, s, m); // Update for right subtree build(arr, 2 * index + 1, m + 1, e); // Update the value at the // current index Tree[index] = max(Tree[2 * index], Tree[2 * index + 1]); }}// Function for finding the index// of the first element at least xint atleast_x(int index, int s, int e, int ql, int qr, int x){ // If current range does // not lie in query range if (ql > e || qr < s) return -1; // If current range is inside // of query range if (s <= ql && e <= qr) { // Maximum value in this // range is less than x if (Tree[index] < x) return -1; // Finding index of first // value in this range while (s != e) { int m = (s + e) / 2; // Update the value of // the minimum index if (Tree[2 * index] >= x) { e = m; index = 2 * index; } else { s = m + 1; index = 2 * index + 1; } } return s; } // Find mid of the current range int m = (s + e) / 2; // Left subtree int val = atleast_x(2 * index, s, m, ql, qr, x); if (val != -1) return val; // If it does not lie in // left subtree return atleast_x(2 * index + 1, m + 1, e, ql, qr, x);}// Function for updating segment treevoid update(int index, int s, int e, int new_val, int pos){ // Update the value, we // reached leaf node if (s == e) Tree[index] = new_val; else { // Find the mid int m = (s + e) / 2; if (pos <= m) { // If pos lies in the // left subtree update(2 * index, s, m, new_val, pos); } else { // pos lies in the // right subtree update(2 * index + 1, m + 1, e, new_val, pos); } // Update the maximum value // in the range Tree[index] = max(Tree[2 * index], Tree[2 * index + 1]); }}// Function to print the answer// for the given queriesvoid printAnswer(int* arr, int n){ // Build segment tree build(arr, 1, 0, n - 1); // Find index of first value // atleast 2 in range [0, n-1] cout << atleast_x(1, 0, n - 1, 0, n - 1, 2) << "\n"; // Update value at index 2 to 5 arr[2] = 5; update(1, 0, n - 1, 5, 2); // Find index of first value // atleast 4 in range [0, n-1] cout << atleast_x(1, 0, n - 1, 0, n - 1, 4) << "\n"; // Find index of first value // atleast 0 in range [0, n-1] cout << atleast_x(1, 0, n - 1, 0, n - 1, 0) << "\n";}// Driver Codeint main(){ int arr[] = { 1, 3, 2, 4, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call printAnswer(arr, N); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ static int maxN = 100;// Stores nodes value of the Treestatic int Tree[] = new int[4 * maxN];// Function to build segment treestatic void build(int arr[], int index, int s, int e){ // Base Case if (s == e) Tree[index] = arr[s]; else { // Find the value of mid int m = (s + e) / 2; // Update for left subtree build(arr, 2 * index, s, m); // Update for right subtree build(arr, 2 * index + 1, m + 1, e); // Update the value at the // current index Tree[index] = Math.max(Tree[2 * index], Tree[2 * index + 1]); }}// Function for finding the index// of the first element at least xstatic int atleast_x(int index, int s, int e, int ql, int qr, int x){ // If current range does // not lie in query range if (ql > e || qr < s) return -1; // If current range is inside // of query range if (s <= ql && e <= qr) { // Maximum value in this // range is less than x if (Tree[index] < x) return -1; // Finding index of first // value in this range while (s != e) { int m = (s + e) / 2; // Update the value of // the minimum index if (Tree[2 * index] >= x) { e = m; index = 2 * index; } else { s = m + 1; index = 2 * index + 1; } } return s; } // Find mid of the current range int m = (s + e) / 2; // Left subtree int val = atleast_x(2 * index, s, m, ql, qr, x); if (val != -1) return val; // If it does not lie in // left subtree return atleast_x(2 * index + 1, m + 1, e, ql, qr, x);}// Function for updating segment treestatic void update(int index, int s, int e, int new_val, int pos){ // Update the value, we // reached leaf node if (s == e) Tree[index] = new_val; else { // Find the mid int m = (s + e) / 2; if (pos <= m) { // If pos lies in the // left subtree update(2 * index, s, m, new_val, pos); } else { // pos lies in the // right subtree update(2 * index + 1, m + 1, e, new_val, pos); } // Update the maximum value // in the range Tree[index] = Math.max(Tree[2 * index], Tree[2 * index + 1]); }}// Function to print the answer// for the given queriesstatic void printAnswer(int[] arr, int n){ // Build segment tree build(arr, 1, 0, n - 1); // Find index of first value // atleast 2 in range [0, n-1] System.out.println(atleast_x(1, 0, n - 1, 0, n - 1, 2)); // Update value at index 2 to 5 arr[2] = 5; update(1, 0, n - 1, 5, 2); // Find index of first value // atleast 4 in range [0, n-1] System.out.println(atleast_x(1, 0, n - 1, 0, n - 1, 4)); // Find index of first value // atleast 0 in range [0, n-1] System.out.println(atleast_x(1, 0, n - 1, 0, n - 1, 0));} // Driver codepublic static void main(String[] args){ int arr[] = { 1, 3, 2, 4, 6 }; int N = arr.length; // Function Call printAnswer(arr, N);}}// This code is contributed by susmitakundugoaldanga. |
Python3
# Python 3 program for the above approachmaxN = 100# Stores nodes value of the TreeTree = [0 for i in range(4 * maxN)]# Function to build segment treedef build(arr, index, s, e): # Base Case global Tree global max if (s == e): Tree[index] = arr[s] else: # Find the value of mid m = (s + e) // 2 # Update for left subtree build(arr, 2 * index, s, m) # Update for right subtree build(arr, 2 * index + 1, m + 1, e) # Update the value at the # current index Tree[index] = max(Tree[2 * index], Tree[2 * index + 1])# Function for finding the index# of the first element at least xdef atleast_x(index, s, e, ql, qr, x): global Tree global max # If current range does # not lie in query range if (ql > e or qr < s): return -1 # If current range is inside # of query range if (s <= ql and e <= qr): # Maximum value in this # range is less than x if (Tree[index] < x): return -1; # Finding index of first # value in this range while (s != e): m = (s + e) // 2 # Update the value of # the minimum index if (Tree[2 * index] >= x): e = m index = 2 * index else: s = m + 1 index = 2 * index + 1 return s # Find mid of the current range m = (s + e) // 2 # Left subtree val = atleast_x(2 * index, s, m, ql, qr, x) if (val != -1): return val # If it does not lie in # left subtree return atleast_x(2 * index + 1, m + 1,e, ql, qr, x)# Function for updating segment treedef update(index, s, e, new_val, pos): global Tree global max # Update the value, we # reached leaf node if (s == e): Tree[index] = new_val else: # Find the mid m = (s + e) // 2 if (pos <= m): # If pos lies in the # left subtree update(2 * index, s, m,new_val, pos) else: # pos lies in the # right subtree update(2 * index + 1, m + 1, e, new_val, pos) # Update the maximum value # in the range Tree[index] = max(Tree[2 * index], Tree[2 * index + 1])# Function to print the answer# for the given queriesdef printAnswer(arr, n): global Tree global max # Build segment tree build(arr, 1, 0, n - 1) # Find index of first value # atleast 2 in range [0, n-1] print(atleast_x(1, 0, n - 1, 0, n - 1, 2)) # Update value at index 2 to 5 arr[2] = 5 update(1, 0, n - 1, 5, 2) # Find index of first value # atleast 4 in range [0, n-1] print(atleast_x(1, 0, n - 1, 0, n - 1, 4)) # Find index of first value # atleast 0 in range [0, n-1] print(atleast_x(1, 0, n - 1, 0, n - 1, 0))# Driver Codeif __name__ == '__main__': arr = [1, 3, 2, 4, 6] N = len(arr) # Function Call printAnswer(arr, N) # This code is contributed by bgangwar59. |
C#
// C# program to implement // the above approach using System;class GFG { static int maxN = 100;// Stores nodes value of the Treestatic int[] Tree = new int[4 * maxN];// Function to build segment treestatic void build(int[] arr, int index, int s, int e){ // Base Case if (s == e) Tree[index] = arr[s]; else { // Find the value of mid int m = (s + e) / 2; // Update for left subtree build(arr, 2 * index, s, m); // Update for right subtree build(arr, 2 * index + 1, m + 1, e); // Update the value at the // current index Tree[index] = Math.Max(Tree[2 * index], Tree[2 * index + 1]); }}// Function for finding the index// of the first element at least xstatic int atleast_x(int index, int s, int e, int ql, int qr, int x){ // If current range does // not lie in query range if (ql > e || qr < s) return -1; // If current range is inside // of query range if (s <= ql && e <= qr) { // Maximum value in this // range is less than x if (Tree[index] < x) return -1; // Finding index of first // value in this range while (s != e) { int m = (s + e) / 2; // Update the value of // the minimum index if (Tree[2 * index] >= x) { e = m; index = 2 * index; } else { s = m + 1; index = 2 * index + 1; } } return s; } // Find mid of the current range int mm = (s + e) / 2; // Left subtree int val = atleast_x(2 * index, s, mm, ql, qr, x); if (val != -1) return val; // If it does not lie in // left subtree return atleast_x(2 * index + 1, mm + 1, e, ql, qr, x);}// Function for updating segment treestatic void update(int index, int s, int e, int new_val, int pos){ // Update the value, we // reached leaf node if (s == e) Tree[index] = new_val; else { // Find the mid int m = (s + e) / 2; if (pos <= m) { // If pos lies in the // left subtree update(2 * index, s, m, new_val, pos); } else { // pos lies in the // right subtree update(2 * index + 1, m + 1, e, new_val, pos); } // Update the maximum value // in the range Tree[index] = Math.Max(Tree[2 * index], Tree[2 * index + 1]); }}// Function to print the answer// for the given queriesstatic void printAnswer(int[] arr, int n){ // Build segment tree build(arr, 1, 0, n - 1); // Find index of first value // atleast 2 in range [0, n-1] Console.WriteLine(atleast_x(1, 0, n - 1, 0, n - 1, 2)); // Update value at index 2 to 5 arr[2] = 5; update(1, 0, n - 1, 5, 2); // Find index of first value // atleast 4 in range [0, n-1] Console.WriteLine(atleast_x(1, 0, n - 1, 0, n - 1, 4)); // Find index of first value // atleast 0 in range [0, n-1] Console.WriteLine(atleast_x(1, 0, n - 1, 0, n - 1, 0));}// Driver codestatic void Main() { int[] arr = { 1, 3, 2, 4, 6 }; int N = arr.Length; // Function Call printAnswer(arr, N);}}// This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program to implement the above approach let maxN = 100; // Stores nodes value of the Tree let Tree = new Array(4 * maxN); // Function to build segment tree function build(arr, index, s, e) { // Base Case if (s == e) Tree[index] = arr[s]; else { // Find the value of mid let m = parseInt((s + e) / 2, 10); // Update for left subtree build(arr, 2 * index, s, m); // Update for right subtree build(arr, 2 * index + 1, m + 1, e); // Update the value at the // current index Tree[index] = Math.max(Tree[2 * index], Tree[2 * index + 1]); } } // Function for finding the index // of the first element at least x function atleast_x(index, s, e, ql, qr, x) { // If current range does // not lie in query range if (ql > e || qr < s) return -1; // If current range is inside // of query range if (s <= ql && e <= qr) { // Maximum value in this // range is less than x if (Tree[index] < x) return -1; // Finding index of first // value in this range while (s != e) { let m = parseInt((s + e) / 2, 10); // Update the value of // the minimum index if (Tree[2 * index] >= x) { e = m; index = 2 * index; } else { s = m + 1; index = 2 * index + 1; } } return s; } // Find mid of the current range let m = parseInt((s + e) / 2, 10); // Left subtree let val = atleast_x(2 * index, s, m, ql, qr, x); if (val != -1) return val; // If it does not lie in // left subtree return atleast_x(2 * index + 1, m + 1, e, ql, qr, x); } // Function for updating segment tree function update(index, s, e, new_val, pos) { // Update the value, we // reached leaf node if (s == e) Tree[index] = new_val; else { // Find the mid let m = parseInt((s + e) / 2, 10); if (pos <= m) { // If pos lies in the // left subtree update(2 * index, s, m, new_val, pos); } else { // pos lies in the // right subtree update(2 * index + 1, m + 1, e, new_val, pos); } // Update the maximum value // in the range Tree[index] = Math.max(Tree[2 * index], Tree[2 * index + 1]); } } // Function to print the answer // for the given queries function printAnswer(arr, n) { // Build segment tree build(arr, 1, 0, n - 1); // Find index of first value // atleast 2 in range [0, n-1] document.write(atleast_x(1, 0, n - 1, 0, n - 1, 2) + "</br>"); // Update value at index 2 to 5 arr[2] = 5; update(1, 0, n - 1, 5, 2); // Find index of first value // atleast 4 in range [0, n-1] document.write(atleast_x(1, 0, n - 1, 0, n - 1, 4) + "</br>"); // Find index of first value // atleast 0 in range [0, n-1] document.write(atleast_x(1, 0, n - 1, 0, n - 1, 0) + "</br>"); } let arr = [ 1, 3, 2, 4, 6 ]; let N = arr.length; // Function Call printAnswer(arr, N);// This code is contributed by decode2207.</script> |
Output
1 2 0
Time Complexity: O(Q*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!
