Neetcode1E2

Cheatsheet Content

1. Sort Array by Increasing Frequency Notes: Use a frequency map (dictionary or Counter) to count occurrences. Then sort based on frequency (ascending) and then value (descending) for tie-breaking. from collections import Counter class Solution: def frequencySort(self, nums: list[int]) -> list[int]: freq = Counter(nums) # Sort by frequency ascending, then by value descending nums.sort(key=lambda x: (freq[x], -x)) return nums 2. Sort the People Notes: Pair names with heights, then sort by height in descending order. Extract names from the sorted pairs. class Solution: def sortPeople(self, names: list[str], heights: list[int]) -> list[str]: # Pair (height, name) and sort by height in descending order paired = sorted(zip(heights, names), key=lambda x: x[0], reverse=True) # Extract names from the sorted pairs return [name for height, name in paired] 3. Relative Sort Array Notes: Count frequencies of elements in arr1 . Iterate through arr2 to place elements in order. Collect remaining elements, sort them, and append. from collections import Counter class Solution: def relativeSortArray(self, arr1: list[int], arr2: list[int]) -> list[int]: counts = Counter(arr1) result = [] for x in arr2: result.extend([x] * counts[x]) counts[x] = 0 # Mark as used remaining = [] for x in sorted(counts.keys()): # Iterate sorted keys for remaining elements if counts[x] > 0: remaining.extend([x] * counts[x]) return result + remaining 4. Design Parking System Notes: Initialize an array/list to store available slots for each car type. addCar method decrements the count if space is available and returns true, else returns false. class ParkingSystem: def __init__(self, big: int, medium: int, small: int): self.slots = [0, big, medium, small] # 0-indexed, carType starts from 1 def addCar(self, carType: int) -> bool: if self.slots[carType] > 0: self.slots[carType] -= 1 return True return False 5. Uncommon Words from Two Sentences Notes: Use frequency maps (Counters) for both sentences. An uncommon word appears exactly once in one sentence and zero times in the other. from collections import Counter class Solution: def uncommonFromSentences(self, s1: str, s2: str) -> list[str]: words1 = s1.split() words2 = s2.split() count1 = Counter(words1) count2 = Counter(words2) uncommon = [] for word in count1: if count1[word] == 1 and word not in count2: uncommon.append(word) for word in count2: if count2[word] == 1 and word not in count1: uncommon.append(word) return uncommon 6. Find the Difference of Two Arrays Notes: Convert arrays to sets for efficient membership testing. Find elements unique to each set. class Solution: def findDifference(self, nums1: list[int], nums2: list[int]) -> list[list[int]]: set1 = set(nums1) set2 = set(nums2) ans1 = list(set1 - set2) # Elements in set1 but not in set2 ans2 = list(set2 - set1) # Elements in set2 but not in set1 return [ans1, ans2] 7. Squares of a Sorted Array Notes: Two-pointer approach is efficient. Place pointers at both ends of the original array. Compare absolute values, square the larger one, and place it at the end of a new result array. Move pointers inwards. class Solution: def sortedSquares(self, nums: list[int]) -> list[int]: n = len(nums) result = [0] * n left, right = 0, n - 1 idx = n - 1 while left abs(nums[right]): result[idx] = nums[left] * nums[left] left += 1 else: result[idx] = nums[right] * nums[right] right -= 1 idx -= 1 return result 8. Merge Two 2D Arrays by Summing Values Notes: Use a dictionary to store sums for each ID. Iterate through both arrays, summing values for common IDs. Convert the dictionary back to a sorted list of lists. class Solution: def mergeArrays(self, nums1: list[list[int]], nums2: list[list[int]]) -> list[list[int]]: sums = {} for id, val in nums1: sums[id] = sums.get(id, 0) + val for id, val in nums2: sums[id] = sums.get(id, 0) + val # Sort by ID and convert to list of lists return sorted([[id, total] for id, total in sums.items()]) 9. Merge Strings Alternately Notes: Use two pointers, one for each string. Append characters alternately. Append any remaining characters from the longer string. class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: result = [] i, j = 0, 0 while i 10. Valid Palindrome II Notes: Use a two-pointer approach. If characters at pointers don't match, try skipping one character from either left or right and check if the remaining substring is a palindrome. Only one skip is allowed. class Solution: def validPalindrome(self, s: str) -> bool: def is_palindrome(sub: str) -> bool: return sub == sub[::-1] left, right = 0, len(s) - 1 while left 11. Reverse String Notes: In-place reversal using two pointers. Swap characters at the left and right pointers, then move pointers inwards until they meet or cross. class Solution: def reverseString(self, s: list[str]) -> None: left, right = 0, len(s) - 1 while left 12. Apply Operations to an Array Notes: First pass: iterate and apply doubling/zeroing operations. Second pass: use two pointers (read and write) to move non-zero elements to the front, filling the rest with zeros. class Solution: def applyOperations(self, nums: list[int]) -> list[int]: n = len(nums) for i in range(n - 1): if nums[i] == nums[i+1]: nums[i] *= 2 nums[i+1] = 0 # Move non-zero elements to the front write_idx = 0 for read_idx in range(n): if nums[read_idx] != 0: nums[write_idx] = nums[read_idx] write_idx += 1 # Fill remaining with zeros while write_idx 13. Check If Two String Arrays are Equivalent Notes: Concatenate all strings in each array and then compare the resulting single strings. class Solution: def arrayStringsAreEqual(self, word1: list[str], word2: list[str]) -> bool: return "".join(word1) == "".join(word2) 14. Backspace String Compare Notes: Helper function to process a string with backspaces. Iterate through the string, building a new string (or list of chars). If a '#' is encountered, pop the last character from the built string if it's not empty. Compare the processed strings. class Solution: def backspaceCompare(self, s: str, t: str) -> bool: def process_string(text: str) -> str: stack = [] for char in text: if char == '#': if stack: stack.pop() else: stack.append(char) return "".join(stack) return process_string(s) == process_string(t) 15. Reverse Words in a String III Notes: Split the string into words. For each word, reverse it. Join the reversed words back with spaces. class Solution: def reverseWords(self, s: str) -> str: words = s.split(' ') reversed_words = [word[::-1] for word in words] return " ".join(reversed_words) 16. Sort Array By Parity Notes: Two-pointer approach. One pointer `left` starts at 0, `right` at `n-1`. Move `left` until an odd number is found. Move `right` until an even number is found. Swap them. Continue until `left` and `right` cross. class Solution: def sortArrayByParity(self, nums: list[int]) -> list[int]: left, right = 0, len(nums) - 1 while left 17. Find First Palindromic String in the Array Notes: Iterate through the array of strings. For each string, check if it's a palindrome (e.g., by comparing with its reverse). Return the first one found. class Solution: def firstPalindrome(self, words: list[str]) -> str: def is_palindrome(s: str) -> bool: return s == s[::-1] for word in words: if is_palindrome(word): return word return "" 18. Assign Cookies Notes: Greedy approach. Sort both `g` (greed factors) and `s` (cookie sizes). Iterate through children and cookies, assigning the smallest possible cookie that satisfies a child's greed. Both pointers move forward. class Solution: def findContentChildren(self, g: list[int], s: list[int]) -> int: g.sort() # Sort children's greed factors s.sort() # Sort cookie sizes child_idx = 0 cookie_idx = 0 content_children = 0 while child_idx = g[child_idx]: # Cookie is large enough for child content_children += 1 child_idx += 1 cookie_idx += 1 else: # Cookie too small, try next cookie for current child cookie_idx += 1 return content_children 19. Minimum Difference Between Highest and Lowest of K Scores Notes: Sort the array. The minimum difference for a window of size `k` will always be between `nums[i+k-1]` and `nums[i]` after sorting. Iterate through all possible windows of size `k`. class Solution: def minimumDifference(self, nums: list[int], k: int) -> int: if k == 1: return 0 nums.sort() min_diff = float('inf') # Iterate through all possible windows of size k for i in range(len(nums) - k + 1): min_diff = min(min_diff, nums[i + k - 1] - nums[i]) return min_diff 20. Minimum Recolors to Get K Consecutive Black Blocks Notes: Sliding window approach. Maintain a window of size `k`. Count 'W's in the current window. Update the count as the window slides by adding the new character and removing the old one. Keep track of the minimum 'W' count. class Solution: def minimumRecolors(self, blocks: str, k: int) -> int: n = len(blocks) min_whites = float('inf') current_whites = 0 # Initialize first window for i in range(k): if blocks[i] == 'W': current_whites += 1 min_whites = current_whites # Slide the window for i in range(k, n): if blocks[i - k] == 'W': # Remove char leaving window current_whites -= 1 if blocks[i] == 'W': # Add char entering window current_whites += 1 min_whites = min(min_whites, current_whites) return min_whites 21. Defuse the Bomb Notes: Handle three cases for `k`: `k > 0` (sum next `k` elements), `k class Solution: def decrypt(self, code: list[int], k: int) -> list[int]: n = len(code) result = [0] * n if k == 0: return result for i in range(n): current_sum = 0 if k > 0: for j in range(1, k + 1): current_sum += code[(i + j) % n] else: # k 22. Make The String Great Notes: Use a stack. Iterate through the string. If the current character forms a "bad pair" with the top of the stack (same letter, different case), pop from the stack. Otherwise, push the character onto the stack. class Solution: def makeGood(self, s: str) -> str: stack = [] for char in s: if stack and stack[-1] != char and stack[-1].lower() == char.lower(): stack.pop() else: stack.append(char) return "".join(stack) 23. Final Prices With a Special Discount in a Shop Notes: For each item, find the first item to its right that is less than or equal to it. If found, apply the discount. A monotonic stack can optimize this, but a simple nested loop works for constraints. class Solution: def finalPrices(self, prices: list[int]) -> list[int]: n = len(prices) result = list(prices) # Copy prices to result for i in range(n): for j in range(i + 1, n): if prices[j] 24. Implement Queue using Stacks Notes: Use two stacks: `in_stack` for pushing elements and `out_stack` for popping. When `out_stack` is empty, transfer all elements from `in_stack` to `out_stack` (reversing order) before popping. This amortizes to $O(1)$ per operation. class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def push(self, x: int) -> None: self.in_stack.append(x) def pop(self) -> int: self._transfer_if_empty() return self.out_stack.pop() def peek(self) -> int: self._transfer_if_empty() return self.out_stack[-1] def empty(self) -> bool: return not self.in_stack and not self.out_stack def _transfer_if_empty(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) 25. Implement Stack using Queues Notes: Use a single queue. For `push(x)`, add `x` to the queue. Then, rotate the queue: dequeue all elements except `x` and enqueue them back. This places `x` at the front, mimicking stack behavior. `pop` and `top` are then simple queue operations. from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x: int) -> None: self.q.append(x) # Rotate the queue to bring the new element to the front for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft() def top(self) -> int: return self.q[0] def empty(self) -> bool: return len(self.q) == 0 26. Baseball Game Notes: Use a stack to keep track of valid scores. Process each operation: integer adds to stack, 'C' pops, 'D' doubles last score and adds, '+' sums last two scores and adds. class Solution: def calPoints(self, operations: list[str]) -> int: records = [] for op in operations: if op.isdigit() or (op[0] == '-' and op[1:].isdigit()): records.append(int(op)) elif op == '+': records.append(records[-1] + records[-2]) elif op == 'D': records.append(records[-1] * 2) elif op == 'C': records.pop() return sum(records) 27. Crawler Log Folder Notes: Treat the folder depth as a counter. "../" decrements (but not below 0), "./" does nothing, and "x/" increments. class Solution: def minOperations(self, logs: list[str]) -> int: depth = 0 for log in logs: if log == "../": depth = max(0, depth - 1) elif log == "./": continue else: # "x/" depth += 1 return depth 28. Clear Digits Notes: Use a stack-like approach. Iterate through the string. If a digit is found, pop the last character from the result stack. Otherwise, append the character. class Solution: def clearDigits(self, s: str) -> str: result = [] for char in s: if char.isdigit(): if result: result.pop() # Remove the last character else: result.append(char) return "".join(result) 29. Minimum String Length After Removing Substrings Notes: Use a stack. Iterate through the string. If the current character with the stack top forms "AB" or "CD", pop the stack. Otherwise, push the character. The final stack length is the minimum length. class Solution: def minLength(self, s: str) -> int: stack = [] for char in s: if stack and ((stack[-1] == 'A' and char == 'B') or \ (stack[-1] == 'C' and char == 'D')): stack.pop() else: stack.append(char) return len(stack) 30. Sqrt(x) Notes: Binary search. Search for an integer `ans` such that `ans * ans x`. The search space is `[0, x]`. Use `mid * mid` carefully to avoid overflow, or `mid class Solution: def mySqrt(self, x: int) -> int: if x == 0: return 0 left, right = 1, x ans = 0 while left 31. Valid Perfect Square Notes: Similar to Sqrt(x), use binary search. Find if there exists an integer `mid` such that `mid * mid == num`. The search space is `[1, num]`. Again, use `mid class Solution: def isPerfectSquare(self, num: int) -> bool: if num 32. Arranging Coins Notes: The problem asks for the maximum `k` such that $1 + 2 + \dots + k \le n$. This sum is $k(k+1)/2$. We need to find the largest `k` satisfying $k(k+1)/2 \le n$. This can be solved with binary search for `k` in the range `[1, n]` or by solving the quadratic equation for `k` ($k^2 + k - 2n \le 0$). class Solution: def arrangeCoins(self, n: int) -> int: # Using binary search left, right = 1, n ans = 0 while left k^2 + k - 2n 33. Guess Number Higher or Lower Notes: Classic binary search problem. The `guess(num)` API tells you if `num` is too high (-1), too low (1), or correct (0). Adjust search range `[left, right]` based on the API's return value. # The guess API is already defined for you. # @param num, your guess # @return -1 if num is higher than the picked number # 1 if num is lower than the picked number # otherwise return 0 # def guess(num: int) -> int: class Solution: def guessNumber(self, n: int) -> int: left, right = 1, n while left 34. Binary Search Notes: Standard binary search algorithm to find a target in a sorted array. Adjust `left` and `right` pointers based on comparison with the middle element. class Solution: def search(self, nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 while left 35. Remove Duplicates from Sorted List Notes: Iterate through the linked list. If `current.val == current.next.val`, skip `current.next` by setting `current.next = current.next.next`. Otherwise, move `current` to `current.next`. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: current = head while current and current.next: if current.val == current.next.val: current.next = current.next.next # Skip the duplicate else: current = current.next # Move to the next unique node return head 36. Remove Linked List Elements Notes: Use a dummy node to simplify edge cases (removing head). Iterate through the list with a `current` pointer. If `current.next.val == val`, remove `current.next` by setting `current.next = current.next.next`. Otherwise, move `current` forward. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy = ListNode(0) dummy.next = head current = dummy while current.next: if current.next.val == val: current.next = current.next.next # Remove the node else: current = current.next # Move current pointer return dummy.next 37. Linked List Cycle Notes: Floyd's Cycle-Finding Algorithm (Tortoise and Hare). Use two pointers, one moves one step at a time (slow), the other two steps (fast). If they meet, there's a cycle. If `fast` or `fast.next` becomes `None`, no cycle. # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if not head or not head.next: return False slow = head fast = head.next while fast and fast.next: if slow == fast: return True slow = slow.next fast = fast.next.next return False 38. Evaluate Boolean Binary Tree Notes: Recursive solution. Base cases are leaf nodes (0 or 1). For internal nodes, recursively evaluate left and right children and apply the boolean operation (OR for 2, AND for 3). # 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 evaluateTree(self, root: Optional[TreeNode]) -> bool: if root.val == 0: # Leaf node False return False if root.val == 1: # Leaf node True return True left_eval = self.evaluateTree(root.left) right_eval = self.evaluateTree(root.right) if root.val == 2: # OR operation return left_eval or right_eval else: # root.val == 3, AND operation return left_eval and right_eval 39. Leaf-Similar Trees Notes: Traverse both trees (e.g., DFS) to collect their leaf values in order. Then compare the two lists of leaf values. # 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: def get_leaf_values(node: TreeNode) -> list[int]: leaves = [] if not node: return leaves if not node.left and not node.right: # Is a leaf node leaves.append(node.val) else: leaves.extend(get_leaf_values(node.left)) leaves.extend(get_leaf_values(node.right)) return leaves leaves1 = get_leaf_values(root1) leaves2 = get_leaf_values(root2) return leaves1 == leaves2 40. Range Sum of BST Notes: Recursive DFS. If a node's value is within the range `[low, high]`, add it to the sum. If `node.val > low`, recurse on the left child. If `node.val # 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 rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int: if not root: return 0 current_sum = 0 if low low: # Potentially find values in left subtree current_sum += self.rangeSumBST(root.left, low, high) if root.val 41. Path Sum Notes: Recursive DFS. Subtract `node.val` from `targetSum` as you go down. A path sum exists if you reach a leaf node and the remaining `targetSum` is 0. Base case: if `not node`, return `False`. # 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False # Check if it's a leaf node and targetSum is met if not root.left and not root.right: return targetSum == root.val # Recurse on children, subtracting current node's value remaining_sum = targetSum - root.val return self.hasPathSum(root.left, remaining_sum) or \ self.hasPathSum(root.right, remaining_sum) 42. Merge Two Binary Trees Notes: Recursive solution. If both nodes exist, create a new node with sum of values and recursively merge their children. If only one node exists, return that node. If neither, return `None`. # 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]: if not root1 and not root2: return None if not root1: return root2 if not root2: return root1 # Both roots exist, create a new node with sum merged_node = TreeNode(root1.val + root2.val) merged_node.left = self.mergeTrees(root1.left, root2.left) merged_node.right = self.mergeTrees(root1.right, root2.right) return merged_node 43. Subtree of Another Tree Notes: Two helper functions: `isSameTree` to check if two trees are identical, and main `isSubtree` to traverse `root` and call `isSameTree` at each node. DFS traversal for `root`. # 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not root: return False if self.isSameTree(root, subRoot): return True return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True if not p or not q or p.val != q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) 44. Balanced Binary Tree Notes: Recursive DFS. A tree is balanced if for every node, the heights of its two subtrees differ by at most 1, AND its left subtree is balanced, AND its right subtree is balanced. A helper function can return height or $-1$ if unbalanced. # 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 isBalanced(self, root: Optional[TreeNode]) -> bool: def check_height(node: Optional[TreeNode]) -> int: if not node: return 0 left_height = check_height(node.left) if left_height == -1: # Left subtree is unbalanced return -1 right_height = check_height(node.right) if right_height == -1: # Right subtree is unbalanced return -1 if abs(left_height - right_height) > 1: # Current node is unbalanced return -1 return 1 + max(left_height, right_height) # Return height of current node return check_height(root) != -1 45. Maximum Depth of Binary Tree Notes: Recursive DFS. The maximum depth of a node is $1 + \max(\text{depth of left child}, \text{depth of right child})$. Base case: depth of `None` is 0. # 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 maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return 1 + max(left_depth, right_depth) 46. N-ary Tree Postorder Traversal Notes: Recursive or iterative solution. Postorder means traversing children first, then the node itself. For N-ary tree, traverse all children from left to right, then visit the node. # Definition for a Node. # class Node: # def __init__(self, val=None, children=None): # self.val = val # self.children = children class Solution: def postorder(self, root: 'Node') -> list[int]: result = [] if not root: return result # Recursive approach # for child in root.children: # result.extend(self.postorder(child)) # result.append(root.val) # return result # Iterative approach using two stacks (or reversing a pre-order traversal) stack = [root] output = [] while stack: node = stack.pop() output.append(node.val) if node.children: for child in node.children: stack.append(child) return output[::-1] # Reverse the result to get postorder