Leetcode Patterns

Prefix[i] will have value calculated till ith index. Subarray sum equals k res = 0 presumToCount = defaultdict(int) presum = 0 for num in nums: presum += num if presum == k: res += 1 res += presumToCount[presum - k] presumToCount[presum] += 1 return res Problems 2845. Count of Interesting Subarrays 1915. Number of Wonderful Substrings Similar to sub array sum equals k, but we use bitmask and xor operations on the prefix values to find the substrings with zero odd count (prefix is zero) and with 1 odd count....

We shrink and grow the window based on the conditions left = 0 for right in range(len(arr)): # logic while grown phase if/while <shrink condition>: # logic while shrink phase Problems 2799. Count Complete Subarrays in an Array 2962. Count Subarrays Where Max Element Appears at Least K Times 992. Subarrays with K Different Integers 2444. Count Subarrays With Fixed Bounds

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/ 2444. Count Subarrays With Fixed Bounds

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....

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....