Skip to content

Instantly share code, notes, and snippets.


Ray liyunrui

View GitHub Profile
liyunrui / 52. N-Queens
Last active Apr 25, 2020
leetcode backtracking
View 52. N-Queens
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
View 22. Generate
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 / 51.
Created Apr 25, 2020
View 51.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
Brute force is to generate all possible ways to put N queens on the
board, which is O(n**n), n raised to power of n
With backtracking, Time complexity is O(n!)
ans = []
View 17. Letter Combinations of a Phone
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, there's 3^m*4*k nodes in last level of recursion tree, where m+k=n. n = len(input),
where m is number of digits that maps to 3 letters and k is number of digits that maps to 4 letters.
So, this is our running time.
liyunrui /
Last active Apr 30, 2020
Priority Queue/ Min-Heap
Data Structure Leetcode Problems Purpose Operation
View 435. Non-overlapping
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.
View 452. Minimum Number of Arrows to Burst
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]
View 253. Meeting Rooms
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 / 37. Sudoku
Last active May 3, 2020
View 37. Sudoku
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.
View 300. Longest Increasing
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?
strictly increasing?
Thought Process
You can’t perform that action at this time.