Problem statement

https://binarysearch.com/problems/Making-Pairwise-Adjacent-Sums-Small/

Solution

The idea is to start from the left and use greedy strategy. First of all, for pair [0, 1] we have choice: decrease 0 or 1 and it is always better to decrease 1. Then on the next step for pair [1, 2] if it is already <= k we do nothing, if it is > k, then we decrease 2-th element and so on.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, nums, k):
        ans, M = 0, 10 ** 9 + 7
        for i in range(1, len(nums)):
            steps = nums[i] + nums[i - 1] - k
            if steps > 0:
                ans += steps
                nums[i] = max(0, nums[i] - steps)
        return ans % M