Buckets:
| tags: | |
| - notes | |
| - stack | |
| ### [Valid Parentheses](https://neetcode.io/problems/validate-parentheses) EASY | |
| You are given a string `s` consisting of the following characters: `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`. | |
| The input string `s` is valid if and only if: | |
| Every open bracket is closed by the same type of close bracket. Open brackets are closed in the correct order. Every close bracket has a corresponding open bracket of the same type. | |
| - Every open bracket is closed by the same type of close bracket. | |
| - Open brackets are closed in the correct order. | |
| - Every close bracket has a corresponding open bracket of the same type. | |
| Return `true` if `s` is a valid string, and `false` otherwise. | |
| ``` | |
| **Example 1:** | |
| Input: s = "[]" | |
| Output: true | |
| **Example 2:** | |
| Input: s = "([{}])" | |
| Output: true | |
| **Example 3:** | |
| Input: s = "[(])" | |
| Output: false | |
| **Explanation: The brackets are not closed in the correct order.** | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution with `O(n)` time and `O(n)` space, where `n` is the length of the given string. | |
| #### **Solution** | |
| To determine if a given string of parentheses `s` is valid, we can use a stack data structure. We iterate through each character in `s`, and if the character is an opening parenthesis (`(`, `{`, `[`), we push it onto the stack. If the character is a closing parenthesis (`)`, `}`, `]`), we check if the stack is empty or if the top element of the stack does not match the current closing parenthesis. If either of these conditions is met, we know the string is not valid. Otherwise, we pop the top element from the stack. At the end, if the stack is empty, the string is valid. | |
| ```python | |
| class Solution: | |
| def isValid(self, s: str) -> bool: | |
| stack = [] | |
| char_map = { | |
| ")": "(", | |
| "]": "[", | |
| "}": "{" | |
| } | |
| for char in s: | |
| if char in char_map: | |
| if stack and stack[-1] == char_map[char]: | |
| stack.pop() | |
| else: | |
| return False | |
| else: | |
| stack.append(char) | |
| return len(stack) == 0 | |
| ``` | |
| ### [Minimum Stack](https://neetcode.io/problems/minimum-stack) MEDIUM | |
| Design a stack class that supports the `push`, `pop`, `top`, and `getMin` operations. | |
| `MinStack()` initialises the stack object.`void push(int val)` pushes the element `val` onto the stack.`void pop()` removes the element on the top of the stack.`int top()` gets the top element of the stack.`int getMin()` retrieves the minimum element in the stack. | |
| - `MinStack()` initialises the stack object. | |
| - `void push(int val)` pushes the element `val` onto the stack. | |
| - `void pop()` removes the element on the top of the stack. | |
| - `int top()` gets the top element of the stack. | |
| - `int getMin()` retrieves the minimum element in the stack. | |
| Each function should run in O(1)_O_(1) time. | |
| ```python | |
| **Example 1:** | |
| Input: ["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"] | |
| Output: [null,null,null,null,0,null,2,1] | |
| **Explanation:** | |
| MinStack minStack = new MinStack(); | |
| minStack.push(1); | |
| minStack.push(2); | |
| minStack.push(0); | |
| minStack.getMin(); # return 0 | |
| minStack.pop(); | |
| minStack.top(); # return 2 | |
| minStack.getMin(); # return 1 | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution with `O(1)` time for each function call and `O(n)` space, where `n` is the maximum number of elements present in the stack. | |
| #### Solution | |
| ```python | |
| class MinStack: | |
| def __init__(self): | |
| self.stack = [] | |
| self.prefix_stack = [] | |
| def push(self, val: int) -> None: | |
| self.stack.insert(0, val) | |
| if self.prefix_stack: | |
| if self.prefix_stack[0] > val: | |
| self.prefix_stack.insert(0, val) | |
| else: | |
| self.prefix_stack.insert(0, self.prefix_stack[0]) | |
| else: | |
| self.prefix_stack.insert(0, val) | |
| def pop(self) -> None: | |
| self.stack = self.stack[1:] | |
| self.prefix_stack = self.prefix_stack[1:] | |
| def top(self) -> int: | |
| return self.stack[0] | |
| def getMin(self) -> int: | |
| return self.prefix_stack[0] | |
| ``` | |
| ### Evaluate Reverse Polish Notation | |
| You are given an array of strings `tokens` that represents a valid arithmetic expression in [Reverse Polish Notation](https://en.wikipedia.org/wiki/Reverse_Polish_notation). Return the integer that represents the evaluation of the expression. The operands may be integers or the results of other operations.The operators include `'+'`, `'-'`, `'*'`, and `'/'`.Assume that division between integers always truncates toward zero. | |
| - The operands may be integers or the results of other operations. | |
| - The operators include `'+'`, `'-'`, `'*'`, and `'/'`. | |
| - Assume that division between integers always truncates toward zero. | |
| ```python | |
| **Example 1: | |
| Input: tokens = ["1","2","+","3","*","4","-"] | |
| Output: 5 | |
| Explanation: ((1 + 2) * 3) - 4 = 5** | |
| ``` | |
| > [!info] **Time and Space Complexity** | |
| > You should aim for a solution with `O(n)` time and `O(n)` space, where `n` is the size of the input array. | |
| #### **Solution** | |
| To evaluate a given reverse Polish notation expression, we can use a stack data structure. We iterate through the tokens in the expression, and for each token, if it is a number, we push it onto the stack. If it is an operator (`+`, `-`, `*`, `/`), we pop the top two elements from the stack, apply the operator to them, and push the result back onto the stack. At the end, the top element of the stack will be the final result of the expression. | |
| ```python | |
| class Solution: | |
| def evalRPN(self, tokens: List[str]) -> int: | |
| stack = [] | |
| for token in tokens: | |
| if token == "+": | |
| stack.append(stack.pop() + stack.pop()) | |
| elif token == "-": | |
| a, b = stack.pop(), stack.pop() | |
| stack.append(b - a) | |
| elif token == "*": | |
| stack.append(stack.pop() * stack.pop()) | |
| elif token == "/": | |
| a, b = stack.pop(), stack.pop() | |
| stack.append(int(float(b) / a)) | |
| else: | |
| stack.append(int(token)) | |
| return stack[-1] | |
| ``` | |
| ### Daily Temperatures | |
| You are given an array of integers `temperatures` where `temperatures[i]` represents the daily temperatures on the `ith` day. Return an array `result` where `result[i]` is the number of days after the `ith` day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the `ith` day, set `result[i]` to `0` instead. | |
| ```python | |
| Example 1: | |
| Input: temperatures = [30,38,30,36,35,40,28] | |
| Output: [1,4,1,2,1,0,0] | |
| Example 2: | |
| Input: temperatures = [22,21,20] | |
| Output: [0,0,0] | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the size of the input array. | |
| #### **Solution** | |
| Create an empty list of size of the `temperature` list filled with zeros and an empty stack. Start iterating the `temperatures` list. Pop out all the elements from the stack, if available and it’s temperature is lower than current temperature, and store the difference between the current temperature index and the popped temperature index, in the res at that popped temperature index. And finally append the index and temperature to stack, as usual. | |
| ```python | |
| class Solution: | |
| def dailyTemperatures(self, temperatures: List[int]) -> List[int]: | |
| stack = [] | |
| res = [0] * len(temperatures) | |
| for idx, temp in enumerate(temperatures): | |
| while stack and temp > stack[-1][1]: | |
| _idx, _temp = stack.pop() | |
| res[_idx] = idx - _idx | |
| stack.append((idx, temp)) | |
| return res | |
| ``` | |
| ### [**Car Fleet](https://neetcode.io/problems/car-fleet?list=neetcode150) MEDIUM** | |
| There are `n` cars traveling to the same destination on a one-lane highway. You are given two arrays of integers `position` and `speed`, both of length `n`. | |
| `position[i]` is the position of the `ith car` (in miles)`speed[i]` is the speed of the `ith` car (in miles per hour) | |
| - `position[i]` is the position of the `ith car` (in miles) | |
| - `speed[i]` is the speed of the `ith` car (in miles per hour) | |
| The destination is at position `target` miles. | |
| A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it. | |
| A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet. | |
| If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet. | |
| Return the number of different car fleets that will arrive at the destination. | |
| ```python | |
| Example 1: | |
| Input: target = 10, position = [1,4], speed = [3,2] | |
| Output: 1 | |
| Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, | |
| meeting each other at 10, the destination. | |
| Example 2: | |
| Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1] | |
| Output: 3 | |
| Explanation: The cars starting at 4 and 7 become a fleet at position 10. | |
| The cars starting at 1 and 0 never catch up to the car ahead of them. | |
| Thus, there are 3 car fleets that will arrive at the destination. | |
| ``` | |
| > [!info] **Time and Space Complexity** | |
| > You should aim for a solution with `O(nlogn)` time and `O(n)` space, where `n` is the size of the input array. | |
| #### Solution | |
| Start by sorting joint `position` and `speed` basis of position. Create a stack and start appending the cars’ time taken to reach destination. The stack must keep the time taken to reach destination for that car which takes time either more or equal to current time. E.g.: If Current car will take 3 hr to reach and previous car took 4 hr to reach, these two cars create a fleet, so 4 will remain in the stack top. | |
| ```python | |
| class Solution: | |
| def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: | |
| sorted_speed_position = sorted([(p, s) for p, s in zip(position, speed)], key=lambda x : x[0], reverse=True) | |
| res = [] | |
| for i in range(len(sorted_speed_position)): | |
| travel_distance = target - sorted_speed_position[i][0] | |
| curr_speed = sorted_speed_position[i][1] | |
| time_taken = travel_distance / curr_speed | |
| if res and res[-1] >= time_taken: | |
| res.append(max(time_taken, res.pop())) | |
| else: | |
| res.append(time_taken) | |
| return len(res) | |
| ``` |
Xet Storage Details
- Size:
- 10.2 kB
- Xet hash:
- b2e81bad3a904bfec2ab9cdb12a80f2954a7683944ff466bb745ea9e61422b57
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.