Smallest Subarray - C++ Solution

1. Introduction

In this post, we explore a common problem in array processing - finding the smallest contiguous subarray whose sum of elements is greater than a given positive integer k. This problem is a classic example of the sliding window technique in algorithm design.

Problem

Given an array of positive integers and a positive integer k, the task is to find the length of the smallest contiguous subarray whose sum is greater than k. If no such subarray exists, return 0.

2. Solution Steps

1. Use a sliding window approach to maintain a running sum of elements.

2. Expand the window from the right until the sum is greater than k.

3. Contract the window from the left to find the smallest possible subarray.

4. Keep track of the minimum length during the process.

5. If the minimum length is not updated, return 0, indicating no valid subarray exists.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

int smallestSubarrayWithSumGreaterK(const vector<int>& nums, int k) {
    int minLength = INT_MAX;
    int sum = 0;
    int start = 0;

    for (int end = 0; end < nums.size(); end++) {
        sum += nums[end];

        while (sum > k) {
            minLength = min(minLength, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }

    return (minLength == INT_MAX) ? 0 : minLength;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
    int k = 20;
    cout << "Smallest Subarray Length: " << smallestSubarrayWithSumGreaterK(nums, k) << endl;
    return 0;
}

Output:

Smallest Subarray Length: 3

Explanation:

The function smallestSubarrayWithSumGreaterK finds the smallest length of a contiguous subarray with a sum greater than k using the sliding window technique. It maintains a running sum and adjusts the window size to ensure the sum is greater than k, simultaneously keeping track of the minimum length. For the input array [1, 2, 3, 4, 5, 6, 7, 8] and k = 20, the smallest subarray with a sum greater than 20 is [6, 7, 8] with a length of 3.