Scribbling

DP Solution Time complexity: O(M*N**2) class Solution: def splitArray(self, nums: List[int], m: int) -> int: self.nums = nums self.table = [0] * (len(nums)+1) summed = 0 for i in range(len(nums)): summed += nums[i] self.table[i+1] = summed self.dp = {} return self.helper(0, len(nums)-1, m) def helper(self, i, j, m): if m == 1: return self.table[j+1] - self.table[i] if i == j: return self.nums[i]..

Several solutions and short analysis of each one. 1. List + Binary Search The most straightforward solution, however, time complexity is O(N**2). class Solution: def countSmaller(self, nums: List[int]) -> List[int]: from bisect import insort, bisect_left arr = [] count = [] for i in range(len(nums) - 1, -1, -1): num = nums[i] idx = bisect_left(arr, num) count.append(idx) insort(arr, num) return ..

Key idea: one's number of candies is affected by all the left and right neighbors. So we iterate the list twice, forward and backward. class Solution: def candy(self, ratings: List[int]) -> int: n = len(ratings) candies = [1] * n # forward pass for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1 # backward pass for i in range(n-2, -1, -1): if ratings[i] > ratings[i+..

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]: self.ret = [] self.dfs(root) return self.ret def dfs(self, node): if node.left and node.right: h = max(self.dfs(node.left), self.dfs(node.right)) + 1 e..

O(N) Time complexity, O(1) Memory Solution using Recursion # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedListToBST(self, he..

Perhaps, the most thinkable solution would be DFS or BFS. Traverse all the '1' points and update mins and maxs. Time complexity would be O(M*N) in this case. class Solution: def minArea(self, image: List[List[str]], x: int, y: int) -> int: m, n = len(image), len(image[0]) ymin, ymax, xmin, xmax = m, -1, n, -1 dy, dx = [0, 1, 0, -1], [1, 0, -1, 0] stack, visited = [(x, y)], set() while stack: i, ..

First solution is using regular expression. Below is some useful patterns. Integer: ^[+-]?\d+$ Flaot: ^[+-]?((\d+(\.\d*)?)|(\.\d+))$ Sicnetific notation: ^[+-]?((\d+(\.\d*)?)|(\.\d+))[eE][+-]?\d+$ class Solution: def isNumber(self, s: str) -> bool: import re pat = re.compile('(^[+-]?((\d+(\.\d*)?)|(\.\d+))$)|(^[+-]?((\d+(\.\d*)?)|(\.\d+))[eE][+-]?\d+$)') return re.match(pat, s) Second solution i..

A solution using sliding window. class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: from collections import Counter ret = [] wordSet = set(words) n, m = len(words), len(words[0]) for i in range(m): wordCounter = Counter(words) k = j = i while j + m = n * m: if s[k:k+m] in wordSet: wordCounter[s[k:k+m]] += 1 k += m word = s[j:j+m] if word in wordSet: wordCounter[word]..

class Solution: def removeElement(self, nums: List[int], val: int) -> int: length = len(nums) i = 0 while i

First thing to try is iterating nums1, nums2, nums3 and looking for the corresponding element in nums4. This will result in O(N**3) time complexity, which raises TLE. class Solution: def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int: from collections import Counter c = Counter(nums4) ret = 0 for n1 in nums1: for n2 in nums2: for n3 in nums3: re..