1498 Number of Subsequences That Satisfy the Given Sum Condition

1498. Number of Subsequences That Satisfy the Given Sum Condition I hate these array problem and subsequences… This is the daily challenge on 6 May 2023, I opened up the submission tab and found that I tried this problem 1 year ago and from the submission history, I recall how miserable it was… Idea I usually look for two ways to solve array+subsequence problem. DP Two pointers This problem has a test case size of \(10^5\), so DP is out of the game, and two pointer does seem promising....

May 6, 2023 · mimimi

2348 Number of Zero Filled Subarrays

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

March 21, 2023 · mimimi

6321 Smallest Missing Non Negative Integer After Operations

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

March 19, 2023 · mimimi

54 Spiral Matrix

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

March 18, 2023 · mimimi