Stack

You are given a string `s` consisting of the following characters: `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`. The input string `s` is valid if and only if: 1. Every open bracket is closed by the same type of close bracket. 2. Open brackets are closed in the correct order. 3. 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:** ```java Input: s = "[]" Output: true ``` **Example 2:** ```java Input: s = "([{}])" Output: true ``` **Example 3:** ```java Input: s = "[(])" Output: false ``` Explanation: The brackets are not closed in the correct order. **Constraints:** * `1 <= s.length <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the given string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to continuously remove valid brackets until no more can be removed. If the remaining string is empty, return true; otherwise, return false. This would result in an <code>O(n^2)</code> solution. Can we think of a better approach? Perhaps a data structure could help. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a stack to store characters. Iterate through the string by index. For an opening bracket, push it onto the stack. If the bracket is a closing type, check for the corresponding opening bracket at the top of the stack. If we don't find the corresponding opening bracket, immediately return false. Why does this work? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> In a valid parenthesis expression, every opening bracket must have a corresponding closing bracket. The stack is used to process the valid string, and it should be empty after the entire process. This ensures that there is a valid substring between each opening and closing bracket. </p> </details>

Design a stack class that supports the `push`, `pop`, `top`, and `getMin` operations. * `MinStack()` initializes 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)$ time. **Example 1:** ```java 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 ``` **Constraints:** * `-2^31 <= val <= 2^31 - 1`. * `pop`, `top` and `getMin` will always be called on **non-empty** stacks. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(1)</code> time for each function call and <code>O(n)</code> space, where <code>n</code> is the maximum number of elements present in the stack. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to always check for the minimum element in the stack for the <code>getMin()</code> function call. This would be an <code>O(n)</code> appraoch. Can you think of a better way? Maybe <code>O(n)</code> extra space to store some information. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a stack to maintain the elements. But how can we find the minimum element at any given time? Perhaps we should consider a prefix approach. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We use an additional stack to maintain the prefix minimum element. When popping elements from the main stack, we should also pop from this extra stack. However, when pushing onto the extra stack, we should push the minimum of the top element of the extra stack and the current element onto this extra stack. </p> </details>

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. **Example 1:** ```java Input: tokens = ["1","2","+","3","*","4","-"] Output: 5 Explanation: ((1 + 2) * 3) - 4 = 5 ``` **Constraints:** * `1 <= tokens.length <= 1000`. * tokens[i] is `"+"`, `"-"`, `"*"`, or `"/"`, or a string representing an integer in the range `[-100, 100]`. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would involve repeatedly finding an operator <code>+ - * /</code> in the array and modifying the array by computing the result for that operator and two operands to its left. This would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe we can use a data structure to handle operations efficiently. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a stack. We iterate through the array, and if we encounter a number, we push it onto the stack. If we encounter an operator, we pop two elements from the stack, treat them as operands, and solve the equation using the current operator. Then, we push the result back onto the stack. Why does this work? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> As the array has postfix expression, stack helps us to maintain the correct order of operations by ensuring that we always use the most recent operands (those closest to the operator) when performing the operation. After the iteration, the final result is left in the stack. </p> </details>

You are given an integer `n`. Return all well-formed parentheses strings that you can generate with `n` pairs of parentheses. **Example 1:** ```java Input: n = 1 Output: ["()"] ``` **Example 2:** ```java Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] ``` You may return the answer in **any order**. **Constraints:** * `1 <= n <= 7` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(4^n / sqrt(n))</code> time and <code>O(n)</code> space, where <code>n</code> is the number of parenthesis pairs in the string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to generate all possible strings of size <code>2n</code> and add only the valid strings. This would be an <code>O(n * 2 ^ (2n))</code> solution. Can you think of a better way? Maybe you can use pruning to avoid generating invalid strings. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking with pruning. But what makes a string invalid? Can you think of a condition for this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> When the count of closing brackets exceeds the count of opening brackets, the string becomes invalid. Therefore, we can maintain two variables, <code>open</code> and <code>close</code>, to track the number of opening and closing brackets. We avoid exploring paths where <code>close > open</code>. Once the string length reaches <code>2n</code>, we add it to the result. </p> </details>

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. **Example 1:** ```java Input: temperatures = [30,38,30,36,35,40,28] Output: [1,4,1,2,1,0,0] ``` **Example 2:** ```java Input: temperatures = [22,21,20] Output: [0,0,0] ``` **Constraints:** * `1 <= temperatures.length <= 1000`. * `1 <= temperatures[i] <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would involve iterating through the array with index <code>i</code> and checking how far is the next greater element to the right of <code>i</code>. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Can you consider a reverse approach? For example, in <code>[2, 1, 1, 3]</code>, the next greater element for the numbers <code>[2, 1, 1]</code> is <code>3</code>. Instead of checking for each element individually, can you think of a way where, by standing at the element <code>3</code>, you compute the result for the elements <code>[2, 1, 1]</code>? Maybe there's a data structure that is useful here. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use a stack to maintain indices in a monotonically decreasing order, popping indices where the values are smaller than the current element. This helps us find the result by using the difference between indices while considering the values at those indices. Can you see how the stack is useful? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> In the array <code>[2, 1, 1, 3]</code>, we don't perform any pop operations while processing <code>[2, 1, 1]</code> because these elements are already in decreasing order. However, when we reach <code>3</code>, we pop elements from the stack until the top element of the stack is no longer less than the current element. For each popped element, we compute the difference between the indices and store it in the position corresponding to the popped element. </p> </details>

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) 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. **Example 1:** ```java 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:** ```java 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. **Constraints:** * `n == position.length == speed.length`. * `1 <= n <= 1000` * `0 < target <= 1000` * `0 < speed[i] <= 100` * `0 <= position[i] < target` * All the values of `position` are **unique**. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(nlogn)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> First draw a picture of all the points which represents the positions and respective speeds of the cars. It is appropriate to represent the position and speed of each car as an array, where each cell corresponds to a car. It is also logical to sort this array based on the positions in descending order. Why? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Because a car can only form a fleet with another car that is ahead of it, sorting the array in descending order ensures clarity about the final speed of each car. Sorting in ascending order would create ambiguity, as the next car might form a fleet with another car while reaching the target, making it difficult to determine its final speed. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Calculating the time for a car to reach the target is straightforward and can be done using the formula: <code>time = (target - position) / speed</code>. Now, it becomes easy to identify that two cars will form a fleet if and only if the car ahead has a time that is greater than or equal to the time of the car behind it. How can we maintain the total number of fleets happened while going through the array? Maybe a data structure is helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use a stack to maintain the times of the fleets. As we iterate through the array (sorted in descending order of positions), we compute the time for each car to reach the target and check if it can form a fleet with the car ahead. If the current car's time is less than or equal to the top of the stack, it joins the same fleet. Otherwise, it forms a new fleet, and we push its time onto the stack. The length of the stack at the end represents the total number of fleets formed. </p> </details>

You are given an array of integers `heights` where `heights[i]` represents the height of a bar. The width of each bar is `1`. Return the area of the largest rectangle that can be formed among the bars. Note: This chart is known as a [histogram](https://en.wikipedia.org/wiki/Histogram). **Example 1:** ```java Input: heights = [7,1,7,2,2,4] Output: 8 ``` **Example 2:** ```java Input: heights = [1,3,7] Output: 7 ``` **Constraints:** * `1 <= heights.length <= 1000`. * `0 <= heights[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A rectangle has a height and a width. Can you visualize how rectangles are formed in the given input? Considering one bar at a time might help. We can try to form rectangles by going through every bar and current bar's height will be the height of the rectangle. How can you determine the width of the rectangle for the current bar being the height of the rectangle? Extending the current bar to the left and right might help determine the rectangle's width. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> For a bar with height <code>h</code>, try extending it to the left and right. We can see that we can't extend further when we encounter a bar with a smaller height than <code>h</code>. The width will be the number of bars within this extended range. A brute force solution would be to go through every bar and find the area of the rectangle it can form by extending towards the left and right. This would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe precomputing the left and right boundaries might be helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> The left and right boundaries are the positions up to which we can extend the bar at index <code>i</code>. The area of the rectangle will be <code>height[i] * (right - left + 1)</code>, which is the general formula for <code>height * width</code>. These boundaries are determined by the first smaller bars encountered to the left and right of the current bar. How can we find the left and right boundaries now? Maybe a data structure is helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use a stack with a monotonically strictly increasing nature, but instead of storing values, we store indices in the stack and perform operations based on the values at those indices. The top of the stack will represent the smaller bar that we encounter while extending the current bar. To find the left and right boundaries, we perform this algorithm from left to right and vice versa, storing the boundaries. Then, we iterate through the array to find the area for each bar and return the maximum area we get. </p> </details>