Skip to main content

Sliding Window

  • problems that involve defining a window or range in the input data (arrays or strings) and then moving that window across the data to perform some operation within the window
  • The window can be of fixed or variable length
  • depending on the use case there are multiple ways to create window -> deque; with one variable for sum etc.

Max sum of k consecutive elements​

def max_k_sum(arr, k):
    left = 0  # start of window
    for i in range(k):
        left += arr[i]
    res = left
    for i in range(k, len(arr)):
        # adjusting the window
        left = left + arr[i] - arr[i - k]
        res = max(res, left)
    return res

Subarray with given sum​

def sub_array_with_given_sum(arr, x):
    s, curr = 0, 0  # start index, current sum
    for e in range(len(arr)):
        curr += arr[e]
        # decreasing window from start
        while curr > x:
            curr -= arr[s]
            s += 1
        if curr == x:
            return True
    return False