Tricks

• paretheses pairing
• monotuous stack

ProblemSet

• valid parentheses
• trapping rain water
• simplify path
• largest rectangle in histogram
• binary tree inorder traversal
• binary tree zigzag level order traversal
• bianry tree preorder traversal
• bianry tree postorder traversal
• evaluate reverse polish notation
• min stack
• binary search tree iterator
• basic calculator
• implement stack using queues
• basic calculator II
• implement queue using stacks
• verify preorder serialization of a binary tree
• flatten nested list iterator
• mini parser
• decode string
• remove k digits
• 132 pattern
• next greater element I
• next greater element II
• exclusive time of functions
• baseball game
• number of atoms
• asteroid collision
• daily temperatures
• backspace string compare
• scroe of parentheses
• decoded string at index
• maximum frequency stack
• online stock span
• sum of subarray minimums
• minimum add to make parentheses valid
• validate stack sequences
• check if word is valid after substitutions
• next greater node in linked list
• remove outermost parentheses
• remove all adjacent duplicates in string
• reverse substrings between each pair of parentheses
• remove all adjacent duplicates in string II
• minimum remove to make valid parentheses
• find the most competitive subsequence

Solutions

Valid Parenthesis

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
  def solution(self, s: str) -> bool:
    min_need = max_need = 0
    for c in s:
      if c == '(':
        min_need += 1
        max_need += 1
      elif c == ')':
        min_need -= 1
        max_need -= 1
      else:
        min_need -= 1
        max_need += 1
      if max_need < 0:
        return False
    return min_need == 0