Smallest Subarray with Sum K from an Array
Given an array arr[] consisting of N integers, the task is to find the length of the Smallest subarray with a sum equal to K.
Examples:
Input: arr[] = {2, 4, 6, 10, 2, 1}, K = 12
Output: 2
Explanation: All possible subarrays with sum 12 are {2, 4, 6} and {10, 2}.Input: arr[] = {-8, -8, -3, 8}, K = 5
Output: 2
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays and for each subarray, check if its sum is equal to K or not. Print the minimum length of all such subarrays.
C++
// c++ code to implement the above idea #include <bits/stdc++.h> using namespace std; // Function to find the Smallest Subarray with // Sum K from an Array int smallestSubarraySumK(vector< int >& arr, int k) { int result = INT_MAX; for ( int i = 0; i < arr.size(); ++i) { int sum = 0; for ( int j = i; j < arr.size(); j++) { sum += arr[j]; if (sum == k) { result = min(result, (j - i + 1)); } } } // Return result return result; } // Driver code int main() { vector< int > arr = { -8, -8, -3, 8 }; int k = 5; int result = smallestSubarraySumK(arr, k); if (result == INT_MAX) cout << -1; else cout << result; return 0; } |
Java
/*package whatever //do not write package name here */ import java.util.*; class GFG { // Function to find the Smallest Subarray with // Sum K from an Array static int smallestSubarraySumK( int [] arr, int k) { int result = Integer.MAX_VALUE; for ( int i = 0 ; i < arr.length; ++i) { int sum = 0 ; for ( int j = i; j < arr.length; j++) { sum += arr[j]; if (sum == k) { result = Math.min(result, (j - i + 1 )); } } } // Return result return result; } public static void main (String[] args) { int [] arr = { - 8 , - 8 , - 3 , 8 }; int k = 5 ; int result = smallestSubarraySumK(arr, k); if (result == Integer.MAX_VALUE) System.out.println(- 1 ); else System.out.println(result); } } // This code is contributed by aadityaburujwale. |
Python3
# python code to implement the above idea import math # Function to find the Smallest Subarray with # Sum K from an Array def smallestSubarraySumK(arr, k): result = 2147483647 ; for i in range ( 0 , len (arr)): ans = 0 ; for j in range (i, len (arr)): ans + = arr[j]; if (ans = = k): result = min (result, (j - i + 1 )); # Return result return result; # Driver code arr = [ - 8 , - 8 , - 3 , 8 ]; k = 5 ; result = smallestSubarraySumK(arr, k); if (result = = 2147483647 ): print ( - 1 ); else : print (result); # This code is contributed by ritaagarwal. |
C#
// Method for checking if we can // make adjacents different or not // c# code to implement the above idea using System; using System.Collections.Generic; class GFG { // Function to find the Smallest Subarray with // Sum K from an Array static int smallestSubarraySumK(List< int > arr, int k) { int result = Int32.MaxValue; for ( int i = 0; i < arr.Count; ++i) { int sum = 0; for ( int j = i; j < arr.Count; j++) { sum += arr[j]; if (sum == k) { result = Math.Min(result, (j - i + 1)); } } } // Return result return result; } // Driver code public static void Main() { List< int > arr = new List< int >{ -8, -8, -3, 8 }; int k = 5; int result = smallestSubarraySumK(arr, k); if (result == Int32.MaxValue) Console.Write(-1); else Console.Write(result); } } // This code is contributed by poojaagarwal2. |
Javascript
// Javascript code to implement the above idea // Function to find the Smallest Subarray with // Sum K from an Array function smallestSubarraySumK(arr, k) { let result = Number.MAX_SAFE_INTEGER; for (let i = 0; i < arr.length; ++i) { let sum = 0; for (let j = i; j < arr.length; j++) { sum += arr[j]; if (sum == k) { result = Math.min(result, (j - i + 1)); } } } // Return result return result; } // Driver code let arr = [ -8, -8, -3, 8 ]; let k = 5; let result = smallestSubarraySumK(arr, k); if (result == Number.MAX_SAFE_INTEGER) document.write(-1); else document.write(result); |
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient approach: The above approach can be further optimized using the Prefix Sum technique and Map.
Follow the steps below to solve the problem:
- currPrefixSum will store the prefix sum ending at ith index.
- Iterate over the array and keep calculating currPrefixSum.
- Check if, currPrefixSum is equal to K.
- If yes, then use this length of subarray (currPrefixSum) to minimize the result.
- Also, check if the required prefix sum (currPrefixSum – K) has been calculated previously or not.
- If the required prefix sum is calculated previously then find its last occurrence of that prefix sum and use it to calculate the length of the current prefix sum equal to K by (current index – last occurrence of required prefix sum) and use it to minimize the result.
- Store the currPrefixSum which is ending at ith index into the map.
- Check if, currPrefixSum is equal to K.
- Finally, return the result.
Below is the implementation of the above approach:
C++
// c++ code to implement the above idea #include <bits/stdc++.h> using namespace std; // Function to find the Smallest Subarray with // Sum K from an Array int smallestSubarraySumK(vector< int > & arr, int k ){ // Use map here to store the prefixSum ending // at ith index. unordered_map< long long , int > unmap; int n = arr.size(); // Store the current Prefix sum till ith index; long long currPrefixSum = 0; // Store the minimum size subarray whose sum is K long long result = INT_MAX; for ( int i = 0; i < n; i++){ currPrefixSum += arr[i]; // Check if the current prefix sum is equals to K if (currPrefixSum == k){ long long currLen = i + 1; result = min(result, currLen); } // Required PrefixSum long long requirePrefixSum = currPrefixSum - k; // Check if there exist any required // Prefix Sum or not if (unmap.count(requirePrefixSum)){ long long foundIdx = unmap[requirePrefixSum]; long long currIdx = i; result = min(result, currIdx - foundIdx); } // Store the current prefix sum ending // at i unmap[currPrefixSum] = i; } if (result >= INT_MAX) return -1; // return the result return result; } // Driver code int main(){ vector< int > arr = {-8, -8, -3, 8}; int k = 5; cout << smallestSubarraySumK(arr, k); return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; public class Main { // Function to find the Smallest Subarray with Sum // K from an Array static int smallestSubarraySumK( int arr[], int n, int K) { // Use map here to store the prefixSum ending // at ith index. HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Store the current Prefix sum till ith // index; int currPrefixSum = 0 ; // Store the minimum size subarray whose // sum is K int result = Integer.MAX_VALUE; for ( int i = 0 ; i < n; i++){ currPrefixSum += arr[i]; // Check if the current prefix sum is // equals to K if (currPrefixSum == K){ int currLen = i + 1 ; result = Math.min(result, currLen); } // Required PrefixSum int requirePrefixSum = currPrefixSum - K; // Check if there exist any required Prefix Sum or not if (mp.containsKey(requirePrefixSum)){ int foundIdx = mp.get(requirePrefixSum); int currIdx = i; result = Math.min(result, currIdx - foundIdx); } // Store the current prefix sum ending at i mp.put(currPrefixSum, i); } if (result >= Integer.MAX_VALUE) return - 1 ; // return the result return result; } // Driver Code public static void main(String[] args){ int arr[] = {- 8 , - 8 , - 3 , 8 }; int n = arr.length; int K = 5 ; System.out.println(smallestSubarraySumK(arr, n, K)); } } |
Python3
# Python3 program to implement # the above approach from collections import defaultdict import sys # Function to find the length of the # smallest subarray with sum K def subArraylen(arr, n, K): mp = defaultdict( lambda : 0 ) currPrefixSum = 0 result = sys.maxsize for i in range (n): currPrefixSum + = arr[i] if (currPrefixSum = = K): currLen = i + 1 result = min (result, currLen) requirePrefixSum = currPrefixSum - K if (requirePrefixSum in mp.keys()): foundIdx = mp[requirePrefixSum] currIdx = i result = min (result, currIdx - foundIdx) mp[currPrefixSum] = i return result # Driver Code if __name__ = = "__main__" : arr = [ - 8 , - 8 , - 3 , 8 ] n = len (arr) K = 5 ln = subArraylen(arr, n, K) # Function call if (ln = = sys.maxsize): print ( "-1" ) else : print (ln) # This code is contributed by Shivam Singh |
C#
// C# Program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to find the Smallest Subarray with Sum // K from an Array static int smallestSubarraySumK( int [] arr, int n, int K) { // Use map here to store the prefixSum ending // at ith index. Dictionary< int , int > mp = new Dictionary< int , int >(); // Store the current Prefix sum till ith // index; int currPrefixSum = 0; // Store the minimum size subarray whose // sum is K int result = int .MaxValue; for ( int i = 0; i < n; i++) { currPrefixSum += arr[i]; // Check if the current prefix sum is // equals to K if (currPrefixSum == K) { int currLen = i + 1; result = Math.Min(result, currLen); } // Required PrefixSum int requirePrefixSum = currPrefixSum - K; // Check if there exist any required Prefix Sum or not if (mp.ContainsKey(requirePrefixSum)) { int foundIdx = mp[requirePrefixSum]; int currIdx = i; result = Math.Min(result, currIdx - foundIdx); } // Store the current prefix sum ending at i mp[currPrefixSum] = i; } if (result >= int .MaxValue) return -1; // return the result return result; } // Driver Code public static void Main() { int [] arr = { -8, -8, -3, 8 }; int n = arr.Length; int K = 5; Console.Write(smallestSubarraySumK(arr, n, K)); } } // This code is contributed by saurabh_jaiswal. |
Javascript
<script> // JavaScript code to implement the above idea // Function to find the Smallest Subarray with // Sum K from an Array function smallestSubarraySumK(arr,k) { // Use map here to store the prefixSum ending // at ith index. let unmap = new Map(); let n = arr.length // Store the current Prefix sum till ith index; let currPrefixSum = 0; // Store the minimum size subarray whose sum is K let result = Number.MAX_VALUE; for (let i = 0; i < n; i++) { currPrefixSum += arr[i]; // Check if the current prefix sum is equals to K if (currPrefixSum == k){ let currLen = i + 1; result = Math.min(result, currLen); } // Required PrefixSum let requirePrefixSum = currPrefixSum - k; // Check if there exist any required // Prefix Sum or not if (unmap.has(requirePrefixSum)){ let foundIdx = unmap.get(requirePrefixSum); let currIdx = i; result = Math.min(result, currIdx - foundIdx); } // Store the current prefix sum ending // at i unmap.set(currPrefixSum, i); } if (result >= Number.MAX_VALUE) return -1; // return the result return result; } // Driver code let arr = [-8, -8, -3, 8]; let k = 5; document.write(smallestSubarraySumK(arr, k)); // This code is contributed by shinjanpatra </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)