Longest subarray with sum at most k

Tags:

Given an array of integers A[], find the length of the longest subarray with the sum at most k where k is an integer. For example:

Input:
A[] = [10, 5, 2, 7, 1, 9], 
k = 15
Output:
4
Explanation
longest subarray with sum at most K is [ 5, 2, 7, 1 ].

Input:
A[] = {-5, 8, -14, 2, 4, 12},
k = 5
Output:
5

Longest subarray with a sum k

First of all, if you are not aware of the fundamentals of a sliding window, I would strongly recommend reading: Sliding window concept

The question is how do we know that this is a sliding window problem? Two hints are present in the problem itself, first, we are looking for a subarray i.e. a window, and second, that window has a certain property i.e with a sum of elements at most k.

We will follow the standard pattern for the sliding window; define two pointers, left(l)and right(r). l shrinks the window whenever a property of the window is violated and r expands the window. Every time we expand the window, we add the number to the current sum. If the sum becomes greater than k, we note down the length of this window and update the maximum length if this greater than the previous length. Then we start shrinking the window and subtract the numbers from the sum until the sum is less or equal to k again.

Let’s take an example and see how it works.
Longest subarray with sum at most k

Show me the implementation

package AlgorithmsAndMe;

public class SubarrayWithSumK {
    public int lengthOfSubarray(int[] a, int k){
        int l = 0;
        int r = 0;

        int len = a.length;
        int max = 0;
        int currentSum = 0;

        while(r < len){
            currentSum += a[r];

            while(l < r && currentSum > k){
                max = Math.max(max, r -l);
                currentSum -= a[l];
                l++;
            }
            r++;
        }

        return max;
    }
}

The time complexity of the above code is linear i.e O(n) with O(1) space complexity.

If you are interested, there is another similar problem on Leetcode called Subarray Product Less Than K, you can try there.

Error loading source code.

Show me the answer

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
       
        int l = 0;
        int r = 0;

        if(k == 0) return 0;
        int len = nums.length;
        int count = 0;
        int currentProd = 1;

        while(r < len){
            currentProd *= nums[r];

            while(l <= r && currentProd >= k){
                currentProd /= nums[l];
                l++;
            }
            count += r - l + 1;
            r++;
        }
        
        return count;
    }
}

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.