Intuition

for (int i = 0; i < pushed.size(); i++) {
	if (pushed[i] != popped[pushed.size() - 1 - i]) {
		return false;
	}
}

But the pop/push operations can happend in any sequence.

Stack

Using a stack. Returns false, IF the next value neither the popped nor pushed.

In each sequence we must do a operation: push or pop. When to push:

  1. stack is empty, or
  2. top of stack is not current popped value

When to pop:

  1. top of stack is current popped value

If no operation could do, returns false.

class Solution {
public:
	bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
		stack<int> st;
		int i = 0, j = 0;
		while (i < pushed.size() || j < popped.size()) {
			// we end push, but still not meet the popped value.
			if (i == pushed.size() && (st.empty() || st.top() != popped[j])) {
				return false;
			}
			if (st.empty()) {
				st.push(pushed[i++]);
			}

			if (st.top() != popped[j]) {
				st.push(pushed[i++]);
			} else {
				st.pop();
				j++;
			}
		}
		return true;
	}
};