{{ message }}

Instantly share code, notes, and snippets.

# Ray liyunrui

• Singapore
Last active Apr 25, 2020
leetcode backtracking
View 52. N-Queens II.py
 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
Last active Feb 8, 2021
leetcode-backtracking
View 22. Generate Parentheses.py
 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.
Last active Feb 9, 2021
leetcode-backtracking
View 51. N-Queens.py
 class Solution: """ Thought Porcess: ----------->x 0 1 2 3 0 1 2 3
Last active Feb 1, 2021
leetcode-backtracking
View 17. Letter Combinations of a Phone Number.py
 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"
Last active Apr 30, 2020
Priority Queue/ Min-Heap
View Priority-Queue.md
Data Structure Leetcode Problems Purpose Operation
Created Apr 30, 2020
leetcode-greedy
View 435. Non-overlapping Intervals.py
 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 """
Created Apr 30, 2020
leetcode-greedy
View 452. Minimum Number of Arrows to Burst Balloons.py
 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]
Last active May 1, 2020
leetcode-greedy
View 253. Meeting Rooms II.py
 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
Last active May 3, 2020
leetcode-backtracking
View 37. Sudoku Solver.py
 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.
Last active Oct 31, 2020
leetcode-dp
View 300. Longest Increasing Subsequence.py
 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