Brute Force/Recursion: time O(2^N) space O(H)

class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(i,n):
            if i > n:
                return 0
            if i == n:
                return 1
            return dfs(i+1,n) + dfs(i+2,n) 
        
        return dfs(0,n)
  1. Memoization 
    class Solution:
 def climbStairs(self, n: int) -> int:
     memo = [None] * (n+1)

     def dfs(i,n,memo):
         # step1: base case 
         if i > n:
             return 0
         if i == n:
             return 1
          # step2: check if memo recorded, if yes, return content in memo 
         if memo[i] != None:
             return memo[i]
         # step3: update memo[i]   
         memo[i] = dfs(i+1,n,memo) + dfs(i+2,n,memo)
         #print(memo)
         # step4: return memo[i]
         return memo[i] 
        
     return dfs(0,n,memo)
  2. DP Idea is current steps is affected by previous one and previous two state ```python class Solution: def climbStairs(self, n: int) -> int: # time O(N) space O(N) # step1: edge case if n == 1: return 1 if n == 2: return 2 # step2: initialize dp = [0] *(n+1) dp[1] = 1 dp[2] = 2 # step3: transition formula for i in range(3,n+1): dp[i] = dp[i-1]+dp[i-2] return dp[n]

space optimization
```python
class Solution:
    def climbStairs(self, n: int) -> int:
        dp =  [0] * (n+1)
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            tmp = dp[1] + dp[2]
            dp[1] = dp[2]
            dp[2] = tmp
        return dp[2]

conventional way of QuisckSelection sort


class Solution:
    # time O(N) space O(1)  
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # step1: choose random pivot
        size = len(nums)
        k = size - k
        lo,hi = 0,size-1
        while lo < hi:
            j = self.partition(nums,lo,hi)
            if j < k:
                lo = j+1
            elif j > k :
                hi = j -1 
            else:
                break
        return nums[k]

    def partition(self,arr,lo,hi):
        p = arr[hi]
        i = lo 
        for j in range(lo,hi):
            if arr[j] <= p :
                arr[i],arr[j] = arr[j],arr[i]
                i += 1 
        # swap i and hi 
        arr[i],arr[hi] = arr[hi],arr[i]
        return i