Consider an integer sequence S, which is initially empty (i.e. S = {}). Also given are Q queries, each of which is one of the following types:
- 1 a b: Insert a and b into the sequence S.
- 2 a b: In the sequence S, among the elements that are less than or equal to a, print b-th largest element. If no such element exist, print -1.
- 3 a b: In the sequence S, among the elements that are greater than or equal to a, print b-th smallest element. If no such element exist, print -1
The task is to print the final sequence formed after performing all the Q queries.
Examples:
Input: Q = 7, A = {{1, {20, 10}}, {1, {30, 20}}, {3, {15, 1}}, {3, {15, 2}}, {3, {15, 3}}, {3, {15, 4}}, {2, {100, 5}} }
Output: 20, 20, 30, -1, -1
Explanation: Initially sequence S={}.
=> After execution of initial 2 queries, it becomes: {20, 10, 30, 20}.
=> In the sequence, elements greater than 15 are 20, 20 and 30. In 3rd query, we have to print the 1st smallest number greater than or equal to 15 which is 20.
=> Similarly, 2nd and 3rd smallest integer which are greater than 15 are 20 and 30 respectively. Now, 6th query asks us the 4th smallest integer which is greater than or equal to 15. But, there are only 3 integers greater than 15, so we print -1. => The last Query asks us the 5th largest integer in the integers less than or equal to 100. But, there are only 4 integers (10, 20, 20, 30), which are less than or equal to 100. So, we print -1.Input: Q = 6, A = {{1, {5, 7}}, {1, {2, 15}}, {1, {11, 16}}, {3, {14, 2}}, {2, {11, 3}}, {2, {10, 10}} }
Output: 16, 5, -1
Approach: The problem can be solved using binary search and multiset.
- Initialize the sequence as a multiset (say s).
- Iterate through the vector A to process the queries.
- If the query is of type-1, insert both a and b into the multiset.
- If the query is of type-2, we calculate the lower bound of a in s and from that lower bound we decrement b times to get the b-th largest element less than or equal to a.
- If the query is of type-3, we calculate the upper bound of a in s and from that upper bound we increment b times to get the b-th smallest element greater than or equal to a.
- In queries of type-2 or 3, if iterator goes beyond s.begin() or s.end(), print answer to that query as -1. Else, print the answer obtained through above two steps.
Following is the code based on above approach:
C++
// C++ code for Find the sequence after// performing Q queries#include <bits/stdc++.h>using namespace std;// function to perform the given queries on svoid solveQueries(int Q, vector<pair<int, pair<int, int> > >& A){ // initializing variable to store answer // to current query and a multiset of integers int ans; multiset<int> s; // iterating through all queries for (int i = 0; i < Q; i++) { int t, a, b; t = A[i].first; a = A[i].second.first; b = A[i].second.second; // if query is of 1st type, we simply // insert both a and b into our sequence if (t == 1) { s.insert(a); s.insert(b); continue; } // If query is of the second type, we // calculate the lower bound of a // and from that lower bound we decrement // b times to get the bth largest element // less than or equal to a if (t == 2) { ans = 0; auto it = s.upper_bound(a); for (int j = 0; j < b; j++) { if (it == s.begin()) { ans = -1; break; } it--; ans = *it; } } // If query is of the third type, // we calculate the upper bound of a and // from that upper bound we increment b times // to get the bth smallest element greater // than or equal to a else { ans = 0; auto it = s.lower_bound(a); for (int j = 0; j < b; j++) { if (it == s.end()) { ans = -1; break; } ans = *it; it++; } } // printing the answer cout << ans << " "; }}// Driver Codeint main(){ int Q = 7; vector<pair<int, pair<int, int> > > A = { { 1, { 20, 10 } }, { 1, { 30, 20 } }, { 3, { 15, 1 } }, { 3, { 15, 2 } }, { 3, { 15, 3 } }, { 3, { 15, 4 } }, { 2, { 100, 5 } } }; solveQueries(Q, A);} |
Java
// Java code for Find the sequence after// performing Q queriesimport java.util.ArrayList;import java.util.Collections;class Pair<X, Y> { public X first; public Y second; Pair(X first, Y second) { this.first = first; this.second = second; } }class Main{// function to calculate lower bound public static int lowerbound(ArrayList<Integer> arr,int target){ int N = arr.size(); int low=0; for(int i=0;i<N-1;i++){ if(arr.get(i)<target && arr.get(i+1)>=target){ low = i+1; break; } } if(arr.get(0)>target) return 0; return low;}// function to calculate lower bound public static int upperbound(ArrayList<Integer> arr,int target){ int N = arr.size(); int high=N; for(int i=N-1;i>=0;i--){ if(arr.get(i)>=target && arr.get(i-1)<target){ high = i; break; } } if(high == N) return N; return high;}// function to perform the given queries on spublic static String solveQueries(int Q, ArrayList<Pair<Integer, Pair<Integer, Integer>>> A){ // initializing variable to store answer // to current query and a multiset of integers int ans; String ansArray = ""; ArrayList<Integer> s = new ArrayList<>(); // iterating through all queries for (int i = 0; i < Q; i++){ int t = A.get(i).first; int a = A.get(i).second.first; int b = A.get(i).second.second; // if query is of 1st type, we simply // insert both a and b into our sequence if (t == 1) { s.add(a); s.add(b); continue; } Collections.sort(s); // If query is of the second type, we // calculate the lower bound of a // and from that lower bound we decrement // b times to get the bth largest element // less than or equal to a if (t == 2) { ans = 0; int it = upperbound(s,a); for (int j = 0; j < b; j++) { if (it == 0) { ans = -1; break; } it--; ans = s.get(it); } } // If query is of the third type, // we calculate the upper bound of a and // from that upper bound we increment b times // to get the bth smallest element greater // than or equal to a else { ans = 0; int it = lowerbound(s,a); for (int j = 0; j < b; j++) { if (it == s.size()) { ans = -1; break; } ans = s.get(it); it++; } } // printing(storing) the answer ansArray+=ans + " "; } return ansArray;}public static void main(String[] args) {// Driver Codeint Q = 7;ArrayList<Pair<Integer, Pair<Integer, Integer>>> A = new ArrayList<Pair<Integer, Pair<Integer, Integer>>>();A.add(new Pair<>(1, new Pair<>(20, 10)));A.add(new Pair<>(1, new Pair<>(30, 20)));A.add(new Pair<>(3, new Pair<>(15, 1)));A.add(new Pair<>(3, new Pair<>(15, 2)));A.add(new Pair<>(3, new Pair<>(15, 3)));A.add(new Pair<>(3, new Pair<>(15, 4)));A.add(new Pair<>(2, new Pair<>(100, 5)));String ansArray = solveQueries(Q, A);// printing answerSystem.out.println(ansArray); } } |
Python3
# Python code for Find the sequence after# performing Q queries# function to calculate lower bound from xml.dom.minidom import Documentdef lowerbound(arr,target): N = len(arr); low = 0; for i in range(N - 1): if(arr[i] < target and arr[i + 1] >= target): low = i+1; break; if(arr[0] > target): return 0; return low;# function to calculate lower bound def upperbound(arr,target): N = len(arr); high = N; for i in range(N - 1, 0, -1): if(arr[i] >= target and arr[i - 1] < target): high = i; break; if(high == N): return N; return high;# function to perform the given queries on sansArray = "";def solveQueries(Q,A): # initializing variable to store answer # to current query and a multiset of integers s = []; # iterating through all queries for i in range(Q): t = A[i]["first"]; a = A[i]["second"]["first"]; b = A[i]["second"]["second"]; # if query is of 1st type, we simply # insert both a and b into our sequence if (t == 1): s.append(a); s.append(b); continue; s.sort(); # If query is of the second type, we # calculate the lower bound of a # and from that lower bound we decrement # b times to get the bth largest element # less than or equal to a if (t == 2): ans = 0; it = upperbound(s,a); for j in range(b): if (it == 0): ans = -1; break; it -= 1 ans = s[it]; # If query is of the third type, # we calculate the upper bound of a and # from that upper bound we increment b times # to get the bth smallest element greater # than or equal to a else: ans = 0; it = lowerbound(s,a); for j in range(b): if (it == len(s)): ans = -1; break; ans = s[it]; it += 1 # printing(storing) the answer global ansArray ansArray += str(ans) + " "; # Driver CodeQ = 7;A = [ {"first" : 1, "second" : {"first" : 20, "second" : 10} },{"first" : 1, "second" : {"first" : 30, "second" : 20} },{"first" : 3, "second" : {"first" : 15, "second" : 1} },{"first" : 3, "second" : {"first" : 15, "second" : 2} },{"first" : 3, "second" : {"first" : 15, "second" : 3} },{"first" : 3, "second" : {"first" : 15, "second" : 4} },{"first" : 2, "second" : {"first" : 100, "second" : 5} }]solveQueries(Q, A);# printing answerprint(ansArray);# This code is contributed by Saurabh Jaiswal |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;// C# code for Find the sequence after// performing Q queriesclass GFG1 { // function to calculate lower bound public static int lowerbound(List<int> arr,int target) { int N = arr.Count; int low=0; for(int i=0;i<N-1;i++) { if(arr[i]<target && arr[i+1]>=target) { low = i+1; break; } } if(arr[0]>target) return 0; return low; } // function to calculate lower bound public static int upperbound(List<int> arr,int target) { int N = arr.Count; int high=N; for(int i=N-1;i>=0;i--) { if(arr[i]>=target && arr[i-1]<target) { high = i; break; } } if(high == N) return N; return high; } class GFG : IComparer<int> { public int Compare(int x, int y) { if (x == 0 || y == 0) { return 0; } // CompareTo() method return x.CompareTo(y); } } // function to perform the given queries on s public static void solveQueries(int Q, List<KeyValuePair<int, KeyValuePair<int, int>>> A) { // initializing variable to store answer // to current query and a multiset of integers int ans; List<int> s = new List<int>(); // iterating through all queries for (int i = 0; i < Q; i++) { int t, a, b; t = A[i].Key; a = A[i].Value.Key; b = A[i].Value.Value; // if query is of 1st type, we simply // insert both a and b into our sequence if (t == 1) { s.Add(a); s.Add(b); continue; } GFG gg = new GFG(); s.Sort(gg); // If query is of the second type, we // calculate the lower bound of a // and from that lower bound we decrement // b times to get the bth largest element // less than or equal to a if (t == 2) { ans = 0; int it = upperbound(s, a); for (int j = 0; j < b; j++) { if (it == 0) { ans = -1; break; } it--; ans = s[it]; } } // If query is of the third type, // we calculate the upper bound of a and // from that upper bound we increment b times // to get the bth smallest element greater // than or equal to a else { ans = 0; int it = lowerbound(s, a); for (int j = 0; j < b; j++) { if (it == s.Count) { ans = -1; break; } ans = s[it]; it++; } } // printing the answer Console.Write(ans + " "); } } static void Main() { int Q = 7; var A = new List<KeyValuePair<int, KeyValuePair<int, int>>>(); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(1, new KeyValuePair<int, int>(20, 10))); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(1, new KeyValuePair<int, int>(30, 20))); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(3, new KeyValuePair<int, int>(15, 1))); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(3, new KeyValuePair<int, int>(15, 2))); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(3, new KeyValuePair<int, int>(15, 3))); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(3, new KeyValuePair<int, int>(15, 4))); A.Add(new KeyValuePair<int, KeyValuePair<int, int>>(2, new KeyValuePair<int, int>(100, 5))); solveQueries(Q, A); }}// The code is contributed by Nidhi goel. |
Javascript
<script>// Javascript code for Find the sequence after// performing Q queries// function to calculate lower bound function lowerbound(arr,target){ let N = arr.length; let low=0; for(let i=0;i<N-1;i++) { if(arr[i]<target && arr[i+1]>=target) { low = i+1; break; } } if(arr[0]>target) return 0; return low;}// function to calculate lower bound function upperbound(arr,target){ let N = arr.length; let high=N; for(let i=N-1;i>=0;i--) { if(arr[i]>=target && arr[i-1]<target) { high = i; break; } } if(high = N) return N; return high;}// function to perform the given queries on slet ansArray = "";function solveQueries(Q,A){ // initializing variable to store answer // to current query and a multiset of integers let ans; let s = []; // iterating through all queries for (let i = 0; i < Q; i++) { let t = A[i].first; let a = A[i].second.first; let b = A[i].second.second; // if query is of 1st type, we simply // insert both a and b into our sequence if (t == 1) { s.push(a); s.push(b); continue; } s.sort(); // If query is of the second type, we // calculate the lower bound of a // and from that lower bound we decrement // b times to get the bth largest element // less than or equal to a if (t == 2) { ans = 0; let it = upperbound(s,a); for (let j = 0; j < b; j++) { if (it == 0) { ans = -1; break; } it--; ans = s[it]; } } // If query is of the third type, // we calculate the upper bound of a and // from that upper bound we increment b times // to get the bth smallest element greater // than or equal to a else { ans = 0; let it = lowerbound(s,a); for (let j = 0; j < b; j++) { if (it == s.length) { ans = -1; break; } ans = s[it]; it++; } } // printing(storing) the answer ansArray+=ans + " "; } }// Driver Codelet Q = 7;let A = [ {"first" : 1, "second" : {"first" : 20, "second" : 10} },{"first" : 1, "second" : {"first" : 30, "second" : 20} },{"first" : 3, "second" : {"first" : 15, "second" : 1} },{"first" : 3, "second" : {"first" : 15, "second" : 2} },{"first" : 3, "second" : {"first" : 15, "second" : 3} },{"first" : 3, "second" : {"first" : 15, "second" : 4} },{"first" : 2, "second" : {"first" : 100, "second" : 5} }]solveQueries(Q, A);// printing answerconsole.log(ansArray);// This code is contributed by akashish__</script> |
Output
20 20 30 -1 -1
Time Complexity: O(Q*log(Q)), where Q is the number of queries
Auxiliary Space: O(Q)
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!
