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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Build an Array With Stack Operations

Number: 1552

Difficulty: Medium

Paid? No

Companies: Adobe, Google

Problem Description

Given an integer array target and an integer n, simulate operations on an initially empty stack using only "Push" and "Pop" operations. You process numbers from 1 to n sequentially. For each number, if it is in target, you perform a "Push" (adding it to the stack) otherwise you perform a "Push" followed immediately by a "Pop" (to ignore it). Once the stack contains the target sequence (from bottom to top), the operations stop. Return the list of operations used to build the target array.

Key Insights

  • Since target is strictly increasing, the stream must be processed sequentially until target’s last element is reached.
  • For each integer from 1 to target[-1], decide whether to simply push (if it matches the next target value) or push then pop (if it does not).
  • The operations stop as soon as the target is fully constructed, so numbers beyond the last element in target are not processed.

Space and Time Complexity

Time Complexity: O(k) where k is the value of target[-1] (in worst-case, it iterates through numbers 1 to target[-1]). Space Complexity: O(m) where m is the number of operations stored (which in worst-case is roughly 2*m where m is the length of target)

Solution

The solution uses a simple iteration over the range [1, target[-1]]. A pointer is used to track the current index in the target array. For each number:

  1. If the current number equals the target at the pointer position, perform a "Push" and increment the pointer.
  2. If it does not match, perform a "Push" followed by a "Pop" to discard the number. This simulation mimics stack operations with a simple control flow. The algorithm stops once all elements in target have been processed. The main data structure used is a list for storing the operations.

Code Solutions

def buildArray(target, n):
    # Initialize an empty list to store the operations
    operations = []
    # Pointer for the current index in target array
    target_index = 0
    
    # Iterate through numbers 1 to n
    for number in range(1, n + 1):
        # If the target has been fully constructed, break out of loop
        if target_index == len(target):
            break
        # Always push the current number onto the stack
        operations.append("Push")
        # If the current number matches the target element at target_index,
        # then it is part of the target, so move to the next target element.
        if number == target[target_index]:
            target_index += 1
        else:
            # Otherwise, pop the number from the stack since it is not needed.
            operations.append("Pop")
    return operations

# Example usage:
print(buildArray([1, 3], 3))
← Back to All Questions