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 queuevoid 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 Codeint 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 approachimport java.util.*;class GFG{// Function to perform all the queries// operations on the given queuestatic 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 Codepublic 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 queuedef 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 Codeif __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 approachusing System;using System.Collections.Generic;using System.Linq;public class GFG { // Function to perform all the queries// operations on the given queuestatic 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 Codepublic 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> |
Output:
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)
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!
