Problem

Consider an empty stack of integers. Let the numbers 1, 2, 3, 4, 5, 6 be pushed onto this stack only in the order they appear from left to right. Let S indicate a push and X indicate a pop operation. Determine if they can be permuted into the specified order using these operations, and if so, provide the sequence of operations.

Examples

Example 1:

1
2
3

Input: Desired order: 325641
Output: SSSXXSSXSXXX
Explanation: Push 1, 2, 3 (SSS), pop 3 (X), pop 2 (X), push 4, 5 (SS), pop 5 (X), push 6 (S), pop 6 (X), pop 4 (X), pop 1 (X).

Example 2:

1
2
3

Input: Desired order: 154623
Output: Not possible
Explanation: Number 2 appears before 3, making it impossible to output 3 before 2.

Solution

Method 1 - Using stack

To determine if a specific order can be achieved using stack operations:

  1. Simulation: Simulate the stack operations to achieve the desired sequence.
  2. Sequence Validation: Validate whether the sequence can be achieved given the constraints of stack operations.

The steps involved are:

  1. Push numbers onto the stack while maintaining S operations.
  2. Pop numbers from the stack to match the desired output using X operations.
  3. Ensure that the constraints of stack operations are respected.

Code

 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

public class Solution {
    public String canGenerateSequence(int[] target) {
        Stack<Integer> stack = new Stack<>();
        StringBuilder result = new StringBuilder();

        int current = 1;
        for (int num : target) {
            if (!stack.isEmpty() && stack.peek() == num) {
                stack.pop();
                result.append("X");
            } else {
                while (current <= num) {
                    stack.push(current);
                    result.append("S");
                    current++;
                }
                stack.pop();
                result.append("X");
            }
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] target1 = {3, 2, 5, 6, 4, 1};
        int[] target2 = {1, 5, 4, 6, 2, 3};

        System.out.println(solution.canGenerateSequence(target1)); // Output: SSSXXSSXSXXX
        System.out.println(solution.canGenerateSequence(target2)); // Output: Not possible
    }
}
 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

class Solution:
    def canGenerateSequence(self, target: List[int]) -> str:
        stack: List[int] = []
        result = []
        
        current = 1
        for num in target:
            if stack and stack[-1] == num:
                stack.pop()
                result.append("X")
            else:
                while current <= num:
                    stack.append(current)
                    result.append("S")
                    current += 1
                stack.pop()
                result.append("X")
        
        return ''.join(result)

# Test the implementation
sol = Solution()
target1 = [3, 2, 5, 6, 4, 1]
target2 = [1, 5, 4, 6, 2, 3]

print(sol.canGenerateSequence(target1))  # Output: SSSXXSSXSXXX
print(sol.canGenerateSequence(target2))  # Output: Not possible

Complexity

  • ⏰ Time complexity: O(n) where n is the number of operations to perform.
  • 🧺 Space complexity: O(n) for maintaining the stack.