We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Build an Array With Stack Operations

Difficulty: Medium

Problem Description

You are given an integer array target and an integer n. You have an empty stack with the operations "Push" and "Pop". Use these operations to build the stack such that its elements (from the bottom to the top) are equal to target, using a stream of integers from the range [1, n]. Return the stack operations needed to build target.

Key Insights

  • The integers must be added in sequence from 1 to n.
  • Elements in the target array are strictly increasing.
  • You can push and pop elements based on whether the current integer is in the target array.
  • The challenge lies in deciding when to pop elements to match the desired target.

Space and Time Complexity

Time Complexity: O(n), where n is the input integer representing the range of integers from 1 to n. Each integer is processed once. Space Complexity: O(m), where m is the number of operations (Push and Pop) needed to build the target array.

Solution

The problem can be solved using a simulation of stack operations. We iterate through the integers from 1 to n, pushing each integer onto the stack. If the integer is not part of the target array, we pop it off the stack. We continue this until we have constructed the target array using the stack. This approach utilizes a simple list to represent the stack and keeps track of the operations performed.

Code Solutions

def buildArray(target, n):
    operations = []
    current = 1
    for num in target:
        while current < num:
            operations.append("Push")
            operations.append("Pop")
            current += 1
        operations.append("Push")
        current += 1
    return operations
← Back to All Questions