Minimum length subarray with sum equal to k

Updated

Given an array and a integer k. You have to find a minimum length sub array such that sum of this sub array is equal to k. If found return starting and ending index ( 0 starting based ).

Examples :

Input : arr = {2, 2, -4, 3, -2} and k = 1
Output : 3 4
Explanation :
We have 3 sub array whose sum is 1, i.e (0,4) , (1,3) , (3,4)
Out of these sub array (3,4) has minimum length 2.

Input : arr = {0 , 1 , -1} and k = 0
Output : 0 0
Explanation :
We have 3 sub array whose sum is 0, i.e (0,2) , (0,0) , (1,2)
Out of these sub array (0,0) has minimum length 1.

Naive Approach – Iterate with two nested loop and check sum of all possible sub array and find the minimum one. Time Complexity – O(N^2) Efficient Approach – Idea is to use prefix sum of this array. The sum of a sub array is equal to prefix sum till ending index – prefix sum till starting index-1 . Consider this example – arr = {2, 2, -4, 3, -2} and k = 1 . pref_sum = {2, 4, 0, 3, 1}. Let ending index = 3 and starting index be 2. Then sum of sub array between these two index is prefix_sum[3] – prefix_sum[2-1] = 3 – 4 = -1. From above we can conclude this sum of sub array is pref_sum[ending] – pref_sum[starting – 1] . Case if starting index is 0, so pref_sum[-1] = 0. Iterate with one single loop and let this index as ending index of sub array . For this ending index we have to find a starting index such that the sum of this sub array is equal to k. we know that prefix_sum[ending] – prefix_sum[starting-1] = k. We can say that we have to find a index whose prefix_sum is prefix_sum[ending] – k. This index will be starting index – 1.

An array of five numbers above its prefix sums, with the shortest window at indexes 3 and 4 marked and its sum worked out as 1 minus 0.

Implementation :

// C++ program to find the 
// minimum length sub array
// array with the sum = k.
  
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find the minimum 
// length sub array in the array 
// with sum = k. 
void MinLenSubArr(int* a, int n, int k) 
{ 
  
    // Variable to store minimum length
    // Declare with maximum value not possible 
    int min_len = n+1; 
    // Variable to store sub array index
    pair<int,int> index;

    // Variable to store prefix sum
    int pref_sum = 0;

    // map to store the prefix sum as key
    // along with index as value
    map<int,int> prefix_sum_index;

    // Base Case
    prefix_sum_index[0] = -1;
  
    // Loop to iterate through the array 
    for (int i = 0; i < n; ++i) { 

    	// Add current value to prefix sum.
    	pref_sum += a[i];

    	// Let this index to be end 
    	// And we will try to find out 
    	// Starting index for a sub array 
    	// such that sum will be k
    	// Let this index be srt
    	// Thus prefix_sum[end] - prefix_sum[srt-1] = k
    	// prefix_sum[end] = pref_sum
    	// Thus we have to check whether there exist 
    	// a sum (pref_sum - k) in a map or not.

    	if(prefix_sum_index.find(pref_sum - k) !=
    		 prefix_sum_index.end())
    	{
    		// We find a index srt-1 such that 
    		// prefix_sum[end] - prefix_sum[srt-1] = k
    		// Length of this sub array is equal to end - srt + 1
    		// i is end & srt  is prefix_sum_index[pref_sum - k] + 1
            int srt = prefix_sum_index[pref_sum - k] + 1;
            int len = i - srt + 1;

    		if(len < min_len )
            {
                // Update minimum length and index
                min_len = len;
                index = {srt,i};
            }
    	}

    	// Update map 

    	prefix_sum_index[pref_sum] = i;

    } 
    if(min_len == n+1)
    	// We don't find any sub array
    	// whose sum is k
    	cout<< "No sub array with sum k" <<endl;
    else
    	cout<< index.first <<" "<< index.second <<endl;
} 
  
// Driver code 
int main() 
{ 
    int a[] = { 2, 2, -4 , 3 ,-2 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    int k = 1;
  
    MinLenSubArr(a, n, k); 
  
    return 0; 
} 
Comment
Next tutorial
Mithlesh Upadhyay Published 17 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials