Skip to content

Instantly share code, notes, and snippets.


Ray liyunrui

  • Singapore
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.
Last active Feb 9, 2021
View 51.
class Solution:
Thought Porcess:
0 1 2 3
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, 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 /
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