liyunrui

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        """
        Brute force:
            We try to find all possible paths from upper-left to lower-right, and find minimum out of them. The time complexity is 2 raist to power of (m+n).
            T: O(2*m+n)
            
        DP:
            T: O(mn), where m is number of rows and n is number of columns
            S: O(mn)

liyunrui

class Solution:
    """
    Problem Clarification
        -We must ask interviewer to go through the examples.
        -You can even go through another examples to make sure there's no misunderstanding.
        -Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative?
            1.should given amount is larger than 0
            2.there's no negatvie coins
            
    Thought Process:

liyunrui

class Solution:
    """    
    Problem Clarification
        -We must ask interviewer to go through the examples.
        -You can even go through another examples to make sure there's no misunderstanding.
        -Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative?
            duplicates? -> yes
            strictly increasing?  means [2,5,5] won't count as valid LIC
            
    Thought Process

liyunrui

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        """
        After thinking in a way, whether it's able to find a subset of element could construct half of sum of all elments in the array. Then, it's a typical 0/1 knapsacks problem.
        
        Let's assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers or not
        
        T: O(n*w), where n is number of elements in array and w is half of sum
        S: O(n*w)
        """

liyunrui

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        """
        DP two-pass version, which it is often easier to think about recursive formulation than below one-pass version.
        
        T: O(2 * n**2)
        S: O(2*n)
        """
        n = len(nums)
        # edge case

liyunrui

class Solution:
    """
    Problem Clarificaitin:
        at least we have one coin to choose right?
        
    Thought Process:
         Brute Force[backtrackiing]
         
         DP:
            Let's define our subproblem total nb of combinations that make up amount j using fisrt i coin only , store sol to dp[i][j], where i <= len(coins) and j <= given amount

liyunrui

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        """
        It's a typical dp problem. Edit distance is the minimum number of editing operations needed to transform a string into another string.
        
        Given two strings and three operation allowed to operate on the string:
            1.insert char
            2.replace char
            3.delete char
        , to find minimum number of operations required to transform word1 to word2.

liyunrui

class Solution:
     """
    Thought Process:
        DP: Since if we can reach the current position relies one previous position.
        
        Let's define our subproblem. dp[i]: if we can reach position i
        
        base case i= 0:
            dp[0] = True
        

liyunrui

class Solution:
    """
    PC:
        Can I assume that no duplicate edges will appear in edges
    """
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        """
        Given n nodes and edge list of undirected graph, to find number of connected components.
        
        Note:

liyunrui

class UnionFindSet:
    def __init__(self, n):
        #Initially, all elements are single element subsets.
        self._parents = [node for node in range(n)]
        # it's like height of tree but it's not always equal to height because path compression technique.
        self._ranks = [1 for i in range(n)]
    
    def find(self, u):
        """
        The find method with path compression, return root of node x, whih can be found by following the chain that begins at x.