Approach Try to solve the problem using brute force. This helps to come up with a logic required for the problem. Identify the pattern. Implement the solution using the pattern. Identify time and space complexity. Tips to match the pattern If the problem involves exploring a search space in a tree or a graph then we can consider BFS or DFS. If the problem requires minimum number of steps then we should use BFS instead of DFS to explore....
class NumArray: def __init__(self, nums: List[int]): self.nums = nums self.n = len(nums) self.k = int(sqrt(self.n)) self.dp = [0] * ((self.n //self. k)+1) for i in range(self.n): self.dp[i//self.k] += self.nums[i] def sumRange(self, left: int, right: int) -> int: s = 0 while left < right and left % self.k != 0 and left != 0: s += self.nums[left] left += 1 while left + self.k - 1 < right: s += self....
Min in rotated sorted array left = 0 right = len(nums)-1 while left < right: if nums[left] < nums[right]: return nums[left] mid = (left + right) // 2 if nums[mid] < nums[right]: right = mid else: left = mid + 1 return nums[left]
Jump game class Solution: def canJump(self, nums: List[int]) -> bool: goal = len(nums) - 1 for i in range(len(nums)-1, -1, -1): if i + nums[i] >= goal: goal = i return goal == 0 # @cache # def dfs(i): # print(i) # if i == len(nums)-1: # return True # for j in range(1, nums[i]+1): # if dfs(i + j): # return True # return False # return dfs(0)
Combination Sum class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] comb = [] def backtrack(start, s): if s > target: return if s == target: res.append(comb[:]) return for i in range(start, len(candidates)): comb.append(candidates[i]) backtrack(i, s + candidates[i]) comb.pop() backtrack(0, 0) return res Combination Sum II 1class Solution: 2 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: 3 candidates.sort() 4 res = [] 5 comb = [] 6 def backtrack(start, s): 7 if s > target: 8 return 9 10 if s == target: 11 res....
Generating bitmask n = len(nums) nth_bit = 1 << n for i in range(2**n): bitmask = bin(i | nth_bit)[3:] print(bitmask) n = len(nums) for i in range(2**n, 2**(n+1)): bitmask = bin(i)[3:] print(bitmask)
Problems 977. Squares of a Sorted Array https://leetcode.com/problems/squares-of-a-sorted-array/description/
Choose the left value Choose the right value Binary search from left to right left = 0 right = len(nums) while left < right: mid = (left + right) // 2 if nums[mid] > target: # This condition can be changed according to the problem right = mid else: left = mid+1 if left > 0 and nums[left-1] == target: return left-1 return -1 Problems 1011. Capacity To Ship Packages Within D Days https://leetcode....
Select right as pivot element and left as fill position from left to right move elements smaller or equal to fill position and move the fill position to right Now p is the kth smallest element def quickselect(l, r): pivot = nums[r] p = l for i in range(l, r): if nums[i] <= pivot: nums[i], nums[p] = nums[p], nums[i] p += 1 nums[p], nums[r] = nums[r], nums[p] if p > k: return quickselect(l, p-1) elif p < k: return quickselect(p+1, r) else: return nums[p]
Problems 2385. Amount of Time for Binary Tree to Be Infected https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/ self.maxDistance = 0 def dfs(node): depth = 0 if not node: return depth leftDepth = dfs(node.left) rightDepth = dfs(node.right) if node.val == start: self.maxDistance = max(leftDepth, rightDepth) depth = -1 elif leftDepth >= 0 and rightDepth >= 0: depth = max(leftDepth, rightDepth) + 1 else: distance = abs(leftDepth) + abs(rightDepth) self.maxDistance = max(self.maxDistance, distance) depth = min(leftDepth, rightDepth) - 1 return depth dfs(root) return self....