Minimum Size Subarray Sum

Data Structures and Algorithms

Statement

Given an array of positive integers numbers, and a positive integer target, find the minimum length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, then return 0.

Constraints

• 1 ≤ target ≤ 10⁴
• 1 ≤ numbers.length() ≤ 10³
• 1 ≤ numbers[i] ≤ 10³

Solution

"""
production algorithm
"""


class Solution:
    def minimum_size_subarray_sum(self, numbers, target):
        """
        time complexity O(n)
        space complexity O(1)
        """
        length, low, high = len(numbers), 0, 0
        current = 0
        result = float("inf")

        # step forward high index
        for high in range(length):
            current += numbers[high]

            # step forward low index
            while target <= current:
                result = min(result, high - low + 1)
                current -= numbers[low]
                low += 1

        if result == float("inf"):
            return 0
        return result

"""
unit tests
"""

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


class SolutionTestCase(TestCase):
    def test_empty_numbers(self):
        # Given
        numbers = []
        target = 20
        solution = Solution()

        # When
        actual = solution.minimum_size_subarray_sum(numbers, target)

        # Then
        expected = 0
        self.assertEqual(actual, expected)

    def test_numbers_less_than_target(self):
        # Given
        numbers = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
        target = 100
        solution = Solution()

        # When
        actual = solution.minimum_size_subarray_sum(numbers, target)

        # Then
        expected = 0
        self.assertEqual(actual, expected)

    def test_numbers_greater_than_target(self):
        # Given
        numbers = [12, 14, 16, 18, 20]
        target = 10
        solution = Solution()

        # When
        actual = solution.minimum_size_subarray_sum(numbers, target)

        # Then
        expected = 1
        self.assertEqual(actual, expected)

    def test_constant_window(self):
        # Given
        numbers = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
        target = 20
        solution = Solution()

        # When
        actual = solution.minimum_size_subarray_sum(numbers, target)

        # Then
        expected = 4
        self.assertEqual(actual, expected)

    def test_dynamic_window(self):
        # Given
        numbers = [5, 5, 5, 5, 10, 10, 3, 7, 2, 8]
        target = 20
        solution = Solution()

        # When
        actual = solution.minimum_size_subarray_sum(numbers, target)

        # Then
        expected = 2
        self.assertEqual(actual, expected)

Strategy

Sliding Window.

Explanation

For each step forward of the high index of the window, add the current integer at the high index to the current sum. Then while the target integer is less than or equal to the current sum, record the minimum length between the low and high indexes seen so far, subtract the integer at the low index from the current sum, and step forward the low index. When the window reaches the end of the array, then the global minimum length of a subarray whose sum is greater than or equal to the target integer has been found.

Time Complexity

At worst the low and high indexes both iterate the length of the array. Therefore the time complexity of the algorithm is O(n).

Space Complexity

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

Links

data_structures_algorithms/algorithms/sliding_window/minimum_size_subarray_sum at main ·…