Valid Parentheses
🔹 Logic
Initialize an empty stack.
Traverse the string character by character
– If the character is an opening bracket ((, [, {), push it onto the stack.
– If it’s a closing bracket (), ], }):
– Pop the top element from the stack.
– Check if it matches the correct opening bracket.
– If it doesn’t match → return false.
After traversal, if the stack is empty, all brackets were validly paired → return true.
Otherwise, return false.
⏱️ Time ComplexityO(n) — each character is processed once.
💾 Space ComplexityO(n) — for the stack in the worst case (all opening brackets).
Basic Calculator
🔹 Logic
Parse the string character by character to build tokens (numbers, operators, and parentheses).
→ Ignore spaces.
Store tokens in numArr.
Iterate through the tokens in reverse order and use a stack to evaluate expressions.
When encountering (, process until matching ) by popping elements and performing additions/subtractions.
Push computed results back to the stack.
After all parentheses are resolved, evaluate the remaining stack linearly for any remaining + or - operations.
Return the final computed result.
⏱️ Time ComplexityO(n) — each character and token is processed a constant number of times.
💾 Space ComplexityO(n) — for storing tokens and stack elements.
Evaluate Reverse Polish Notation (RPN)
🔹 Logic
Initialize an empty stack.
Iterate through each token in the input list:
If the token is a number, push it onto the stack.
If the token is an operator (+, -, *, /):
Pop the top two numbers from the stack (say b and a).
Apply the operation b (operator) a.
Push the result back onto the stack.
After processing all tokens, the stack will contain one element — the final result.
Return that result.
⏱️ Time ComplexityO(n) — each token is processed exactly once.
💾 Space ComplexityO(n) — for storing intermediate results in the stack.
Min Stack
🔹 Logic
Use two stacks:stack_arr → stores all pushed values.min_stack → keeps track of the minimum value at each level.
Push (val):
Push val into stack_arr.
Push min(val, currentMin) into min_stack.
Pop():
Pop the top element from both stacks.
Top():
Return the top of stack_arr.
getMin():
Return the top of min_stack, which always holds the minimum value so far.
⏱️ Time ComplexityO(1) for all operations (push, pop, top, getMin).
💾 Space ComplexityO(n) — for storing elements and their corresponding minimums.
Simplify Path
🔹 Logic
Split the input path by '/' to get all directory components.
Initialize an empty stack to build the simplified path.
Iterate through each part:
If the part is '', '.', or '/', ignore it.
If the part is '..', pop the last directory from the stack (go one level up).
Otherwise, push the directory name into the stack.
Join the stack contents with '/' and prepend '/' to form the absolute path.
If the stack is empty, return '/'.
⏱️ Time ComplexityO(n) — each directory part is processed once.
💾 Space ComplexityO(n) — for storing directory names in the stack.
