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

class Solution:
    """
    Problem Clarification:
        What's definition of well-formed parethenses?
            "()" is o
            ")(" is x
    Thought Process:
        Brute Froce:
            
        Backtracking: it's a recursive search algorithm. 

liyunrui

class Solution:
    """
    Thought Porcess:
     ----------->x
     0 1 2 3
    0
    1
    2
    3
    

liyunrui

class Solution:
    """
    Thought Process:
        we need variable called cur_digit_idx to tell us which level we're in the recursion tree during backtracking.
    
    Time complexity analysis:
        we're going to have n depth of recursion tree. And, for each node we might have 3 choices or 4 choices to go deeper. So, running time would be O(3**m * 4**k), where m+k=n and n = len(input), m is number of digits that map to 3 letters and k is number of digits that map to 4 letters. 
        
    Test case
         digits = "2"

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 findMinArrowShots(self, points: List[List[int]]) -> int:
        n = len(points)
        # edge case
        if n == 0:
            return 0
        ending_time, ans = float('-inf'), 0 # the earliest end time
        # sort the balloons by their end x-coordinate
        for i in sorted(points, key=lambda x: x[1]):
            start_time = i[0]

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:
    """    
    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?
            strictly increasing?
            
    Thought Process