Given a binary array arr[], the task is to design a data structure that supports the following operations in O(1).
- Type 1: Remove and print the leftmost 0 from the array.
- Type 2: Remove and print the leftmost 1 from the array.
- Type 3: Remove and print the leftmost element from the array.
If any of the requested element is not in the array then print -1.
Examples:
Input: arr[] = {1, 0, 1, 1, 1}, q[] = {1, 3, 1}
Output:
0
1
-1
Type 1 query: Print 0 and the array become {1, 1, 1, 1}
Type 3 query: Print 1, arr[] = {1, 1, 1}
Type 1 query: There are no 0s left, so print -1
Input: arr[] = {1, 0, 1, 0, 1}, q[] = {3, 3, 3}
Output:
1
0
1
Naive approach: A simple approach is to insert all the elements in a queue which supports first in first out. This approach will work in O(1) for finding the leftmost element in the array but it cannot find the left-most 1 or the left-most 0 in O(1).
Efficient approach: Create two queues, the first queue will store the indices of the 0s in the order of appearance and the second queue will store the indices of 1s in the order of appearance. Now, the given operations can be performed as follows:
- Type 1: Print the remove the head of the first queue in O(1).
- Type 2: Print the remove the head of the second queue in O(1).
- Type 3: Compare the head of both the queues and return the one with minimum index and then remove it..
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h>using namespace std;// To store the indices of 0s and 1s static queue<int> zero; static queue<int> one ; // Function to return the leftmost 0 static int getLeftMostZero() { // If there are no 0s if (zero.empty()) return -1; // pop the head of the queue zero.pop(); return 0; } // Function to return the leftmost 1 static int getLeftMostOne() { // If there are no 1s if (one.empty()) return -1; // pop the head of the queue one.pop(); return 1; } // Function to return the pre-calculate array // such that arr[i] stores the count of // valid numbers in the range [0, i] int getLeftMostElement() { // If there are no elements left if (zero.empty() && one.empty()) return -1; // If only 1s are there else if (zero.empty()) { one.pop(); return 1; } // If only 0s are there else if (one.empty()) { zero.pop(); return 0; } // Get the element which is at // the left-most position int res = (zero.front() < one.front()) ? 0 : 1; if (res == 0) zero.pop(); else one.pop(); return res; } // Function to perform the queries void performQueries(int arr[], int n, int queries[], int q) { for (int i = 0; i < n; i++) { if (arr[i] == 0) zero.push(i); else one.push(i); } // For every query for (int i = 0; i < q; i++) { // Get its type int type = queries[i]; switch (type) { // Perform type 1 query case 1: cout << (getLeftMostZero()) << endl; break; // Perform type 2 query case 2: cout << (getLeftMostOne()) << endl; break; // Perform type 3 query case 3: cout << (getLeftMostElement()) << endl; break; } } } // Driver code int main() { int arr[] = { 1, 0, 1, 1, 1 }; int n = sizeof(arr) / sizeof(int); int queries[] = { 1, 3, 1 }; int q = sizeof(queries) / sizeof(int); performQueries(arr, n, queries, q); } // This code is contributed by andrew1234 |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to return the leftmost 0 static int getLeftMostZero(Queue<Integer> zero) { // If there are no 0s if (zero.isEmpty()) return -1; // Remove the head of the queue zero.remove(); return 0; } // Function to return the leftmost 1 static int getLeftMostOne(Queue<Integer> one) { // If there are no 1s if (one.isEmpty()) return -1; // Remove the head of the queue one.remove(); return 1; } // Function to return the pre-calculate array // such that arr[i] stores the count of // valid numbers in the range [0, i] static int getLeftMostElement(Queue<Integer> zero, Queue<Integer> one) { // If there are no elements left if (zero.isEmpty() && one.isEmpty()) return -1; // If only 1s are there else if (zero.isEmpty()) { one.remove(); return 1; } // If only 0s are there else if (one.isEmpty()) { zero.remove(); return 0; } // Get the element which is at // the left-most position int res = (zero.peek() < one.peek()) ? 0 : 1; if (res == 0) zero.remove(); else one.remove(); return res; } // Function to perform the queries static void performQueries(int arr[], int n, int queries[], int q) { // To store the indices of 0s and 1s Queue<Integer> zero = new LinkedList<>(); Queue<Integer> one = new LinkedList<>(); for (int i = 0; i < n; i++) { if (arr[i] == 0) zero.add(i); else one.add(i); } // For every query for (int i = 0; i < q; i++) { // Get its type int type = queries[i]; switch (type) { // Perform type 1 query case 1: System.out.println(getLeftMostZero(zero)); break; // Perform type 2 query case 2: System.out.println(getLeftMostOne(one)); break; // Perform type 3 query case 3: System.out.println(getLeftMostElement(zero, one)); break; } } } // Driver code public static void main(String args[]) { int arr[] = { 1, 0, 1, 1, 1 }; int n = arr.length; int queries[] = { 1, 3, 1 }; int q = queries.length; performQueries(arr, n, queries, q); }} |
Python3
# Python3 implementation of the approachfrom collections import deque# To store the indices of 0s and 1szero = deque()one = deque()# Function to return the leftmost 0def getLeftMostZero(): # If there are no 0s if not len(zero): return -1 # pop the head of the queue zero.popleft() return 0# Function to return the leftmost 1def getLeftMostOne(): # If there are no 1s if not len(one): return -1 # pop the head of the queue one.popleft() return 1# Function to return the pre-calculate array# such that arr[i] stores the count of# valid numbers in the range [0, i]def getLeftMostElement(): # If there are no elements left if not len(zero) and not len(one): return -1 # If only 1s are there elif not len(zero): one.popleft() return 1 # If only 0s are there elif not len(one): zero.popleft() return 0 # Get the element which is at # the left-most position res = 0 if zero[0] < one[0] else 1 if res == 0: zero.popleft() else: one.popleft() return res# Function to perform the queriesdef performQueries(arr: list, n: int, queries: list, q: int): for i in range(n): if arr[i] == 0: zero.append(i) else: one.append(i) # For every query for i in range(q): # Get its type type = queries[i] # Perform type 1 query if type == 1: print(getLeftMostZero()) # Perform type 2 query elif type == 2: print(getLeftMostOne()) # Perform type 3 query elif type == 3: print(getLeftMostElement())# Driver Codeif __name__ == "__main__": arr = [1, 0, 1, 1, 1] n = len(arr) queries = [1, 3, 1] q = len(queries) performQueries(arr, n, queries, q)# This code is contributed by# sanjeev2552 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Function to return the leftmost 0 static int getLeftMostZero(Queue<int> zero) { // If there are no 0s if (zero.Count == 0) return -1; // Remove the head of the queue zero.Dequeue(); return 0; } // Function to return the leftmost 1 static int getLeftMostOne(Queue<int> one) { // If there are no 1s if (one.Count == 0) return -1; // Remove the head of the queue one.Dequeue(); return 1; } // Function to return the pre-calculate array // such that arr[i] stores the count of // valid numbers in the range [0, i] static int getLeftMostElement(Queue<int> zero, Queue<int> one) { // If there are no elements left if (zero.Count == 0 && one.Count == 0) return -1; // If only 1s are there else if (zero.Count == 0) { one.Dequeue(); return 1; } // If only 0s are there else if (one.Count == 0) { zero.Dequeue(); return 0; } // Get the element which is at // the left-most position int res = (zero.Peek() < one.Peek()) ? 0 : 1; if (res == 0) zero.Dequeue(); else one.Dequeue(); return res; } // Function to perform the queries static void performQueries(int []arr, int n, int []queries, int q) { // To store the indices of 0s and 1s Queue<int> zero = new Queue<int>(); Queue<int> one = new Queue<int>(); for (int i = 0; i < n; i++) { if (arr[i] == 0) zero.Enqueue(i); else one.Enqueue(i); } // For every query for (int i = 0; i < q; i++) { // Get its type int type = queries[i]; switch (type) { // Perform type 1 query case 1: Console.WriteLine(getLeftMostZero(zero)); break; // Perform type 2 query case 2: Console.WriteLine(getLeftMostOne(one)); break; // Perform type 3 query case 3: Console.WriteLine(getLeftMostElement(zero, one)); break; } } } // Driver code public static void Main(String []args) { int []arr = { 1, 0, 1, 1, 1 }; int n = arr.Length; int []queries = { 1, 3, 1 }; int q = queries.Length; performQueries(arr, n, queries, q); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the approach// Function to return the leftmost 0function getLeftMostZero(zero){ // If there are no 0s if (zero.length==0) return -1; // Remove the head of the queue zero.shift(); return 0;}// Function to return the leftmost 1function getLeftMostOne(one){ // If there are no 1s if (one.length==0) return -1; // Remove the head of the queue one.shift(); return 1;}// Function to return the pre-calculate array // such that arr[i] stores the count of // valid numbers in the range [0, i]function getLeftMostElement(zero,one){ // If there are no elements left if (zero.length==0 && one.length==0) return -1; // If only 1s are there else if (zero.length==0) { one.shift(); return 1; } // If only 0s are there else if (one.length==0) { zero.shift(); return 0; } // Get the element which is at // the left-most position let res = (zero[0] < one[0]) ? 0 : 1; if (res == 0) zero.shift(); else one.shift(); return res;}// Function to perform the queriesfunction performQueries(arr,n,queries,q){ // To store the indices of 0s and 1s let zero = []; let one = []; for (let i = 0; i < n; i++) { if (arr[i] == 0) zero.push(i); else one.push(i); } // For every query for (let i = 0; i < q; i++) { // Get its type let type = queries[i]; switch (type) { // Perform type 1 query case 1: document.write(getLeftMostZero(zero)+"<br>"); break; // Perform type 2 query case 2: document.write(getLeftMostOne(one)+"<br>"); break; // Perform type 3 query case 3: document.write(getLeftMostElement(zero, one)+"<br>"); break; } }}// Driver codelet arr=[1, 0, 1, 1, 1];let n = arr.length;let queries=[1, 3, 1 ];let q = queries.length;performQueries(arr, n, queries, q);// This code is contributed by avanitrachhadiya2155</script> |
Output:
0 1 -1
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!
