Stack

Question 1

20. Valid Parentheses (Easy)

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:
Input: s = “()”
Output: true

Example 2:
Input: s = “()[]{}”
Output: true

Example 3:
Input: s = “(]”
Output: false

Answer 1

Stack problem!

Iterate through the string and for each iteration, check to see if it’s either an opening symbol or a closing symbol.

If it’s closing, it needs to match the opening tag on the top of the stack.

1. Remove edge cases (empty string and strings with odd numbered length)
2. Create stack(array) and pairs object with opening and closing values.
3. Loop through the string…3a. if it’s an opening symbol, add it to the stack3b. if it’s a closing symbol pop the most recent symbol off the stack and save to variable3c. If the variable matches the value of pairs[lastOpeningSymbol]

Question 2

739. Daily Temperatures (Medium)

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Answer 2

Stack problem!

monotonic decreasing stack problem! our stack is always going to be in decreasing order, so only add lower temperature values for the stack. if it’s higher, pop off the top of the stack, if it’s lower, push onto the stack.

Question 3

155. Min Stack (Medium)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

What do you need to solve this?
Why can’t you just use a variable for min?
What’s the process for pushing?
Both arrays should be…

Answer 3

Use 2 Arrays
use two arrays in minStack, one for the complete stack and one for minStack.

Why not variable?
what if you pop off that min? need to know what the next min is

push by comparing
when pushing, compare the pushed val to last value of the minStack. if it’s less than or equal to, push the val BUT if it’s not, just push another instance of the last value.

Both arrays should be the same length
This way the “top” value in the stack or the last in the array is always the minimum