Competitive-Programming/Validate stack sequences.cpp at main · Yosef-6/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>sim;
        int j = 0;
        unordered_map<int,bool>loc;
        while(pushed[j] != popped[0]){
        loc[pushed[j]] = true;
        sim.push(pushed[j]);
        j++;
        }
        j++;
        for(int i = 1; i<popped.size(); i++){

            if(loc.find(popped[i]) != loc.end()){
                if(sim.top() == popped[i])
                    sim.pop();
                else
                    return false;
            }
            else{
                   while( j < pushed.size() &&pushed[j] != popped[i]){
                   loc[pushed[j]] = true;
                   sim.push(pushed[j]);
                   j++;
                   }
                   j++;


            }

        }
        return true;


    }
};