# Longest Sub-Array with Sum K

### Problem

<https://practice.geeksforgeeks.org/problems/longest-sub-array-with-sum-k0809/1>

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2F7LUn8hplwhuQOzZi0pBK%2Fimage.png?alt=media&#x26;token=4de50258-3c13-418a-8e4c-fd2c1faaa1d0" alt=""><figcaption></figcaption></figure>

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FYt76uJ2hKgNKekSDBuov%2Fimage.png?alt=media&#x26;token=64cb4abc-f72a-4d67-a8d9-2dfa7277f55a" alt=""><figcaption></figcaption></figure>

### Solution

```java
// Function for finding maximum and value pair
public static int lenOfLongSubarr (int nums[], int N, int K) {
    // N -> Length of nums
    // Time complexity: O(n)
    // Space complexity: O(n), n -> Space taken by HashMap
    int prefix = 0, maxLen = 0;
    
    // Store the prefix sum with the position
    Map<Integer, Integer> map = new HashMap<>();
    
    for(int i=0;i<N;i++) {
        prefix += nums[i];
        
        // To handle the case where the prefix sum itself equals to target sum
        if(prefix == K) { 
            // Then the longest subarray is the current position itself
            maxLen = i+1;
        }
        
        // Checking the complement and last position where it occurred
        // to calculate the maximum length of the subarray
        int complement = prefix - K;
        if(map.containsKey(complement)) {
            maxLen = Math.max(maxLen, i - map.get(complement));
        }
        
        // Putting prefix as we check if the prefix is found in previous positions
        map.putIfAbsent(prefix, i);
    }
    return maxLen;
}
```