My website

class Solution: def breakPalindrome(self, s: str) -> str: """ tc O(N) sc O(N) main idea: loop through half of the string, find the first char not equal to 'a', change it to 'a' otherwise: change last position'char to 'b' """ n = len(s) if n == 1: return "" res... [Read More]

```python class Solution: def minKnightMoves(self, x: int, y: int) -> int: “”” tc O(XY) sc O(XY) main idea: limit the search on board onto quardrant. take care of edge case where going to (1,1) from (0,0) takes 2 steps “”” x,y = abs(x),abs(y) if x ==1 and y == 1:... [Read More]

Bucket Sort Solution class Solution: def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int: """ main idea: bucket sort tc O(N) sc O(1000) """ total_box = total_val = 0 # optimization buckets = [0] *1001 for box, units in boxTypes: total_box += box # optimization total_val += units*box # optimization buckets[units]... [Read More]

import heapq class Solution: def minimumCost(self, n: int, connections: List[List[int]]) -> int: """ main idea: MST (Prim) tc O((E+V)*lgE + E) sc O(E+V) 1. build graph based on connections 2. create a priority queue, put any start point along with its cost in the queue to start 3. pop off... [Read More]

class Solution: def __init__(self, w: List[int]): """ main idea: presum + binary search tc O(N) sc O(N) """ self.psum = [0] * len(w) self.psum[0] = w[0] for i in range(1,len(w)): self.psum[i] = self.psum[i-1] + w[i] # can update directly from array w def pickIndex(self) -> int: """tc O(lgN) sc O(1)... [Read More]