Given a positive integer N representing the set of integers [1, N] and an array queries[] of length Q of type {L, K}, the task is to perform the given queries according to the following rules and print the result:
- If the value of L is 1, then delete the given integer K.
- If the value of L is 2, then print the first integer from K to N which is not deleted.
Note: When all the elements to the right are deleted, the answer will be -1.
Examples:
Input: N = 3, queries[] = {{2, 1}, {1, 1}, {2, 1}, {2, 3}}
Output: 1 2 3
Explanation:
For the first query: the rightmost element for 1 is 1 only.
After the second query: 1 is deleted.
For the third query: the rightmost element for 1 is 2.
For the fourth query: the rightmost element for 3 is 3.Input: N = 5, queries = {{2, 1}, {1, 3}, {2, 3}, {1, 2}, {2, 2}, {1, 5}, {2, 5}}
Output: 1 4 4 -1
Approach: The given problem can be solved by using Disjoint Set Union Data Structure. Initially, all the elements are in different sets, for the first type query perform the Union Operation on the given integer. For the second type of query, get the parent of the given vertex and print the value stored in the array graph[]. Follow the steps below to solve the problem:
- Initialize the vector graph(N + 2).
- Iterate over the range [1, N+1] using the variable i and set the value of graph[i] as i.
- Iterate over the queries[] using the variable query and perform the following steps:
- If query.first is 1 then call for function operation Union(graph, query.second, query.second + 1).
- Otherwise, call for function operation Get(graph, query.second) and assign it to variable a. Now, if the value of a is (N + 1), then print -1. Otherwise, print the value of graph[a] as the result.
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 Get operation// of disjoint set unionint Get(vector<int>& graph, int a){ return graph[a] = (graph[a] == a ? a : Get(graph, graph[a]));}// Function to perform the union// operation of disjoint set unionvoid Union(vector<int>& graph, int a, int b){ a = Get(graph, a); b = Get(graph, b); // Update the graph[a] as b graph[a] = b;}// Function to perform given queries on// set of vertices initially not connectedvoid Queries(vector<pair<int, int> >& queries, int N, int M){ // Stores the vertices vector<int> graph(N + 2); // Mark every vertices rightmost // vertex as i for (int i = 1; i <= N + 1; i++) { graph[i] = i; } // Traverse the queries array for (auto query : queries) { // Check if it is first type // of the given query if (query.first == 1) { Union(graph, query.second, query.second + 1); } else { // Get the parent of a int a = Get(graph, query.second); // Print the answer for // the second query if (a == N + 1) cout << -1 << " "; else cout << graph[a] << " "; } }}// Driver Codeint main(){ int N = 5; vector<pair<int, int> > queries{ { 2, 1 }, { 1, 1 }, { 2, 1 }, { 2, 3 } }; int Q = queries.size(); Queries(queries, N, Q); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to perform the Get operation// of disjoint set unionpublic static int Get(int[] graph, int a){ return graph[a] = (graph[a] == a ? a : Get(graph, graph[a]));}// Function to perform the union// operation of disjoint set unionpublic static void Union(int[] graph, int a, int b){ a = Get(graph, a); b = Get(graph, b); // Update the graph[a] as b graph[a] = b;}// Function to perform given queries on// set of vertices initially not connectedpublic static void Queries(int[][] queries, int N, int M){ // Stores the vertices int[] graph = new int[N + 2]; // Mark every vertices rightmost // vertex as i for (int i = 1; i <= N + 1; i++) { graph[i] = i; } // Traverse the queries array for (int[] query : queries) { // Check if it is first type // of the given query if (query[0] == 1) { Union(graph, query[1], query[1] + 1); } else { // Get the parent of a int a = Get(graph, query[1]); // Print the answer for // the second query if (a == N + 1) System.out.print(-1); else System.out.print(graph[a] + " "); } }}// Driver Codepublic static void main(String args[]){ int N = 5; int[][] queries = { { 2, 1 }, { 1, 1 }, { 2, 1 }, { 2, 3 }}; int Q = queries.length; Queries(queries, N, Q);}}// This code is contributed by gfgking. |
Python3
# Python 3 program for the above approach# Function to perform the Get operation# of disjoint set uniondef Get(graph, a): if graph[graph[a]]!= graph[a]: graph[a] = Get(graph, graph[a]) else: return graph[a]# Function to perform the union# operation of disjoint set uniondef Union(graph, a, b): a = Get(graph, a) b = Get(graph, b) # Update the graph[a] as b graph[a] = b# Function to perform given queries on# set of vertices initially not connecteddef Queries(queries, N, M): # Stores the vertices graph = [0 for i in range(N + 2)] # Mark every vertices rightmost # vertex as i for i in range(1,N + 2,1): graph[i] = i # Traverse the queries array for query in queries: # Check if it is first type # of the given query if (query[0] == 1): Union(graph, query[1], query[1] + 1) else: # Get the parent of a a = Get(graph, query[1]) # Print the answer for # the second query if (a == N + 1): print(-1) else: print(graph[a],end = " ")# Driver Codeif __name__ == '__main__': N = 5 queries = [[2, 1],[1, 1],[2, 1],[2, 3]] Q = len(queries) Queries(queries, N, Q) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG{ // Function to perform the Get operation // of disjoint set union public static int Get(int[] graph, int a) { return graph[a] = (graph[a] == a ? a : Get(graph, graph[a])); } // Function to perform the union // operation of disjoint set union public static void Union(int[] graph, int a, int b) { a = Get(graph, a); b = Get(graph, b); // Update the graph[a] as b graph[a] = b; } // Function to perform given queries on // set of vertices initially not connected public static void Queries(int[][] queries, int N, int M) { // Stores the vertices int[] graph = new int[N + 2]; // Mark every vertices rightmost // vertex as i for (int i = 1; i <= N + 1; i++) { graph[i] = i; } // Traverse the queries array foreach (int[] query in queries) { // Check if it is first type // of the given query if (query[0] == 1) { Union(graph, query[1], query[1] + 1); } else { // Get the parent of a int a = Get(graph, query[1]); // Print the answer for // the second query if (a == N + 1) Console.Write(-1); else Console.Write(graph[a] + " "); } } } // Driver Code static void Main(string[] args) { int N = 5; int[][] queries = { new int[] { 2, 1 }, new int[] { 1, 1 }, new int[] { 2, 1 }, new int[] { 2, 3 } }; int Q = queries.Length; Queries(queries, N, Q); }} |
Javascript
<script>// Javascript program for the above approach// Function to perform the Get operation// of disjoint set unionfunction Get(graph, a) { return (graph[a] = graph[a] == a ? a : Get(graph, graph[a]));}// Function to perform the union// operation of disjoint set unionfunction Union(graph, a, b) { a = Get(graph, a); b = Get(graph, b); // Update the graph[a] as b graph[a] = b;}// Function to perform given queries on// set of vertices initially not connectedfunction Queries(queries, N, M) { // Stores the vertices let graph = new Array(N).fill(2); // Mark every vertices rightmost // vertex as i for (let i = 1; i <= N + 1; i++) { graph[i] = i; } // Traverse the queries array for (let query of queries) { // Check if it is first type // of the given query if (query[0] == 1) { Union(graph, query[1], query[1] + 1); } else { // Get the parent of a let a = Get(graph, query[1]); // Print the answer for // the second query if (a == N + 1) document.write(-1 + " "); else document.write(graph[a] + " "); } }}// Driver Codelet N = 5;let queries = [ [2, 1], [1, 1], [2, 1], [2, 3],];let Q = queries.length;Queries(queries, N, Q);// This code is contributed by gfgking.</script> |
Output:
1 2 3
Time Complexity: O(M*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!