Flashcards for "Stacks"

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pairs = sorted(zip(position, speed), key=lambda x: x[0], reverse=True)
        fleets = 0
        current_time = 0.0
        for pos, sp in pairs:
            time = (target - pos) / sp
            if time > current_time:
                fleets += 1
                current_time = time
        return fleets

from collections import deque


## Think This: You want the stack to be always decreasing order, if not, pop and make it one. 
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Initialize a stack to keep track of temperatures and their indices.
        stack = deque([])
        
        # Initialize the result list with 0s, each representing the number of days to wait.
        res = [0] * len(temperatures)
        
        # Iterate through the list of temperatures along with their indices.
        for index, current_temp in enumerate(temperatures):
            # While the stack is not empty and the current temperature is higher than 
            # the temperature at the top of the stack (last recorded temperature),
            # pop the stack and calculate the number of days waited for a warmer temperature.
            while stack and stack[-1][0] < current_temp:
                _, index_of_cooler_day = stack.pop()
                res[index_of_cooler_day] = index - index_of_cooler_day
            
            # Push the current temperature and its index onto the stack.
            # This is done for each temperature as we might need to compare 
            # it with future temperatures.
            stack.append((current_temp, index))
        
        # Return the result list containing the number of days to wait for a warmer temperature.
        return res

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            if token not in "+-/*":
                stack.append(int(token))
                continue

            number_2 = stack.pop()
            number_1 = stack.pop()

            result = 0
            if token == "+":
                result = number_1 + number_2
            elif token == "-":
                result = number_1 - number_2
            elif token == "*":
                result = number_1 * number_2
            else:
                result = int(number_1 / number_2)

            stack.append(result)

        return stack.pop()

class Solution:
    def generateParenthesis(self, n):
        result = []
        self.generate(n, "", result, 0, 0)
        return result

    def generate(self, n, partial, result, o_count, c_count):
        if len(partial) == 2 * n and o_count == c_count:
            result.append(partial)
            return
        if c_count < o_count:
            self.generate(n, partial + ")", result, o_count, c_count + 1)
        if len(partial) < 2 * n:
            self.generate(n, partial + "(", result, o_count + 1, c_count)

class Solution(object):
    def largestRectangleArea(self, heights):

        maxArea = 0
        stack = []  # (start_index, height) — monotonic INCREASING by height

        for i, h in enumerate(heights):
            start = i

            # If current bar is smaller, it ends rectangles of taller bars on stack
            while stack and stack[-1][1] > h:
                idx, height = stack.pop()
                maxArea = max(maxArea, height * (i - idx))  # width = i - idx
                start = idx  # current bar can extend left to where popped bar started

            # Push current bar with its leftmost start
            stack.append((start, h))

        # Remaining bars extend to the end of the histogram
        n = len(heights)
        for idx, height in stack:
            maxArea = max(maxArea, height * (n - idx))

        return maxArea

from collections import deque

class MinStack:
    def __init__(self):
        self.stack = deque()
        
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = self.stack[-1][1]
            # Always push the new value along with the updated minimum.
            self.stack.append((val, min(val, current_min)))
        
    def pop(self) -> None:
        self.stack.pop()
        
    def top(self) -> int:
        return self.stack[-1][0]
    
    def getMin(self) -> int:
        return self.stack[-1][1]

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        stack=[]
        
        for c in s:
            if c == '{':
                stack.append('}')
            elif c == '(':
                stack.append(')')
            elif c=='[':
                stack.append(']')
            else:
                if len(stack)==0: return False
                elif(stack.pop()!=c): return False
        
        return len(stack)==0