Perform given queries on Queue according to the given rules
Given a queue consisting of the first N natural numbers and queries Query[][] of the type {E, X}, the task is to perform the given queries on the given queue according to the following rules:
- If the value of E is 1, then pop the front element from the queue.
- If the value of E is 2, then remove the value X from the queue if it exists.
- If the value of E is 3, then find the position of X in the queue if it exists. Otherwise, print “-1”.
Examples:
Input: N = 5, Query[][] = {{1, 0}, {3, 3}, {2, 2}}
Output: 2
Explanation:
Initially queue looks like { 1, 2, 3, 4, 5 }. Following are the operations performed according to the queries given:
1st query E = 1, X = 0 -> 1 is popped out changing queue to { 2, 3, 4, 5 }.
2nd query E = 3, X = 3 -> The position of 3 is printed.
3rd query E = 2, X = 2 -> 2 is removed from queue changing queue to { 3, 4, 5 }.Input: N = 5, Query[][] = {{1, 0}, {3, 1}}
Output: -1
Approach: The given problem can be solved by using Greedy Approach and Binary Search. Follow the steps below to solve the given problem.
- Initialize a variable say countE1 as 0 to count the number of occurrences of event E1.
- Increment the value of countE1 by 1 when the query is of type E1.
- Maintain a set data structure that stores the elements which are removed while performing queries operations.
- For the query of type 3 perform the following steps:
- Initialize a variable, say position to store the initial position of X.
- Find the value of X in the set to check whether X is already removed or not and if X is present in the set, the print -1. Otherwise, find the position of X.
- Traverse the set with iterator say it and if the value of it > X, then break out of the loop. Otherwise, decrease the position by 1.
- Print the final position of X store in position variable.
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 all the queries // operations on the given queue void solve( int n, int m, int ** queries) { // Stores the count query of type 1 int countE1 = 0; set< int > removed; for ( int i = 0; i < m; i++) { // Event E1: increase countE1 if (queries[i][0] == 1) ++countE1; // Event E2: add the X in set else if (queries[i][0] == 2) removed.insert(queries[i][1]); // Event E3: Find position of X else { // Initial position is // (position - countE1) int position = queries[i][1] - countE1; // If X is already removed or // popped out if (removed.find(queries[i][1]) != removed.end() || position <= 0) cout << "-1\n" ; // Finding the position of // X in queue else { // Traverse set to decrease // position of X for all the // number removed in front for ( int it : removed) { if (it > queries[i][1]) break ; position--; } // Print the position of X cout << position << "\n" ; } } } } // Driver Code int main() { int N = 5, Q = 3; int ** queries = new int *[Q]; for ( int i = 0; i < Q; i++) { queries[i] = new int [2]; } queries[0][0] = 1; queries[0][1] = 0; queries[1][0] = 3; queries[1][1] = 3; queries[2][0] = 2; queries[2][1] = 2; solve(N, Q, queries); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to perform all the queries // operations on the given queue static void solve( int n, int m, int [][]queries) { // Stores the count query of type 1 int countE1 = 0 ; HashSet<Integer> removed = new HashSet<Integer>(); for ( int i = 0 ; i < m; i++) { // Event E1: increase countE1 if (queries[i][ 0 ] == 1 ) ++countE1; // Event E2: add the X in set else if (queries[i][ 0 ] == 2 ) removed.add(queries[i][ 1 ]); // Event E3: Find position of X else { // Initial position is // (position - countE1) int position = queries[i][ 1 ] - countE1; // If X is already removed or // popped out if (removed.contains(queries[i][ 1 ]) || position <= 0 ) System.out.print( "-1\n" ); // Finding the position of // X in queue else { // Traverse set to decrease // position of X for all the // number removed in front for ( int it : removed) { if (it > queries[i][ 1 ]) break ; position--; } // Print the position of X System.out.print(position+ "\n" ); } } } } // Driver Code public static void main(String[] args) { int N = 5 , Q = 3 ; int [][]queries = new int [Q][ 2 ]; queries[ 0 ][ 0 ] = 1 ; queries[ 0 ][ 1 ] = 0 ; queries[ 1 ][ 0 ] = 3 ; queries[ 1 ][ 1 ] = 3 ; queries[ 2 ][ 0 ] = 2 ; queries[ 2 ][ 1 ] = 2 ; solve(N, Q, queries); } } // This code is contributed by shikhasingrajput |
Python3
# python program for the above approach # Function to perform all the queries # operations on the given queue def solve(n, m, queries): # Stores the count query of type 1 countE1 = 0 removed = set () for i in range ( 0 , m): # Event E1: increase countE1 if (queries[i][ 0 ] = = 1 ): countE1 + = 1 # Event E2: add the X in set elif (queries[i][ 0 ] = = 2 ): removed.add(queries[i][ 1 ]) # Event E3: Find position of X else : # Initial position is # (position - countE1) position = queries[i][ 1 ] - countE1 # If X is already removed or # popped out if (queries[i][ 1 ] in removed or position < = 0 ): print ( "-1" ) # Finding the position of # X in queue else : # Traverse set to decrease # position of X for all the # number removed in front for it in removed: if (it > queries[i][ 1 ]): break position - = 1 # Print the position of X print (position) # Driver Code if __name__ = = "__main__" : N = 5 Q = 3 queries = [[ 0 for _ in range ( 2 )] for _ in range (Q)] queries[ 0 ][ 0 ] = 1 queries[ 0 ][ 1 ] = 0 queries[ 1 ][ 0 ] = 3 queries[ 1 ][ 1 ] = 3 queries[ 2 ][ 0 ] = 2 queries[ 2 ][ 1 ] = 2 solve(N, Q, queries) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to perform all the queries // operations on the given queue static void solve( int n, int m, int [,]queries) { // Stores the count query of type 1 int countE1 = 0; HashSet< int > removed = new HashSet< int >(); for ( int i = 0; i < m; i++) { // Event E1: increase countE1 if (queries[i, 0] == 1) ++countE1; // Event E2: add the X in set else if (queries[i, 0] == 2) removed.Add(queries[i, 1]); // Event E3: Find position of X else { // Initial position is // (position - countE1) int position = queries[i, 1] - countE1; // If X is already removed or // popped out if (removed.Contains(queries[i, 1]) || position <= 0) Console.WriteLine( "-1\n" ); // Finding the position of // X in queue else { // Traverse set to decrease // position of X for all the // number removed in front foreach ( int it in removed) { if (it > queries[i, 1]) break ; position--; } // Print the position of X Console.WriteLine(position+ "\n" ); } } } } // Driver Code public static void Main ( string [] args) { int N = 5, Q = 3; int [,]queries = new int [Q, 2]; queries[0, 0] = 1; queries[0, 1] = 0; queries[1, 0] = 3; queries[1, 1] = 3; queries[2, 0] = 2; queries[2, 1] = 2; solve(N, Q, queries); } } // This code is contributed by code_hunt. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to perform all the queries // operations on the given queue function solve(n, m, queries) { // Stores the count query of type 1 let countE1 = 0; let removed = new Set(); for (let i = 0; i < m; i++) { // Event E1: increase countE1 if (queries[i][0] == 1) ++countE1; // Event E2: add the X in set else if (queries[i][0] == 2) removed.add(queries[i][1]); // Event E3: Find position of X else { // Initial position is // (position - countE1) let position = queries[i][1] - countE1; // If X is already removed or // popped out if (removed.has(queries[i][1]) != false || position <= 0) document.write( "-1" + "<br>" ); // Finding the position of // X in queue else { // Traverse set to decrease // position of X for all the // number removed in front for (let it of removed) { if (it > queries[i][1]) break ; position--; } // Print the position of X document.write(position + "<br>" ); } } } } // Driver Code let N = 5, Q = 3; let queries = new Array(Q); for (let i = 0; i < Q; i++) { queries[i] = new Array(2); } queries[0][0] = 1; queries[0][1] = 0; queries[1][0] = 3; queries[1][1] = 3; queries[2][0] = 2; queries[2][1] = 2; solve(N, Q, queries); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity:
- For Query of type 1: O(1)
- For Query of type 2: O(log N)
- For Query of type 3: O(N2 log N)
Auxiliary Space: O(N)
Contact Us