87. Scramble String Idea Reading through the description, take note of these: If the length of the string is 1, stop. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x. The above two pieces of information heavily hint that this is a DP problem. The first sentence tells us the base case, length of string is 1....

110. Balanced Binary Tree This is an easy problem but I did take quite some time to come out with a relatively elegant (at least to my own eyes) solution. Idea We need to check if the given tree is height balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. We need to find out the depth of the two subtrees(left and right), so we have to use a helper function because obviously the given function has only one parameter....

1475. Final Prices With a Special Discount in a Shop Brute Force This is an easy problem, so brute force solution is expected to AC, but I’ll skip it here… Monotonic Stack The problem states that we need to find the next smaller-or-equal element hinting a mono increasing stack. Algorithm loop through prices, since we need next smaller-or-equal element, we append the index to a stack if it is not (so we hav a mono increasing stack) once an element i breaks the increasing property, we found the smaller-or-equal element, we can pop from the stack and minus the price (ref to the implementation for details) return the modified prices as answer Code A typical mono stack structure but with some modification on details....

649 Dota2 Senate Ideas The question description is so long but we can conclude that the best strategy for the current senator is to ban opponent’s team’s next closest senator. Following this, we should be able to work this out by simulation (but it took me 2 hours…). Approach 1 - Simulation (not so good) We use two queues, q and next_q to simulate if q is empty or the first element in it is the same as the current element, put the current senator into q if current element c is different from the first element in q, c should have been banned by the first element (because this is the first different element it sees)....

Simulation(bad idea) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: s=[] p1=0 p2=0 while p2<len(popped): target=popped[p2] while p1<len(pushed) and (len(s)==0 or s[-1]!=target): s.append(pushed[p1]) p1+=1 if not s or s[-1]!=target: return False while p2<len(popped) and (s and s[-1]==popped[p2]): s.pop() p2+=1 return p1==len(pushed) and p2==len(popped) and len(s)==0 This is my first thought, simulate the push and pop and see if we can go through the whole given pushed and popped...

Idea This is today’s daily challenge, I hate subarray problems as sometimes I tend to mess up with the sliding window pointer(especially the left pointer when shirking is needed). However, I learnt one thing from all those stupid subarray problems. Don’t care about the start of the subarray, always count how many subarrays END at current index By sticking to this rule, surprisingly I AC it in one shot… Solution 1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def zeroFilledSubarray(self, nums: List[int]) -> int: l=r=0 res=0 ll=len(nums) while r<ll: if nums[r]==0: res+=r-l+1 else: l=r+1 r+=1 return res

Since we’re allowed to do +value and -value for unlimited number of times and we don’t really have a deterministic way to check the result. So we should consider to start with the solution space(\(10^5\), not so bad). Starting from solution space, this problem turns into: checking if we can find a number in the array that equals to the next number checking if we can find a number which can be processed and become the next number The first one is trivial....

Union Find with a counter that does count-- when there is a successful union, when the count reach 1 (everything is connected) return the timestamp Trick: remember to sort by timestamp

1st approach I don’t like this although this was my original thought keep a visited set and going by the direction (right, down, left, right) and turn if we hit a boundary or hit a visited number. on when to stop: The last puzzle piece is when shall we stop. An interesting observation is that if we reach the visited cell, we need to turn. However, when we meet another visited cell immediately after changing the direction, it means we reached the last element in the matrix....

Oh.. is this too easy to take notes…? My private note is empty for this…