Find Maximum of Sliding Window

Data Structures and Algorithms

Statement

Given an integer list s find the maximum of each contiguous sublist of size k.

Constraints

• 1 ≤ s.length() ≤ 10³
• -10⁴ ≤ s[i] ≤ 10⁴
• 1 ≤ k

Solution

"""
production algorithm
"""

from collections import deque


class Solution:
    def find_maximum(self, numbers, size):
        """
        time complexity O(n)
        space complexity O(k)
        """
        window = deque()
        result = list()

        # build window
        for index in range(size):
            self.cleanup(numbers, index, window)
            window.append(index)
        result.append(numbers[window[0]])

        # slide window
        for index in range(size, len(numbers)):
            if window[0] < index - size + 1:
                window.popleft()
            self.cleanup(numbers, index, window)
            window.append(index)
            result.append(numbers[window[0]])

        return result

    def cleanup(self, numbers, index, window):
        """
        time complexity O(k)
        space complexity O(1)
        """
        while window and numbers[window[-1]] < numbers[index]:
            window.pop()

"""
unit tests
"""

from unittest import TestCase
from algorithms.sliding_window.find_maximum.solution import Solution


class SolutionTestCase(TestCase):
    def test_strictly_increasing_numbers(self):
        # Given
        numbers = [51, 53, 55, 57, 59, 61, 63, 65, 67, 69]
        size = 3
        solution = Solution()

        # When
        actual = solution.find_maximum(numbers, size)

        # Then
        expected = [55, 57, 59, 61, 63, 65, 67, 69]
        self.assertEqual(actual, expected)

    def test_strictly_decreasing_numbers(self):
        # Given
        numbers = [69, 67, 65, 63, 61, 59, 57, 55, 53, 51]
        size = 3
        solution = Solution()

        # When
        actual = solution.find_maximum(numbers, size)

        # Then
        expected = [69, 67, 65, 63, 61, 59, 57, 55]
        self.assertEqual(actual, expected)

    def test_constant_numbers(self):
        # Given
        numbers = [51, 51, 51, 51, 51, 51, 51, 51, 51, 51]
        size = 3
        solution = Solution()

        # When
        actual = solution.find_maximum(numbers, size)

        # Then
        expected = [51, 51, 51, 51, 51, 51, 51, 51]
        self.assertEqual(actual, expected)

    def test_worst_case_numbers(self):
        # Given
        numbers = [51, 51, 51, 53, 53, 53, 55, 55, 55, 57]
        size = 3
        solution = Solution()

        # When
        actual = solution.find_maximum(numbers, size)

        # Then
        expected = [51, 53, 53, 53, 55, 55, 55, 57]
        self.assertEqual(actual, expected)

Strategy

Sliding Window.

Explanation

First, build the window. Push indexes of values to the tail of the window. If the value of the last index of the tail is less than the current value, then pop the last index of the tail until its value is greater than the current value. Then push the index of the current value to the tail of the window. Finally, record the maximum value of the window from the index at the head of the window.

Next, slide the window. If the index at head of the window is no longer in the window, then pop the index of the head of the window. If the value of the last index of the tail is less than the current value, then pop the last index of the tail until its value is greater than the current value. Then push the index of the current value to the tail of the window. Finally, record the maximum of the window from the index at the head of the window.

Time Complexity

The time complexity of the algorithm appears to be O(nk) at first glance but consider the four cases of the given integers list: strictly increasing, strictly decreasing, constant, or mixed increasing/decreasing/constant values.

If the integers list is strictly increasing, then the size of the auxiliary window is never greater than one, and cleanup always has time complexity O(1).

If the integers list is strictly decreasing, then the size of the auxiliary window reaches k, but cleanup still always has time complexity O(1).

If the integers list is constant, then the size of the auxiliary window still reaches k, but cleanup still always has time complexity O(1).

Finally, the integers list can be mixed increasing/decreasing/constant values. For example assume the integers list models a staircase function so that the auxiliary window reaches size k before it’s emptied and then filled again. The auxiliary window can be filled and then emptied a maximum of n/k times. To empty a full auxiliary window has time complexity O(k). Together, the time complexity to empty a full auxiliary window the maximum number of times is O(n/k * k) or O(n).

Therefore the time complexity of the algorithm is O(n).

Space Complexity

The auxiliary space complexity of the algorithm is O(k).

Links

data_structures_algorithms/algorithms/sliding_window/find_maximum at main ·…