Longest Subarray with Given Sum (Positives)

Given an array of positive integers and a target sum k, your task is to find the length of the longest contiguous subarray whose elements sum up to exactly k.

If no such subarray exists, return 0.

This problem assumes all elements in the array are positive, which allows us to use an efficient sliding window approach.

Step-by-Step Beginner-Friendly Solution: Longest Subarray with Given Sum (k)

Understanding the Problem

We are given an array of positive integers and a target value k. Our task is to find the longest contiguous subarray whose elements sum up exactly to k.

Let’s break this down:

• A subarray is a part of the array with consecutive elements.
• We are not interested in all such subarrays — only the one that has the maximum length and whose total sum is k.

Example to Understand

arr = [1, 2, 3, 1, 1, 1, 4, 2, 3], k = 6

Let’s walk through this manually:

• [1, 2, 3] → sum = 6 → valid, length = 3
• [1, 1, 1, 1, 2] → sum = 6 → valid, length = 5
• [4, 2] → sum = 6 → valid, length = 2

So, the longest subarray with sum = 6 is length 5.

How Can We Solve This Efficiently?

We use a powerful technique called the sliding window, which is ideal when all array elements are positive.

Why Sliding Window Works for Positive Numbers

When elements are positive:

• Adding more elements to the window increases the sum.
• To reduce the sum, we can safely remove elements from the beginning of the window.

Approach: Sliding Window Algorithm

• Initialize two pointers start and end at index 0.
• Maintain a variable curr_sum to store the current sum of the window.
• Also keep track of max_len to record the maximum length of a valid subarray found so far.

Edge Cases: What Happens Then?

• No Valid Subarray: max_len remains 0.
• Empty Array: Nothing to process, so return 0.
• Single Element Equals k: Return 1 as that single element forms the subarray.
• Target Sum is 0: With all elements positive, we cannot reach a sum of 0, so return 0.

This solution is very efficient. It visits each element at most twice — once when expanding the window and once when shrinking it — giving it a time complexity of O(n).

Note: This technique only works when all elements in the array are positive. If negative numbers are allowed, we’ll need a different approach such as prefix sums with a hashmap.

1. Given an array arr and a target sum k.
2. Initialize variables: start = 0, curr_sum = 0, and max_len = 0.
3. Traverse the array using a loop with index end:
4. → Add arr[end] to curr_sum.
5. → While curr_sum > k, subtract arr[start] from curr_sum and increment start.
6. → If curr_sum == k, update max_len as max(max_len, end - start + 1).
7. Return max_len as the result after the loop.

#include <stdio.h>

int longestSubarraySumK(int arr[], int n, int k) {
    int start = 0, curr_sum = 0, max_len = 0;
    for (int end = 0; end < n; end++) {
        curr_sum += arr[end];
        while (curr_sum > k) {
            curr_sum -= arr[start++];
        }
        if (curr_sum == k) {
            if (max_len < end - start + 1)
                max_len = end - start + 1;
        }
    }
    return max_len;
}

int main() {
    int arr[] = {1, 2, 3, 1, 1, 1, 1, 2};
    int k = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Longest Subarray Length: %d\n", longestSubarraySumK(arr, n, k));
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int longestSubarraySumK(vector<int>& arr, int k) {
    int start = 0, curr_sum = 0, max_len = 0;
    for (int end = 0; end < arr.size(); end++) {
        curr_sum += arr[end];
        while (curr_sum > k) {
            curr_sum -= arr[start++];
        }
        if (curr_sum == k) {
            max_len = max(max_len, end - start + 1);
        }
    }
    return max_len;
}

int main() {
    vector<int> arr = {1, 2, 3, 1, 1, 1, 1, 2};
    int k = 5;
    cout << "Longest Subarray Length: " << longestSubarraySumK(arr, k) << endl;
    return 0;
}

def longest_subarray_sum_k(arr, k):
    start = 0
    curr_sum = 0
    max_len = 0
    for end in range(len(arr)):
        curr_sum += arr[end]
        while curr_sum > k:
            curr_sum -= arr[start]
            start += 1
        if curr_sum == k:
            max_len = max(max_len, end - start + 1)
    return max_len

arr = [1, 2, 3, 1, 1, 1, 1, 2]
k = 5
print("Longest Subarray Length:", longest_subarray_sum_k(arr, k))

public class LongestSubarraySumK {
    public static int longestSubarraySumK(int[] arr, int k) {
        int start = 0, curr_sum = 0, max_len = 0;
        for (int end = 0; end < arr.length; end++) {
            curr_sum += arr[end];
            while (curr_sum > k) {
                curr_sum -= arr[start++];
            }
            if (curr_sum == k) {
                max_len = Math.max(max_len, end - start + 1);
            }
        }
        return max_len;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 1, 1, 1, 1, 2};
        int k = 5;
        System.out.println("Longest Subarray Length: " + longestSubarraySumK(arr, k));
    }
}

function longestSubarraySumK(arr, k) {
    let start = 0, curr_sum = 0, max_len = 0;
    for (let end = 0; end < arr.length; end++) {
        curr_sum += arr[end];
        while (curr_sum > k) {
            curr_sum -= arr[start];
            start++;
        }
        if (curr_sum === k) {
            max_len = Math.max(max_len, end - start + 1);
        }
    }
    return max_len;
}

const arr = [1, 2, 3, 1, 1, 1, 1, 2];
const k = 5;
console.log('Longest Subarray Length:', longestSubarraySumK(arr, k));

package main

import (
    "fmt"
)

func longestSubarraySumK(arr []int, k int) int {
    start, currSum, maxLen := 0, 0, 0
    for end := 0; end < len(arr); end++ {
        currSum += arr[end]
        for currSum > k {
            currSum -= arr[start]
            start++
        }
        if currSum == k {
            if maxLen < end-start+1 {
                maxLen = end - start + 1
            }
        }
    }
    return maxLen
}

func main() {
    arr := []int{1, 2, 3, 1, 1, 1, 1, 2}
    k := 5
    fmt.Println("Longest Subarray Length:", longestSubarraySumK(arr, k))
}

fn longest_subarray_sum_k(arr: &[i32], k: i32) -> usize {
    let (mut start, mut curr_sum, mut max_len) = (0, 0, 0);
    for end in 0..arr.len() {
        curr_sum += arr[end];
        while curr_sum > k {
            curr_sum -= arr[start];
            start += 1;
        }
        if curr_sum == k {
            max_len = max_len.max(end - start + 1);
        }
    }
    max_len
}

fn main() {
    let arr = vec![1, 2, 3, 1, 1, 1, 1, 2];
    let k = 5;
    println!("Longest Subarray Length: {}", longest_subarray_sum_k(&arr, k));
}

fun longestSubarraySumK(arr: IntArray, k: Int): Int {
    var start = 0
    var currSum = 0
    var maxLen = 0
    for (end in arr.indices) {
        currSum += arr[end]
        while (currSum > k) {
            currSum -= arr[start++]
        }
        if (currSum == k) {
            maxLen = maxOf(maxLen, end - start + 1)
        }
    }
    return maxLen
}

fun main() {
    val arr = intArrayOf(1, 2, 3, 1, 1, 1, 1, 2)
    val k = 5
    println("Longest Subarray Length: ${longestSubarraySumK(arr, k)}")
}

func longestSubarraySumK(_ arr: [Int], _ k: Int) -> Int {
    var start = 0, currSum = 0, maxLen = 0
    for end in 0..<arr.count {
        currSum += arr[end]
        while currSum > k {
            currSum -= arr[start]
            start += 1
        }
        if currSum == k {
            maxLen = max(maxLen, end - start + 1)
        }
    }
    return maxLen
}

let arr = [1, 2, 3, 1, 1, 1, 1, 2]
let k = 5
print("Longest Subarray Length:", longestSubarraySumK(arr, k))

function longestSubarraySumK(arr: number[], k: number): number {
    let start = 0, curr_sum = 0, max_len = 0;
    for (let end = 0; end < arr.length; end++) {
        curr_sum += arr[end];
        while (curr_sum > k) {
            curr_sum -= arr[start];
            start++;
        }
        if (curr_sum === k) {
            max_len = Math.max(max_len, end - start + 1);
        }
    }
    return max_len;
}

const arr: number[] = [1, 2, 3, 1, 1, 1, 1, 2];
const k: number = 5;
console.log("Longest Subarray Length:", longestSubarraySumK(arr, k));

Time complexity

Space complexity

O(1)

The algorithm uses constant extra space — only a few variables are maintained (start, end, curr_sum, max_len), regardless of input size.