Two Pointers: Given an array and a value K, you need to return the size of minimum subarray that is equal to k

Problem Statement:

Given an array and a value K, you need to return the size of minimum subarray that is equal to k

Example:

Input: arr = [1, 2, 3, 4] k = 3

Output: 1

subarray[1, 2] and [3] matches the k value, but [3] matches the given condition.

Solution Explanation:

We will solve the problem by using sliding window with two pointer approach.

Take two pointers left and right and a variable sum.

Move the right pointer forward and add arr[right] to sum.

IF the sum is greater than equal to k,

then update the min_len to the current window size.

Shrink the window from left by subtracting nums[left] from sum and incrementing left.

continue the process and return the result.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <climits>

using namespace std;


int solution(vector<int>& nums, int k) 
{
    int left = 0, right = 0;
    int sum = 0;

    int ans = INT_MAX;

    while (right < nums.size()) 
    {
        sum += nums[right];
        while (sum >= k) 
        {
            
            ans = min(ans, right - left + 1);
            sum -= nums[left];

            left++;
        }
        right++;
    }

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

int main()
{
    vector<int> arr = {1, 2, 3, 4};
    int k = 3;

    cout << solution(arr, k);

    return 0;
}

Output

1