Programming

Problem Given an integer array  nums , return the length of the longest strictly increasing subsequence. Solution DP. Second solution can be O(nlg(n)) First solution : Two for loops checking for each number, what would be the max subsequence based on 1 to n-1. Second solution : Build a sequence, whose i-th position stores the best option (number) for subsequences of length i . Use binary search to make the search log(n) The second approach does not build a single subsequence does produce the correct length. # First: DP, O(N 2 ) from typing import List def lengthOfLIS ( self , nums : List [ int ]) -> int :     local_sol = [ 1 ]*( len ( nums ))     global_sol = 1     for i in range ( 1 , len ( nums )):         for j in range ( i ):             if nums [ i ] > nums [ j ]:                 local_sol [ i ] = max ( local_sol [ i ], local_sol [ j ]+ 1 )...

   Problem Given a set of balloons (start, end), find number of arrows needed to burst. An arrow bursts all the balloons in its vertical path. Solution Greedy. Trick is to sort them by 'end'. Keep a current end that for the current row.  Every time, a balloon starts after the current end Increase the arrow count.  # Greedy def findMinArrowShots ( self , points : List [ List [ int ]]) -> int :                   if not points :             return 0                 points . sort ( key = lambda x : x [ 1 ])             cur_end = points [ 0 ][ 1 ]         arrow = 1                 for start , end in points :             if start > cur_end :                 arrow += 1     ...

  Problem Given the  root  of a binary search tree, and an integer  k , return  the   k th   smallest value ( 1-indexed ) of all the values of the nodes in the tree . Solution In-order traversal. Recursive or Iterative. Recursive is easy but need to traverse entire tree Or add a lot of ugly code. Iterative is tricky. Two while loops. One always slides to the left. The root is like a pointer.  It does not always come from the stack! # Iterative def kthSmallest ( self , root : Optional [ TreeNode ], k : int ) -> int :         stack = []         while True :             while root :                 stack . append ( root )                 root = root .left             root = stack . pop ()             k -= 1         ...

Problem Given different coins of infinite amount, find the fewest coins to make up an amount. Solution DP. Can be done recursively or iteratively. Iterative code is much shorter. Top-down recursion: Start with amount and use one coin and find the min for the remaining recursively. Use memoization. Iterative: For 1 to amount find the min coin using min of (amount - coin_i) for each coin. Don't forget to initialize inf and 0 properly. For loops can be swapped! # DP: Iterative from typing import List def coinChange ( self , coins : List [ int ], amount : int ) -> int :                         import math     dp = [ math . inf ] * ( amount + 1 )     dp [0] = 0     for x in range (1, amount + 1):         for coin in coins :             if x >= coin :                 dp [ x ] = min ( dp [ x ], dp...