Weekly

https://preview.redd.it/1aex84qo5itg1.png?width=869&format=png&auto=webp&s=22a231a9c24beeafffb86040007b6be45acf0242 There were 1000s of cheaters in this contest which led to 5000+ submissions for this problem. But in actuality this problem is beautiful and interesting I recently analyzed Question 3 (3891) from LeetCode Weekly Contest 496, and it turned out to be a very interesting observation + greedy style problem. The problem statement: You are given an array nums. You can increase any element by 1 in one operation. An index i is called special (peak) if: nums[i] > nums[i-1] and nums[i] > nums[i+1] Goal: 1. Maximize the number of peaks 2. Among all such configurations, minimize total operations # Key Observation First ignore operations and only think about maximum possible peaks. If index i is a peak: nums[i] > nums[i-1] nums[i] > nums[i+1] Then: * i-1 cannot be a peak * i+1 cannot be a peak So peaks cannot be adjacent. Therefore the maximum number of peaks possible in an array of length n is: floor((n-2)/2) because only indices [1 … n-2] can become peaks. # Important Structure To maximize peaks, we must select indices with distance ≥ 2. Example pattern: _ P _ P _ P _ So we always move in +2 jumps when choosing peak positions. # Case 1: n is Odd When n is odd, the structure becomes fixed. Inside the middle (n-2) elements: (n-2)/2 + 1 elements Peaks must occur at: 1, 3, 5, 7 ... There is only one optimal configuration. So the solution is straightforward: For each such index i, calculate operations needed: cost[i] = max(0, max(nums[i-1], nums[i+1]) + 1 - nums[i]) Sum all costs. # Case 2: n is Even Now the interesting part. When n is even, there are multiple valid peak patterns. Because while doing +2 jumps, you may need one +3 jump to stay within bounds. Example idea: P _ P _ P _ _ P _ P _ P So the peak positions are not fixed anymore. We must try multiple valid configurations and choose the one with minimum total operations. # Optimization Trick Instead of recomputing costs repeatedly: 1. Precompute the cost of making each index a peak cost[i] = max(0, max(nums[i-1], nums[i+1]) + 1 - nums[i]) 2. Build suffix cost arrays. This allows efficient calculation when we shift the peak pattern. Using suffix sums lets us evaluate each configuration in O(1) after preprocessing. My video solution link for better explanation - <a href="https://www.youtube.com/watch?v=WFTS9H37vOI&t=18s)