Skip to content

Instantly share code, notes, and snippets.

Avatar

Ray liyunrui

  • Singapore
View GitHub Profile
@liyunrui
liyunrui / 52. N-Queens II.py
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
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.
@liyunrui
liyunrui / 51. N-Queens.py
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
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"
@liyunrui
liyunrui / Priority-Queue.md
Last active Apr 30, 2020
Priority Queue/ Min-Heap
View Priority-Queue.md
Data Structure Leetcode Problems Purpose Operation
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
"""
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]
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
@liyunrui
liyunrui / 37. Sudoku Solver.py
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.
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