fizzbuzzer

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Longest Subarray

Sharing is caring!

Problem Statement
A subarray of array a is defined as a contiguous block of a’s elements having a length that is less than or equal to the length of the array. For example, the subarrays of array a = [1, 2, 3] are , , , [1, 2], [2, 3], and [1, 2, 3]. Given an integer, k = 3, the subarrays having elements that sum to a number ≤ k are , , and [1, 2]. The longest of these subarrays is [1, 2], which has a length of 2. Given an array, a, determine its longest subarray that sums to less than or equal to a given value k.

Function Description
Complete the function maxLength in the editor below. The function must return an integer that represents the length of the longest subarray of a that sums to a number ≤ k.

maxLength has the following parameter(s):

a[a,…a[n-1]]: an array of integers
k: an integer

Constraints
1 ≤ n ≤ 105
1 ≤ a[i] ≤ 103
1 ≤ k ≤ 109

Sample Input 0

3
1
2
3
4

Sample Output 0

2

Explanation 0
The subarrays of [1, 2, 3] having elements that sum to a number ≤ (k = 4) are , , , and [1, 2]. The longest of these is [1, 2], which has a length of 2. Return 2 as the answer.

Solution

public class LongestSubarray {

public static int maxLength(List<Integer> a, int k) {
int maxLen = -1;
int sum = 0;
int start = 0;
int end = 0;

for (int i = 0; i < a.size(); i++) {
sum += a.get(i);
end = i;

while (sum > k) {
sum -= a.get(start);
start++;
}

maxLen = Math.max(maxLen, end - start + 1);
}

return maxLen;
}

public static void main(String[] args) {

System.out.println(maxLength(Arrays.asList(1,2,3), 7));
}
}