July 26, 2025 - Daily Drill¶
🎯 Daily Goals¶
- Review Anki Deck
- Lumosity training
- Leetcode
- Developing laplace
- Langchain Learning
📝 What I learned:¶
Leetcode Problem¶
Thinking Process¶
The moment we saw combinations and permutations we can start to think of backtracking. There are mainly two subproblems we need to figure out. The first one is when to prune the state-space tree. The other is how to avoid duplication in the answer. The first question is actually quite easy. As we are doing backtracking, if the current combination is already larger than the target, we should prune it. The second one is a bit more tricky. The duplication would only happen if there are duplicate candidates. For example, candidates = [10,1,2,7,6,1,5], target = 8. The answer [1, 7], [7,1] would be duplicates in the return result. A good way to eliminate duplication is by sorting. Here if we sort the candidates before the backtracking, the returned answer would also be in sort. Now, we can think of when a duplication would happen. Should we avoid all duplicate candidates? Of course not, in the previous example, [1, 1, 6] would be a valid answer. The key is avoid duplication that happens on the same level of the state-space tree. [1, 1, 6] is not a problem since the first 1 has the depth of 1 in state-space tree. While [1, 7] could cause duplication since after we travese through all possible combination that starts with [1, ...] and backtrack, we hit another 1. As a result, we need to check if the next candidate on the same level is equal to the previous candidate.
Implementation¶
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: ret = [] candidates.sort() def backtrack(current, cur_sum, cur_idx): if cur_sum > target: return if cur_sum == target: tuple(current) ret.append(current[:]) return for i in range(cur_idx, len(candidates)): if i > cur_idx and candidates[i] == candidates[i - 1]: continue current.append(candidates[i]) backtrack(current, cur_sum + candidates[i], i + 1) current.pop() return backtrack([], 0, 0) return ret
Complexity Analysis¶
Assume there is n candidates in the array
- Time Complexity: O(2n)
- Space Complexity: O(n)
In the worst case, let's say the target is greater than the sum of all possible combinations. We still need to traverse through all possible ones. For space, we are keep track of the current list to store the possilbe combinations. The worst case it needs O(n) space.
Key Takeaways¶
- Use sorting to avoid duplication
- Think in terms of state-space tree would help you understand the promblem better
- Get familiar with the backtrack pattern.
Thinking Process¶
A maximum product subarray must end with certain index. So if we know the maximum producet subarary ending with each index respectively, we can get the answer. The trickest part of the problem is to deal with negative numbers and zero. Say you got a negative number right now and you know the maximum product of the subarray ending in the previous index. Can you tell the maximum product including the current negative number? Actually no. To get a maximum product of containing the negative, you might want the minimum product of the previous subarray. Here is the pseudo code to do that:
temp_max = max(curr, max(max_so_far * curr, min_so_far * curr))
min_so_far = min(curr, min(max_so_far * curr, min_so_far * curr))
max_so_far = temp_max
This code actually takes care of all possible situation for both positive, negative and 0 all at once.
Complexity Analysis¶
Assume there are n numebrs in the nums array
- Time Complexity: O(n)
- Space Complexity: O(1)