DEV Community

Abhishek Sharma Gaur
Abhishek Sharma Gaur

Posted on

Leet code problem 1441: Build an Array With Stack Operations

Problem: https://leetcode.com/problems/build-an-array-with-stack-operations/

Intuition

The code defines a method named buildArray that takes two parameters: target (an array of integers) and n (an integer). The goal of this code is to build an array that represents a sequence of "Push" and "Pop" operations required to transform an empty array into the target array, considering the value of n.

Approach

Here's a step-by-step explanation of the code:

result = []: This initializes an empty array named result, which will store the sequence of "Push" and "Pop" operations.

target_set = Set.new(target): This line creates a set named target_set containing the elements from the target array. A set is a data structure in Ruby that stores unique elements. This set is used to efficiently check if a specific number i is present in the target array later in the code.

(1..target[-1]).each do |i|: This line sets up a loop that iterates from 1 to the last element of the target array, which is accessed with target[-1].

result << "Push": In each iteration, "Push" is added to the result array, as this operation is performed unconditionally.

result << "Pop" unless target_set.include?(i): This line adds "Pop" to the result array unless the current value i is present in the target_set. It uses the include? method to check for the presence of i in the target_set.

result: Finally, the result array is returned, which contains the sequence of "Push" and "Pop" operations required to transform an empty array into the target array.

This Ruby code is similar in functionality to the Python code you provided earlier, but it uses Ruby-specific constructs, such as the Set data structure and the << operator for array appending.

Complexity

  • Time complexity:
    O(n)

  • Space complexity:
    O(1)

Code

# @param {Integer[]} target
# @param {Integer} n
# @return {String[]}
def build_array(target, n)
    result = []
    target_set = Set.new(target)
    (1..target[-1]).each do |i|
        result << "Push"
        result << "Pop" unless target_set.include?(i)
    end
    result
end
Enter fullscreen mode Exit fullscreen mode
class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        return [
            x
            for i in range(1, target[-1] + 1)
            for x in ["Push"] + ["Pop"] * (i not in set(target))
        ]

Enter fullscreen mode Exit fullscreen mode
/**
 * @param {number[]} target
 * @param {number} n
 * @return {string[]}
 */
var buildArray = function(target, n) {
    const result = [];

    for (let i = 1; i <= target[target.length - 1]; i++) {
        result.push("Push");
        if (!target.includes(i)) {
            result.push("Pop");
        }
    }

    return result;

};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)