liyunrui

class Solution:
    def totalNQueens(self, n: int) -> int:
        """
        T: O(n!). There's n choices to put the first queen in first row, then not
        more than n(n-2) to put the second one, and etc. Therefore, time complexity is
        n factorial.
        
        We use two 1-D arrays to represetn diagonals because it's a vector.
        """
        self.count = 0

liyunrui

Data Structure	Leetcode Problems	Purpose	Operation

liyunrui

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """
        Greedy problem because of pattern: "Find minimum or maximum number of something to do something"
        
        T: O(nlogn)
        S: O(1). No extra space is used.
        
        Reference: https://leetcode.com/problems/non-overlapping-intervals/discuss/276056/Python-Greedy-Interval-Scheduling
        """

liyunrui

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        """
        There're two major portions that take up time.
        One is sorting part, we sort the intervals based on starting time, which takes O(nlogn) time.

        Another one is we use min-heap. We have N operations of insertion or extraction totally. It takes O(n * log(n)) time.

        T: O(nlogn)
        S: O(n) because in the worse case, we might contains N elements in min-heap

liyunrui

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        
        Brute Force
        1. Generate all possible boards
        2. To check if it's a valid sudoku board. 
        So, the operation is exponential amount.
        T(9**81), where 9 is # choices we can make to fill empty cell and 81 is number of cells we need to fill in the grid.

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:
    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:
    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 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:
    def canJump(self, nums: List[int]) -> bool:
        """
        Greedy Approach
        
        To determine Greedy strategy:
            1.What's our locally optimal solution at each step(index)?
                1.1. if max position the one could reach starting from the current index i or before less than current index i --> impossible to reach current index i from index < i. Clearly, it leads to impossible to reach the last index.
                
                1.2. keep track max position the one could reach starting from the current index i or before.