Practice Problems

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const map = new Map(); // stores value -> next greater
    const stack = [];

    for (let num of nums2) {
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            map.set(stack.pop(), num);
        }
        stack.push(num);
    }

    return nums1.map(n => map.has(n) ? map.get(n) : -1);
};

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        mapping = {}

        for num in nums2:
            while stack and num > stack[-1]:
                mapping[stack.pop()] = num
            stack.append(num)

        return [mapping.get(n, -1) for n in nums1]

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
        Deque<Integer> stack = new ArrayDeque<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> st;

        for (int num : nums2) {
            while (!st.empty() && st.top() < num) {
                map[st.top()] = num;
                st.pop();
            }
            st.push(num);
        }

        vector<int> res;
        for (int num : nums1) {
            res.push_back(map.count(num) ? map[num] : -1);
        }
        return res;
    }
};

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    mp := make(map[int]int)
    var stack []int

    for _, num := range nums2 {
        for len(stack) > 0 && stack[len(stack)-1] < num {
            mp[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, num)
    }

    res := make([]int, len(nums1))
    for i, num := range nums1 {
        if val, ok := mp[num]; ok {
            res[i] = val
        } else {
            res[i] = -1
        }
    }
    return res
}

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Integer[]}
def next_greater_element(nums1, nums2)
    stack = []
    mapping = {}

    nums2.each do |num|
        while !stack.empty? && stack.last < num
            mapping[stack.pop] = num
        end
        stack.push(num)
    end

    nums1.map { |n| mapping.fetch(n, -1) }
end

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const res = new Array(n).fill(0);
    const stack = []; // indices

    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const idx = stack.pop();
            res[idx] = i - idx;
        }
        stack.push(i);
    }
    return res;
};

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = [] # indices

        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                idx = stack.pop()
                res[idx] = i - idx
            stack.append(i)

        return res

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }
}

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> st; // indices

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int idx = st.top();
                st.pop();
                res[idx] = i - idx;
            }
            st.push(i);
        }
        return res;
    }
};

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    res := make([]int, n)
    var stack []int // indices

    for i, temp := range temperatures {
        for len(stack) > 0 && temp > temperatures[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = i - idx
        }
        stack = append(stack, i)
    }
    return res
}

# @param {Integer[]} temperatures
# @return {Integer[]}
def daily_temperatures(temperatures)
    res = Array.new(temperatures.length, 0)
    stack = [] # indices

    temperatures.each_with_index do |temp, i|
        while !stack.empty? && temp > temperatures[stack.last]
            idx = stack.pop
            res[idx] = i - idx
        end
        stack.push(i)
    end

    res
end

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];

    // Iterate twice to handle circular nature
    for (let i = 0; i < 2 * n; i++) {
        const num = nums[i % n];
        while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
            res[stack.pop()] = num;
        }
        if (i < n) {
            stack.push(i);
        }
    }

    return res;
};

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1] * n
        stack = []

        # Iterate twice to handle circular nature
        for i in range(2 * n):
            num = nums[i % n]
            while stack and nums[stack[-1]] < num:
                res[stack.pop()] = num
            if i < n:
                stack.append(i)

        return res

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        // Iterate twice to handle circular nature
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                res[stack.pop()] = num;
            }
            if (i < n) {
                stack.push(i);
            }
        }

        return res;
    }
}

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st;

        // Iterate twice to handle circular nature
        for (int i = 0; i < 2 * n; ++i) {
            int num = nums[i % n];
            while (!st.empty() && nums[st.top()] < num) {
                res[st.top()] = num;
                st.pop();
            }
            if (i < n) {
                st.push(i);
            }
        }

        return res;
    }
};

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }
    var stack []int

    // Iterate twice to handle circular nature
    for i := 0; i < 2*n; i++ {
        num := nums[i%n]
        for len(stack) > 0 && nums[stack[len(stack)-1]] < num {
            res[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        if i < n {
            stack = append(stack, i)
        }
    }

    return res
}

# @param {Integer[]} nums
# @return {Integer[]}
def next_greater_elements(nums)
    n = nums.length
    res = Array.new(n, -1)
    stack = []

    # Iterate twice to handle circular nature
    (0...(2 * n)).each do |i|
        num = nums[i % n]
        while !stack.empty? && nums[stack.last] < num
            res[stack.pop] = num
        end
        stack.push(i) if i < n
    end

    res
end

var StockSpanner = function() {
    this.stack = []; // [price, span]
};

/**
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {
    let span = 1;

    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
        span += this.stack.pop()[1];
    }

    this.stack.push([price, span]);
    return span;
};

class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span)

    def next(self, price: int) -> int:
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        self.stack.append((price, span))
        return span

class StockSpanner {
    private Deque<int[]> stack; // [price, span]

    public StockSpanner() {
        stack = new ArrayDeque<>();
    }

    public int next(int price) {
        int span = 1;

        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }

        stack.push(new int[]{price, span});
        return span;
    }
}

class StockSpanner {
private:
    stack<pair<int, int>> st; // (price, span)

public:
    StockSpanner() {}

    int next(int price) {
        int span = 1;

        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }

        st.push({price, span});
        return span;
    }
};

type StockSpanner struct {
    stack [][2]int // [price, span]
}

func Constructor() StockSpanner {
    return StockSpanner{stack: make([][2]int, 0)}
}

func (this *StockSpanner) Next(price int) int {
    span := 1

    for len(this.stack) > 0 && this.stack[len(this.stack)-1][0] <= price {
        span += this.stack[len(this.stack)-1][1]
        this.stack = this.stack[:len(this.stack)-1]
    }

    this.stack = append(this.stack, [2]int{price, span})
    return span
}

class StockSpanner
    def initialize()
        @stack = [] # [price, span]
    end

    # @param {Integer} price
    # @return {Integer}
    def next(price)
        span = 1

        while !@stack.empty? && @stack.last[0] <= price
            span += @stack.pop[1]
        end

        @stack.push([price, span])
        span
    end
end

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    const stack = [];

    for (const digit of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }

    // Remove remaining k digits from the end
    while (k > 0) {
        stack.pop();
        k--;
    }

    // Remove leading zeros and build result
    const result = stack.join('').replace(/^0+/, '');
    return result || '0';
};

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []

        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)

        # Remove remaining k digits from the end
        stack = stack[:-k] if k else stack

        # Remove leading zeros and build result
        return ''.join(stack).lstrip('0') or '0'

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char digit : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }

        // Remove remaining k digits from the end
        while (k > 0) {
            stack.pop();
            k--;
        }

        // Build result in correct order
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pollLast());
        }

        // Remove leading zeros
        while (sb.length() > 0 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

class Solution {
public:
    string removeKdigits(string num, int k) {
        string stack;

        for (char digit : num) {
            while (k > 0 && !stack.empty() && stack.back() > digit) {
                stack.pop_back();
                k--;
            }
            stack.push_back(digit);
        }

        // Remove remaining k digits from the end
        while (k > 0) {
            stack.pop_back();
            k--;
        }

        // Remove leading zeros
        size_t start = stack.find_first_not_of('0');
        return start == string::npos ? "0" : stack.substr(start);
    }
};

func removeKdigits(num string, k int) string {
    stack := []byte{}

    for i := 0; i < len(num); i++ {
        digit := num[i]
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > digit {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, digit)
    }

    // Remove remaining k digits from the end
    stack = stack[:len(stack)-k]

    // Remove leading zeros
    result := strings.TrimLeft(string(stack), "0")
    if result == "" {
        return "0"
    }
    return result
}

# @param {String} num
# @param {Integer} k
# @return {String}
def remove_kdigits(num, k)
    stack = []

    num.each_char do |digit|
        while k > 0 && !stack.empty? && stack.last > digit
            stack.pop
            k -= 1
        end
        stack.push(digit)
    end

    # Remove remaining k digits from the end
    stack = stack[0...-k] if k > 0

    # Remove leading zeros and build result
    result = stack.join.sub(/^0+/, '')
    result.empty? ? '0' : result
end

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function(nums) {
    const stack = [];
    let third = -Infinity; // The "2" in 132

    // Traverse from right to left
    for (let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] < third) {
            return true; // Found "1" that is less than "2"
        }
        while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
            third = stack.pop(); // Update "2" (nums[k])
        }
        stack.push(nums[i]); // Push potential "3" (nums[j])
    }

    return false;
};

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        third = float('-inf')  # The "2" in 132

        # Traverse from right to left
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < third:
                return True  # Found "1" that is less than "2"
            while stack and stack[-1] < nums[i]:
                third = stack.pop()  # Update "2" (nums[k])
            stack.append(nums[i])  # Push potential "3" (nums[j])

        return False

class Solution {
    public boolean find132pattern(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int third = Integer.MIN_VALUE; // The "2" in 132

        // Traverse from right to left
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < third) {
                return true; // Found "1" that is less than "2"
            }
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                third = stack.pop(); // Update "2" (nums[k])
            }
            stack.push(nums[i]); // Push potential "3" (nums[j])
        }

        return false;
    }
}

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> st;
        int third = INT_MIN; // The "2" in 132

        // Traverse from right to left
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] < third) {
                return true; // Found "1" that is less than "2"
            }
            while (!st.empty() && st.top() < nums[i]) {
                third = st.top(); // Update "2" (nums[k])
                st.pop();
            }
            st.push(nums[i]); // Push potential "3" (nums[j])
        }

        return false;
    }
};

func find132pattern(nums []int) bool {
    stack := []int{}
    third := math.MinInt32 // The "2" in 132

    // Traverse from right to left
    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] < third {
            return true // Found "1" that is less than "2"
        }
        for len(stack) > 0 && stack[len(stack)-1] < nums[i] {
            third = stack[len(stack)-1] // Update "2" (nums[k])
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, nums[i]) // Push potential "3" (nums[j])
    }

    return false
}

# @param {Integer[]} nums
# @return {Boolean}
def find132pattern(nums)
    stack = []
    third = -Float::INFINITY # The "2" in 132

    # Traverse from right to left
    (nums.length - 1).downto(0) do |i|
        return true if nums[i] < third # Found "1" that is less than "2"

        while !stack.empty? && stack.last < nums[i]
            third = stack.pop # Update "2" (nums[k])
        end
        stack.push(nums[i]) # Push potential "3" (nums[j])
    end

    false
end

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    heights.push(0); // Add sentinel
    const stack = [];
    let maxArea = 0;

    for (let i = 0; i < heights.length; i++) {
        while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
            const h = heights[stack.pop()];
            // If stack is empty, it means h was the smallest so far, so width stretches from 0 to i
            const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }

    return maxArea;
};

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0) # Sentinel
        stack = []
        max_area = 0

        for i, h in enumerate(heights):
            while stack and h < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        return max_area

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;

        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i]; // Sentinel
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0); // Sentinel
        stack<int> st;
        int maxArea = 0;

        for (int i = 0; i < heights.size(); ++i) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        return maxArea;
    }
};

func largestRectangleArea(heights []int) int {
    heights = append(heights, 0) // Sentinel
    var stack []int
    maxArea := 0

    for i, h := range heights {
        for len(stack) > 0 && h < heights[stack[len(stack)-1]] {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]

            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }

            if area := height * width; area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

# @param {Integer[]} heights
# @return {Integer}
def largest_rectangle_area(heights)
    heights << 0 # Sentinel
    stack = []
    max_area = 0

    heights.each_with_index do |h, i|
        while !stack.empty? && h < heights[stack.last]
            height = heights[stack.pop]
            width = stack.empty? ? i : i - stack.last - 1
            max_area = [max_area, height * width].max
        end
        stack.push(i)
    end

    max_area
end

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const stack = [];
    let water = 0;

    for (let i = 0; i < height.length; i++) {
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const bottom = stack.pop();

            if (stack.length === 0) break;

            const left = stack[stack.length - 1];
            const width = i - left - 1;
            const boundedHeight = Math.min(height[i], height[left]) - height[bottom];
            water += width * boundedHeight;
        }
        stack.push(i);
    }

    return water;
};

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        water = 0

        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                bottom = stack.pop()

                if not stack:
                    break

                left = stack[-1]
                width = i - left - 1
                bounded_height = min(h, height[left]) - height[bottom]
                water += width * bounded_height

            stack.append(i)

        return water