हिन्दी flagहिन्दी  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

You are given an array of integers nums and an integer k. Your task is to find the length of the longest subarray that has a sum equal to k. If no such subarray exists, return 0.

Examples

Example 1:

Input: nums = [1, -1, 5, -2, 3], K = 3
Output: 4

Explanation:
The subarray [1, -1, 5, -2] has a sum of 3, which is the longest subarray with sum 3.
Example 2:

Input: nums = [-2, -1, 2, 1], K = 1
Output: 2

Explanation:
The subarray [-1, 2] has a sum of 1, which is the longest subarray with sum 1.

Different Approaches

1️⃣ Brute Force Approach

Algorithm:

  1. Initialize maxLen to 0.
  2. Iterate through all subarrays of the given array and calculate their sum.
  3. If the sum is equal to k, update maxLen with the length of the current subarray.
  4. Return maxLen.

Dry Run:

Initialization:
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
 k = 15
Iterate through the array:

i = 0

       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^
          |
          i
k = 15
 
For j = i = 0
sum = 0
maxLength = 0
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^
          |
          i
          j
     sum += nums[j]
          = 10
     Does it is equal to k
     No sum is 10 while k is 15
     Increment j

For j = 1
sum = 10
maxLength = 0
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^     ^
          |     |
          i     j
          
     sum += nums[j]
          = 10 + 5
     Does it is equal to k
     Yes sum is 15 while k is 15
          Get its length, j - i + 1
                  length = 1 - 0 + 1
                         = 2
          Assign max of maxLength and length to maxLength
          maxLength = max(maxLength, length)
                    = max(0, 2)
                    = 2

For j = 2
sum = 15
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^           ^
          |           |
          i           j
          
     sum += nums[j]
          = 15 + 2
          = 17
     Does it is equal to k
     No, sum is 17 while k is 15
     So, Increment j

For j = 3
sum = 17
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^                 ^
          |                 |
          i                 j
          
     sum += nums[j]
          = 17 + 7
          = 24
     Does it is equal to k
     No, sum is 24 while k is 15
     So, Increment j

For j = 4
sum = 24
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^                       ^
          |                       |
          i                       j
          
     sum += nums[j]
          = 24 + 1
          = 25
     Does it is equal to k
     No, sum is 25 while k is 15
     So, Increment j
     
For j = 5
sum = 25
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^                             ^
          |                             |
          i                             j
          
     sum += nums[j]
          = 25 + 9
          = 34
     Does it is equal to k
     No, sum is 34 while k is 15
     So, Increment j

For j = 6
sum = 34
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^                                   ^
          |                                   |
          i                                   j
          
     For j = 6 it went out of bounds so inner loop
     will terminate,
     Now run for next value of i by fixing next element.

i = 1:

       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^
                |
                i
k = 15

For j = i = 1
sum = 0
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^
                |
                i
                j
     sum += nums[j]
          = 0 + 5
     Does it is equal to k
     No sum is 5 while k is 15
     Increment j

For j = 2
i = 1
k = 15
sum = 5
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^     ^
                |     |
                i     j
                
     sum += nums[j]
          = 5 + 2
     Does it is equal to k
     No sum is 7 while k is 15
     Increment j
     
For j = 3
i = 1
k = 15
sum = 7
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^           ^
                |           |
                i           j
                
     sum += nums[j]
          = 7 + 7
          = 14
     Does it is equal to k
     No sum is 14 while k is 15
     Increment j

For j = 4
i = 1
k = 15
sum = 14
maxLength = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^                 ^
                |                 |
                i                 j
                
     sum += nums[j]
          = 14 + 1
          = 15
     Does it is equal to k
     Yes, sum is 15 while k is 15
          Get its length, j - i + 1
                  length = 4 - 1 + 1
                         = 4
          Assign max of maxLength and length to maxLength
          maxLength = max(maxLength, length)
                    = max(2, 4)
                    = 4

For j = 5
i = 1
k = 15
sum = 15
maxLength = 4
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^                       ^
                |                       |
                i                       j
                
     sum += nums[j]
          = 15 + 9
          = 24
     Does it is equal to k
     No, sum is 24 while k is 15
     Increment j
     
For j = 6
i = 1
k = 15
sum = 24
maxLength = 4
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^                             ^
                |                             |
                i                             j
                
     The j went out of bounds to array. So, inner
     loop will terminate and i is incremented.
Keep doing it until outer loop i < nums.size
And at last return maxLength.

Code Implementation in C++:


#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int longestSubarray(vector<int> &nums, int k)
    {
        int n = nums.size(); 
        int maxLength = 0;

        // starting index
        for (int startIndex = 0; startIndex < n; startIndex++) { 
            // ending index
            for (int endIndex = startIndex; endIndex < n; endIndex++) { 
                /* add all the elements of 
                   subarray = nums[startIndex...endIndex]  */
                int currentSum = 0;
                for (int i = startIndex; i <= endIndex; i++) {
                    currentSum += nums[i];
                }

                if (currentSum == k)
                    maxLength = max(maxLength, endIndex - startIndex + 1);
            }
        }
        return maxLength;
    }
};

int main()
{
    vector<int> a = { -1, 1, 1 };
    int k = 1;

    // Create an instance of the Solution class
    Solution solution;
    // Function call to get the result
    int len = solution.longestSubarray(a, k);
    
    cout << "The length of the longest subarray is: " << len << "\n";
    return 0;
}

Complexity Analysis:

  • Time Complexity:O(n^2), where n is the number of elements in array.
  • Space Complexity:O(1)

2️⃣ Cumulitive Sum using HashMap

Algorithm:

  1. Initialize a hashmap mp to store the prefix sum and its corresponding index.
    • The key of the hashmap will be the prefix sum.
    • The value of the hashmap will be the index of the first occurrence of the prefix sum.
  2. Initialize maxLen to 0 and sum to 0.
  3. Iterate through the array and calculate the prefix sum.
    1. At each iteration, update the sum by adding the current element.
    2. If sum - k is present in mp, update maxLen with the maximum length so far.
      1. If sum - k is present in the hashmap, it means there exists a subarray with the required sum.
      2. Update maxLen with the maximum length of the subarray.
    3. If sum is not present in mp, add it to mp.
      1. If the current prefix sum is not present in the hashmap, add it to the hashmap along with its index.
  4. Return maxLen.

Dry Run:

Initialization:
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
 k = 15
 maxlen = 0
 currentSum = 0
 
 unordered_map(prefixSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
Iterate over the array:
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^
          |
          i
 k = 15
 maxlen = 0
 currentSum = 0
 
 unordered_map(prefixSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 
Iteration 1: i = 0
     currentSum += nums[i]
     currentSum = 0 + 10
                = 10
     Check if currentSum is equal to k
         No it does not.
     Else if
         Check if currentSum - target(k) exist in
         the map
              = 10 - 15
              = -5
         No it does not exist in the map
     
     Check if currentSum 10, does not exist in map
     Yes it does not exist
         So add the currentSum as key and index as
         value in the map
         currentSum = 10, index = 0
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^
                |
                i
 k = 15
 maxlen = 0
 currentSum = 10
 
 unordered_map(prefixSum || currentSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 | 10  |  0  |
 +-----+-----+
 
Iteration 2: i = 1
     currentSum += nums[i]
     currentSum = 10 + 5
                = 15
     Check if currentSum is equal to k
         Yes it is equal, 15 == 15
         set maxlen = i + 1
                    = 1 + 1
                    = 2
     
     Check if currentSum 15, does not exist in map
     Yes it does not exist
         So add the currentSum as key and index as
         value in the map
         currentSum = 15, index = 1
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                      ^
                      |
                      i
 k = 15
 maxlen = 2
 currentSum = 15
 
 unordered_map(prefixSum || currentSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 | 10  |  0  |
 +-----+-----+
 | 15  |  1  |
 +-----+-----+
 
Iteration 3: i = 2
     currentSum += nums[i]
     currentSum = 15 + 2
                = 17
     Check if currentSum is equal to k
         No, it is not
     Else if
         Check currentSum - target(k) exist in
         the map
              = 17 - 15
              = 2
         No it does not exist in the map
     
     Check if currentSum 17, does not exist in map
     Yes it does not exist
         So add the currentSum as key and index as
         value in the map
         currentSum = 17, index = 2
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                            ^
                            |
                            i
 k = 15
 maxlen = 2
 currentSum = 17
 
 unordered_map(prefixSum || currentSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 | 10  |  0  |
 +-----+-----+
 | 15  |  1  |
 +-----+-----+
 | 17  |  2  |
 +-----+-----+
 
Iteration 4: i = 3
     currentSum += nums[i]
     currentSum = 17 + 7
                = 24
     Check if currentSum is equal to k
         24 != 15
         No, it is not
     Else if
         Check currentSum - target(k) exist in
         the map
              = 24 - 15
              = 9
         No it does not exist in the map
     
     Check if currentSum 24, does not exist in map
     Yes it does not exist
         So add the currentSum as key and index as
         value in the map
         currentSum = 24, index = 3
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                  ^
                                  |
                                  i
 k = 15
 maxlen = 2
 currentSum = 24
 
 unordered_map(prefixSum || currentSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 | 10  |  0  |
 +-----+-----+
 | 15  |  1  |
 +-----+-----+
 | 17  |  2  |
 +-----+-----+
 | 24  |  3  |
 +-----+-----+
 
Iteration 5: i = 4
     currentSum += nums[i]
     currentSum = 24 + 1
                = 25
     Check if currentSum is equal to k
         25 != 15
         No, it is not
     Else if
         Check currentSum - target(k) exist in
         the map
              = 25 - 15
              = 10
         Yes, it does exist in the map
             Set maxLen = max(maxLen, i - map[currentSum - k])
             maxLen = max(2, 4 - 0)
             maxLen = 4
     
     Check if currentSum 25, does not exist in map
     Yes it does not exist
         So add the currentSum as key and index as
         value in the map
         currentSum = 25, index = 4
       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                        ^
                                        |
                                        i
 k = 15
 maxlen = 4
 currentSum = 25
 
 unordered_map(prefixSum || currentSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 | 10  |  0  |
 +-----+-----+
 | 15  |  1  |
 +-----+-----+
 | 17  |  2  |
 +-----+-----+
 | 24  |  3  |
 +-----+-----+
 | 25  |  4  |
 +-----+-----+
 
Iteration 5: i = 4
     currentSum += nums[i]
     currentSum = 25 + 9
                = 34
     Check if currentSum is equal to k
         34 != 15
         No, it is not
     Else if
         Check currentSum - target(k) exist in
         the map
              = 34 - 15
              = 9
         No, it does not exist in the map
     
     Check if currentSum 34, does not exist in map
     Yes it does not exist
         So add the currentSum as key and index as
         value in the map
         currentSum = 34, index = 5
Loop Termination:

       +-----+-----+-----+-----+-----+-----+
nums = | 10  |  5  |  2  |  7  |  1  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                              ^
                                              |
                                              i
 k = 15
 maxlen = 4
 currentSum = 34
 
 unordered_map(prefixSum || currentSum, index)
 +-----+-----+
 | key |value|
 +-----+-----+
 | 10  |  0  |
 +-----+-----+
 | 15  |  1  |
 +-----+-----+
 | 17  |  2  |
 +-----+-----+
 | 24  |  3  |
 +-----+-----+
 | 25  |  4  |
 +-----+-----+
 | 34  |  5  |
 +-----+-----+
 
Since i has exceeded the bounds of the array so, loop
will terminate and maxlen contains the answer.

Code Implementation in C++:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int longestSubarrayWithSumK(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    int maxLen = 0;
    int sum = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        
        if (sum == k) {
            maxLen = i + 1;
        }
        else if (mp.find(sum - k) != mp.end()) {
            maxLen = max(maxLen, i - mp[sum - k]);
        }
        
        if (mp.find(sum) == mp.end()) {
            mp[sum] = i;
        }
    }
    
    return maxLen;
}

int main() {
    vector<int> nums1 = {1, -1, 5, -2, 3};
    int k1 = 3;
    cout << "Length of the longest subarray with sum " << k1 << ": " << longestSubarrayWithSumK(nums1, k1) << endl;
    
    vector<int> nums2 = {-2, -1, 2, 1};
    int k2 = 1;
    cout << "Length of the longest subarray with sum " << k2 << ": " << longestSubarrayWithSumK(nums2, k2) << endl;
    
    return 0;
}

Complexity Analysis:

  • Time Complexity:O(n)
  • Space Complexity:O(n)
Your experience on this site will be improved by allowing cookies Cookie Policy