Home

138. Copy List with Random Pointer Solution 1 - O(n) space Keep a 2-way dictionary for .random def copyRandomList(self, head): """ :type head: Node :rtype: Node """ tail, htail = Node(0), head res = tail idx_node, node_idx = {}, {} idx = 0 while htail: idx_node[idx] = Node(htail.val) node_idx[htail] = idx tail.next...

221. Maximal Square Solution Reference Keep the length of the square instead of the area. The length of a square depends on the 3 girds which are neighbors to it. The smallest decides its length. def maximalSquare(self, matrix): """ :type matrix: List[List[str]] :rtype: int """ if matrix is None or len(matrix) == 0: ...

142. Linked List Cycle II Solution H: distance from head to cycle entry E, D: distance from E to X, L: cycle length 2H + 2D = H + D + L –> H + D = nL –> H = nL - D Thus if two pointers start from head and X, respectively, one first reaches E, the other also reaches E. [Reference](https://leetcode.com/pro...

148. Sort List Solution - Merge Sort Cleaner Solution def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ curr = head l = 0 while curr is not None: l += 1 curr = curr.next return self.mergesort(head, l) def mergesort(self, head, l): if head is None or head.next...

240. Search a 2D Matrix II Solution 1 Find a sub-matrix for searching. Apply binary search to each row/col of the sub-matrix. def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if len(matrix) == 0 or len(matrix[0]) == 0: return False ridx = 0 for i, r in...

416. Partition Equal Subset Sum Solution 1 If the sum sum of the array is odd, it cannot be partitioned. If any element in the array is greater than target = sum / 2, it cannot be partitioned. If target is in the array, it can be partitioned directly. Otherwise try with (a) keep the first num or (b) discard ...

438. Find All Anagrams in a String Solution Use a sliding window to scan through s. Check if the characters in the window is the same as those in p. Can use an array where index represents the character and element represents the count as well. ```python def findAnagrams(self, s, p): “”” :type s: str :type p: str ...

560. Subarray Sum Equals K Solution Reference Whenever the sums has increased by a value of k, we’ve found a subarray of sums=k. 0 is needed as the initial value to find the first subarray. def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ sums = 0 res = 0 ...