My website

class Solution: def scheduleCourse(self, courses: List[List[int]]) -> int: """ tc O(NlgN) sc O(N) main idea: greedy 1. sort by ddl then push duration into heap (note, in negtive value) 2. start from t=0, if t +current_duration <= ddl, push into hp 3. if hp[0] > current_duration, pop out bigger duration,... [Read More]

DP solution ```python class Solution: def numSquares(self, n: int) -> int: “”” tc O(NlnN) sc O(N) “”” # dp[i]: given number is i, the least number of perfect squares that sum to i dp = [n]*(n+1) dp[0] = 0 for x in range(1,n+1): i = 1 for i in range(1,int(sqrt(x))+1):... [Read More]

```python class Solution: def prevPermOpt1(self, A: List[int]) -> List[int]: “”” main idea: two ptr to find two elements in array, swap them. there are several cases to consider: (1) len of A <2; (2) A is in ascending order => nothing to swap since it’s already smallest permutation (3)when look... [Read More]

```python class Solution: def diStringMatch(self, S: str) -> List[int]: “"”tc O(N) sc O(N) 1. initialize left ptr and right ptr 2. go through S, check if s == ‘D’ or ‘I’ 3. if s == ‘I’, append left value; otherwise append right value 4. add the rest left ptr to... [Read More]

```python class Solution: def shortestBridge(self, A: List[List[int]]) -> int: “"”tc O(RC) sc O(RC) 1. mark one of island as 2 2. dfs at each pos, spread 4 dirs, find each # island, push it to q 3. bfs to iterate all coordinates in queue, check 4 directions, if they has... [Read More]