Stack Sequence - Google Top Interview Questions


Problem Statement :


Given a list of distinct integers pushes, and another list of integers pops, return whether this is a valid sequence of stack push and pop actions.

Constraints

n ≤ 100,000 where n is the length of pushes

m ≤ 100,000 where m is the length of pops

Example 1

Input

pushes = [0, 1, 4, 6, 8]

pops = [1, 0, 8, 6, 4]

Output

True

Explanation

We can first push [0, 1], then pop both off. Then push [4, 6, 8] and then pop them all off.



Example 2

Input

pushes = [1, 2, 3, 4]

pops = [4, 1, 2, 3]

Output

False

Explanation


This is not valid since 3 was pushed after 1 but is popped earlier.


Solution :



title-img



                        Solution in C++ :

bool solve(vector<int>& pushes, vector<int>& pops) {
    stack<int> st;
    int i = 0, j = 0;
    while (i < pops.size()) {
        if (st.empty())
            st.push(pushes[j++]);
        else {
            if (st.top() == pops[i]) {
                st.pop();
                i++;
            } else
                st.push(pushes[j++]);
        }
    }
    return st.size() == 0;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public boolean solve(int[] pushes, int[] pops) {
        Stack<Integer> stack = new Stack();
        int p = 0;
        for (int i = 0; i < pushes.length; i++) {
            stack.push(pushes[i]);
            while (!stack.isEmpty() && stack.peek() == pops[p]) {
                p++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, pushes, pops):
        stack = []
        i = 0
        l = 0
        for n in pushes:
            stack.append(n)
            l += 1
            while l and stack[-1] == pops[i]:
                stack.pop()
                i += 1
                l -= 1
        return not l
                    

View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →