Cheap Trick
1. Swap all element equal to some value/criteria to the end of the array
- Have a pointer to hold the first occurence of the value, if the pointer at any given time points to an element with value different from the target value, we can leave it be cause the element will be swap with itself so nothing happens
- This problem is a perfect example
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
swapPos = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[swapPos], nums[i] = nums[i], nums[swapPos]
swapPos += 1
def removeElement(self, nums: List[int], val: int) -> int:
firstOccurence = 0
for i in range(len(nums)):
if nums[i] != val:
nums[firstOccurence], nums[i] = nums[i], nums[firstOccurence]
firstOccurence+=1
return firstOccurence
- An advance for this is this Sort Colors problem, where we do this twice but in reverse
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
swapPos = 0
for i in range(len(nums)):
if nums[i] == 0:
nums[swapPos], nums[i] = nums[i], nums[swapPos]
swapPos += 1
swapPos = len(nums) - 1
for i in range(len(nums) - 1, -1, -1):
if nums[i] == 2:
nums[swapPos], nums[i] = nums[i], nums[swapPos]
swapPos -= 1
2. Boyer-Moore Voting algorithm
3 Check palindrome using middle out instead of 2 pointer from 2 side in may reduce the overall time complexity
4. When need to count occurence of each element in a string or array and store them in a hashmap => Use collections.Counter
5. If need to store the active set of element for existence checking (e.g in sliding window problems), use a Set instead of hashmap/Couter if dont care about number of appearance**
6. When iterate an array, can check 2 value at the same time with nums[i] and nums[i-1]/nums[i+1] or both**
7. Duplication handling: When work with array where we need some kind of combination but the array contains duplicate value and the result doesn't allow duplicating combination, we can sort the array to eliminate the duplicating call during iteration => During iteration, at each index we only care about all indexes at the right side of the current index, and if the element at the adjacent index is the same we can skip it** ^73797d
8. When working with tree, if there is a need to count the number of possible node, keep in mind that each tree layer has 2x the number of node compare to the previous layer**
9. When working with graph, if asked about number of connected node or sth that does not necessarily require traversal, maybe try counting indegree-outdegree**
10. When working with problem that requires validity of parentheses or stuff like, one trick is to use a stack and try to add opening and when meet a closing we can either pop the top of the stack if the top is an opening or add if otherwise. We can also consider save the index of the parentheses when adding to the stack**
11. Another trick when dealing with validity of parenthesis is to count the number of orphan. We will traverse the string on 2 pass, 1 from left to right to count orphan closing and then from right to left to count orphan opening.**
- Ref: https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/solutions/1646594/left-to-right-and-right-to-left/?orderBy=most_votes
- A side note from this is that we can generalized *parenthesis problems* to always use and keep track of *open count* and *close count*, we then can only add a *close bracket* if the *close count < open count*
https://leetcode.com/problems/generate-parentheses
def generateParenthesis(self, n: int) -> List[str]:
res = []
working = []
def backtrack(openCount, closeCount):
if openCount == closeCount == n:
res.append("".join(working))
return
if openCount < n:
working.append("(")
backtrack(openCount+1, closeCount)
working.pop()
if closeCount < openCount:
working.append(")")
backtrack(openCount, closeCount+1)
working.pop()
backtrack(0, 0)
return res
12. When using sliding window, not always need to use left, right with while loop. We can init the left = 0 and increment the right in a for loop, and inside the for loop we do sth to increase the left
- Permutation: can be thought of number of ways to order some input.
- Example: permutations of ABCD, taken 3 at a time (24 variants): ABC, ACB, BAC, BCA, ...
- Combnation: can be thought as the number of ways of selecting from some input.
- Example: combination of ABCD, taken 3 at a time (4 variants): ABC, ABD, ACD, and BCD.
- Subset: can be thought as a selection of objects form the original set.
- Example: subset of ABCD: 'A', 'B', 'C', 'D,' 'A,B' , 'A,C', 'A,D', 'B,C', 'B,D', 'C,D', 'A,B,C', ...
13. When dealing with string or array, sometimes it is helpful and make life easier by using string/array slicing/concatenating
- For example with [this problem](https://leetcode.com/problems/valid-palindrome-ii/description/) , we can simulate the 'delete character' action by slicing the string and combine it without the specify character
def validPalindrome(s: str) -> bool:
l, r = 0, len(s) - 1
while l <= r:
if s[l] != s[r]:
s1 = s[:l] + s[l + 1 :]
s2 = s[:r] + s[r + 1 :]
return s1 == s1[::-1] or s2 == s2[::-1]
l += 1
r -= 1
return True
14. When asked about subarray sum, one trick to calculate this is to calculate the prefix at each index and to get the sum we can do prefix[i] + nums[i] - prefix[j] ^d4096b
15. When asked about order of letter => use ord(c)
- If asked about shifting letter arcoding to alphabet and some offset:
def shiftCharacter(c, offset):
start = ord('a')
return chr((ord(c) + offset - start) %26 + start)
16. When have to generate a random value, use Python built in ^7ce46a
random.random() # => Return a floating point between (0,1) (inclusive)
random.randint(a,b) # Return an int value between (a, b) (inclusive)
17. When we have to randomly pick a value and the probability is weighted (which is fundamental in probability and statistics, this is called Cumulative Distribute Function - CDF) ^935917
- Example: [1, 3] when we have a 25% chance to pick the first value and 75% to pick the second
- Steps:
- Convert weights into cumulative ranges: [1,3] => [0.25, 1]
- This can be done via prefixSum:
prefix += curVal / totalSum - This ranges mean that the first value cover 25% range from 0-0.25 and the second covers 75% range from 0.25-1.0
- This can be done via prefixSum:
- Use Python to generate a random seed from (0,1) (see tips right above)
- Now we can just simply find the first index where the probability is greater than the seed value
- Seed = 0.55 => it should fall into the range [0.25, 1.0] => Should return the value 3
- We can do this in a few way
- Linear search
- Binary search [[Binary Search#^3c6735 | Example]
- Convert weights into cumulative ranges: [1,3] => [0.25, 1]
18. When deal with problems that require calculation between any 2 pairs of elements.
- Sorting
- [[3. Two Pointer]]
- [[Prefix Sum]]
- [[Greedy]]
If the problem ask about difference between any 2 num => Only need to care about the difference of max value & min value (because it is guaranteed that anything in between will have smaller differences)https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
- This can be solved using [[8. Heap#Two Heaps Pattern]] depends on the complexity
def longestSubarray(self, nums: List[int], limit: int) -> int:
res = 0
left = 0
minHeap = []
maxHeap = []
for right, num in enumerate(nums):
heapq.heappush(minHeap, (num, right))
heapq.heappush(maxHeap, (-num, right))
while -maxHeap[0][0] - minHeap[0][0] > limit:
left += 1
while maxHeap[0][1] < left:
heapq.heappop(maxHeap)
while minHeap[0][1] < left:
heapq.heappop(minHeap)
res = max(res, right - left + 1)
return res
19. Sometimes (rare) where we may need to delete a value in the middle of an array and then we have to update the index of everything that comes after that value (like this problem), and you don't necessarily care about the order, you just want to maintain an array of values with indexing. A trick is that:
- We don't actually have to update element, just the removed and the last one
- So we can swap the removed element to the last, and then remove the last element, which is O(1)
https://leetcode.com/problems/insert-delete-getrandom-o1
class RandomizedSet:
def __init__(self):
self.set = {}
self.nums = []
def insert(self, val: int) -> bool:
if val in self.set:
return False
self.set[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.set:
return False
removedIndex = self.set[val]
lastIndex = len(self.nums) - 1
lastValue = self.nums[-1]
self.nums[removedIndex], self.nums[lastIndex] = self.nums[lastIndex], self.nums[removedIndex]
self.set[lastValue] = removedIndex
self.nums.pop()
del self.set[val]
return True
def getRandom(self) -> int:
seed = random.randint(0, len(self.nums) - 1)
return self.nums[seed]
20. When a problem give you some kind of math constraint that requires a pair, e.g: j-i == nums[j] - nums[i] or something similar, try to modify the equation to move all i, j to the same side to simplify the problem
https://leetcode.com/problems/count-number-of-bad-pairs
- This is also an example of [[2. Problem Solving Strategy#Invert | Invert strategy]]
- Instead of count the bad pairs we count the good pair and subtract it
def countBadPairs(self, nums: List[int]) -> int:
diffCount = collections.defaultdict(int)
count = 0
for i in range(len(nums)):
diff = nums[i] - i
goodCount = diffCount[diff]
count += i - goodCount
diffCount[diff] += 1
return count