Prefix sum problems: Longest subarray with sum k

Problem Statement:

You are given an array, and a value K, find the length of the longest subarray.

Example:

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

Output: 1

Solution 1: Bruteforce approach

We will calculate the sum of all sub arrays and return the length of the longest sub array having sum k.

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

Solution 2: Prefix sum approach

We will map with prefix sum approach.

The hash map will take sum as key and index as values.

Then starting from the first index, if the total is k, then set the maxLen to i+1.

Check if sum-k is present in hash table, if present update the maxLen.

Insert current sum into the map.

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

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;


int solution_2(vector <int> arr, int k) 
{
    unordered_map<int, int> mp;

    int maxLen = 0;
    int prefSum = 0;

    for (int i = 0; i < arr.size(); ++i) 
    {
        prefSum += arr[i];

        if (prefSum == k) 
            maxLen = i + 1;

        else if (mp.find(prefSum - k) != mp.end()) 
            maxLen = max(maxLen, i - mp[prefSum - k]);

      	if (mp.find(prefSum) == mp.end())
            mp[prefSum] = i;
    }

    return maxLen;
}


int solution_1(vector <int> arr, int K) 
{
  int n = arr.size();
  int count = 0;

  for (int i = 0; i < n; i++) 
  {
    for (int j = i; j < n; j++) 
    {
      int sum = 0;
      for (int k = i; k <= j; k++) 
      {
        sum += arr[k];
      }
      count += (sum == K);
    }
  }
  return count;
}


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

    return 0;
}

Output

1
1