Python Program to find the length of largest subarray with sum k

Given an array of integers, we are going to find the length of the largest subarray with sum k in Python. For example

Input: arr[] = {2, 4, 5, 6, -3, 1}
k = 12
Output: 4
Explanation: The longest subarray with elements sum is k {4, 5, 6, -3}.

Input: arr[] = {1, 0, -4}
k = 2
Output: 0
Explanation: There is no possible subarray with sum k.

Input: arr[] = {4, -1, 1, 0, 10}
k = 1
Output: 1
Exaplnation: The longest subarray with elements sum is k {1}.

Largest Subarray with Sum k

Method 1: Using two nested loops

1. Consider all the subarray one by one and check the sum of every subarray.

2. If the sum of the subarray and k is equal then return the maximum length.

See the Python code below:

def longest_len(arr, k):
    max_len = 0
    for i in range(len(arr)):
        current_sum = 0
        for j in range(i, len(arr)):
            current_sum += arr[j]
# if current_sum equal to k then update max_len
            if current_sum == k:
                max_len = max(max_len, j-i+1)
    return max_len

arr = [15, -2, -8, 1, 7, 10, 13, 5, 6, 2]
k = int(input("Enter the k value: "))
print("The length of the longest subarray with sum k is ", longest_len(arr, k))

Output

Enter the k value: 13
The length of the longest subarray with sum k is 5

This method takes O(n^2) time complexity and O(1) space complexity.

Method 2: Using a Hash Map

A Hash Map allows intersection and deletions of key-value pair in constant time.

1. Create a hash map to store the sum-index pair as a key-value pair.

2. For every index of the array, update the value of the sum.

3. Check if the current is present in the hash map or not.

4. If present update the max len value.

5. Else add current value to hash map.

6. Return the maximum length.

def longest_len(arr, k):
    hash_map = {}
    max_len = 0
    current_sum = 0
    for i in range(len(arr)):
        current_sum += arr[i]

        if arr[i] is k and max_len is 1:
            max_len = 1

        if current_sum == k:
            max_len = i+1

        if current_sum in hash_map:
            max_len = max(max_len, i-hash_map[current_sum])
        else:
            hash_map[current_sum] = i

    return max_len

arr = [15, -2, 2, -8, 1, 7, 10, 13]
k = int(input("Enter the k value: "))
print("The length of the longest subarray with sum k is ", longest_len(arr, k))

Output

Enter the k value: 12
The length of the longest subarray with sum k is 3

Enter the k value: 0
The length of the longest subarray with sum k is 5

Leave a Reply

Your email address will not be published. Required fields are marked *