Given a binary array, where 1 denotes a push operation and 0 denotes a pop operation in a stack or queue. The task is to check if the possible set of operations is valid or not.
Examples:
Input: a[] = {1, 1, 0, 0, 1}
Output: ValidInput : a[] = {1, 1, 0, 0, 0}
Output : Invalid
The third pop operation cannot be done as the stack or queue will be empty at that moment of time.
A naive approach will be to use a stack or queue and perform a push operation when an array element is 1, and perform a pop operation when an array element is 0. When a pop operation is there to be performed, then the move is invalid if the stack or queue is empty. If we can perform all the operations, then the moves are valid.
Time Complexity: O(N), as we will be using a loop to traverse N times where N is the number of elements in the array.
Auxiliary Space: O(N), as we will be using extra space for the stack or queue.
An efficient approach will be counting the push operation and reducing them when a pop operation is performed. If during any instance, the count becomes less than 0, then the set of operations is invalid.
Below is the implementation of the above approach.
C++
// C++ program to Check if moves in a stack// or queue are possible or not#include <bits/stdc++.h>using namespace std;// Function to check if// operations are valid or notbool check(int a[], int n){ // count number of push operations int ones = 0; // traverse in the array for (int i = 0; i < n; i++) { // push operation if (a[i]) ones++; // pop operation else ones--; // if at any moment pop() operations // exceeds the number of push operations if (ones < 0) return false; } return true;}// Driver Codeint main(){ int a[] = { 1, 1, 0, 0, 1 }; int n = sizeof(a) / sizeof(a[0]); if (check(a, n)) cout << "Valid"; else cout << "Invalid";} |
Java
// Java program to Check if moves in a stack// or queue are possible or notpublic class GFG {// Function to check if// operations are valid or not static boolean check(int a[], int n) { // count number of push operations int ones = 0; // traverse in the array for (int i = 0; i < n; i++) { // push operation if (a[i] ==1) { ones++; } // pop operation else { ones--; } // if at any moment pop() operations // exceeds the number of push operations if (ones < 0) { return false; } } return true; }// Driver Code static public void main(String[] args) { int a[] = {1, 1, 0, 0, 1}; int n = a.length; if (check(a, n)) { System.out.println("Valid"); } else { System.out.println("Invalid"); } }}// This code is contributed by Rajput-Ji |
Python 3
# Python 3 program to Check if moves # in a stack or queue are possible or not# Function to check if# operations are valid or notdef check(a, n): # count number of push operations ones = 0; # traverse in the array for i in range (0, n): # push operation if (a[i]): ones = ones + 1; # pop operation else: ones = ones - 1; # if at any moment pop() operations # exceeds the number of push operations if (ones < 0): return False; return True;# Driver Codea = [ 1, 1, 0, 0, 1 ];n = len(a);if (check(a, n)): print("Valid");else: print("Invalid");# This code is contributed # by Akanksha Rai |
C#
using System; // C# program to Check if moves in a stack// or queue are possible or not public class GFG { // Function to check if// operations are valid or not static bool check(int []a, int n) { // count number of push operations int ones = 0; // traverse in the array for (int i = 0; i < n; i++) { // push operation if (a[i] ==1) { ones++; } // pop operation else { ones--; } // if at any moment pop() operations // exceeds the number of push operations if (ones < 0) { return false; } } return true; } // Driver Code static public void Main() { int []a = {1, 1, 0, 0, 1}; int n = a.Length; if (check(a, n)) { Console.Write("Valid"); } else { Console.Write("Invalid"); } }}// This code is contributed by Rajput-Ji |
PHP
<?php// PHP program to Check if moves in a // stack or queue are possible or not // Function to check if // operations are valid or not function check($a, $n) { // count number of push operations $ones = 0; // traverse in the array for ($i = 0; $i < $n; $i++) { // push operation if ($a[$i]) $ones++; // pop operation else $ones--; // if at any moment pop() operations // exceeds the number of push operations if ($ones < 0) return false; } return true; } // Driver Code $a = array( 1, 1, 0, 0, 1 ); $n = count($a);if (check($a, $n)) echo "Valid"; else echo "Invalid"; // This code is contributed by Ryuga?> |
Javascript
<script>// JavaScript program to Check if moves in a stack// or queue are possible or not // Function to check if // operations are valid or not function check(a , n) { // count number of push operations var ones = 0; // traverse in the array for (i = 0; i < n; i++) { // push operation if (a[i] == 1) { ones++; } // pop operation else { ones--; } // if at any moment pop() operations // exceeds the number of push operations if (ones < 0) { return false; } } return true; } // Driver Code var a = [ 1, 1, 0, 0, 1 ]; var n = a.length; if (check(a, n)) { document.write("Valid"); } else { document.write("Invalid"); }// This code is contributed by todaysgaurav </script> |
Valid
Complexity Analysis:
- Time Complexity: O(N), as we are using a loop to traverse N times, where N is the number of elements in the array.
- Auxiliary Space: O(1), as we are not using any extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
