Skip to content

Instantly share code, notes, and snippets.

@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
@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 64. Minimum Path Sum.py
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
"""
Brute force:
We try to find all possible paths from upper-left to lower-right, and find minimum out of them. The time complexity is 2 raist to power of (m+n).
T: O(2*m+n)
DP:
T: O(mn), where m is number of rows and n is number of columns
S: O(mn)
View 673. Number of Longest Increasing Subsequence.py
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
"""
DP two-pass version, which it is often easier to think about recursive formulation than below one-pass version.
T: O(2 * n**2)
S: O(2*n)
"""
n = len(nums)
# edge case
View 416. Partition Equal Subset Sum.py
class Solution:
def canPartition(self, nums: List[int]) -> bool:
"""
After thinking in a way, whether it's able to find a subset of element could construct half of sum of all elments in the array. Then, it's a typical 0/1 knapsacks problem.
Let's assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers or not
T: O(n*w), where n is number of elements in array and w is half of sum
S: O(n*w)
"""
View 72. Edit Distance.py
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
"""
It's a typical dp problem. Edit distance is the minimum number of editing operations needed to transform a string into another string.
Given two strings and three operation allowed to operate on the string:
1.insert char
2.replace char
3.delete char
, to find minimum number of operations required to transform word1 to word2.