Problem statement

https://binarysearch.com/problems/Longest-Equivalent-Sublist-After-K-Increments/

Solution 1

First solution is to use monotonic queue with binary search: check(x) is question: how many steps we need to make to make window of size x with equal elements.

Complexity

It is O(n log n) for time and O(n) for space, however in python it is TLE.

Code

class Solution:
    def solve(self, A, k):
        def check(x):
            if x > len(A): return float("inf")
            deq, n, ans, out = deque([0]), len(A), [], float("inf")
            for i in range (n):
                while deq and deq[0] <= i - x: deq.popleft()
                while deq and A[i] >= A[deq[-1]]: deq.pop()
                deq.append(i)
                ans.append(A[deq[0]]) 
            for i in range(n - x + 1):
                out = min(out, ans[i+x-1]*x - acc[i+x] + acc[i])

            return out

        if not A: return 0
        acc = [0] + list(accumulate(A))

        beg, end = 0, len(A) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid) > k:
                end = mid
            else:
                beg = mid
        return beg

Solution 2

There is also smarter solution, which combine the idea of sliding window and monotonic deque! The idea is to keep sliding window, and expand it only if we have number of steps in this window <= k.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        ans = beg = total = 0
        Q = deque()
        for end, a in enumerate(nums):
            total += a
            while Q and nums[Q[-1]] <= a: Q.pop()
            Q.append(end)
            while Q and k < (end - beg + 1) * nums[Q[0]] - total:
                total -= nums[beg]
                if Q and beg == Q[0]: Q.popleft()
                beg += 1

            ans = max(ans, end - beg + 1)
        return ans