[leetcode #946] Validate Stack Sequences

Problem

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:

· 1 <= pushed.length <= 1000
· 0 <= pushed[i] <= 1000
· All the elements of pushed are unique.
· popped.length == pushed.length
· popped is a permutation of pushed.

Idea

pushed와 popped가 배열로 주어지며, push·pop 순서가 stack에서 유효한지 확인하는 문제다.

실제 stack을 이용해 풀면 쉽다.

popped를 순서대로 탐색하면서 pushed 배열의 값과 일치할 때까지 stack에 pushed 값을 push한다. stack의 가장 위에 있는 값이 popped의 현재 값과 일치할 경우 stack에서 pop을 해준다.

stack의 가장 위 값이 popped의 현재 값과 일치하지도 않으며 pushed를 모두 탐색했을 경우 유효한 순서가 아니므로 false를 리턴한다.

popped 탐색이 끝나면 유효한 stack 순서이므로 true를 리턴한다.

Solution

class Solution {
    Stack<Integer> stack = new Stack<>();

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int pushedIndex = 0;
        for (int i=0; i < popped.length; i++) {
            if (!stack.isEmpty() && popped[i] == stack.peek()) {
                stack.pop();
                continue;
            }
            pushedIndex = push(pushed, pushedIndex, popped[i]);
            if (pushedIndex == -1) {
                return false;
            }
        }

        return true;
    }

    private int push(int[] pushed, int startIndex, int popValue) {
        for (int i=startIndex; i < pushed.length; i++) {
            if (pushed[i] == popValue) {
                return i+1;
            }
            stack.push(pushed[i]);
        }

        return -1;
    }
}

Reference

https://leetcode.com/problems/validate-stack-sequences/