Problem overview
The method longestSubarray receives an Array[Int] named nums of positive integers and a limit S. It must find the longest contiguous block of elements whose sum is at most S, and return its start and end indices as an Array[Int] of two elements, both inclusive.
In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11. The block from index 3 to index 8 is [2, 2, 1, 1, 3, 1], with sum 10, so the answer is [3, 8]. Extending it by one element on either side pushes the sum past 11. The statement asks for O(n) time and O(1) extra space.
Approach: a window that only moves right
The brute-force way tries every start index and, for each, every end index, recomputing sums. That is at least O(n²). The elements are all positive, which gives a faster tool: adding an element to a block always increases its sum, and removing one always decreases it. So a block that is too big can be fixed by shrinking it from the left, and a block that still fits can be grown on the right.
The solution keeps a window of consecutive elements that starts at first and ends just before last. For each possible first, it grows the window rightward as far as the limit allows. Then it removes nums(first) and moves to the next start. The key point is that last never moves back. If the window from first reached up to last - 1, then the window from first + 1 can start from the same right end, because dropping an element only makes the sum smaller. Every element enters the window once and leaves it once, which is why the whole scan is linear.
Step by step
- Prepare the answer.
var answer = Array(0, 0)is a placeholder for the best pair of indices. It is replaced as soon as a valid window is found. - Declare three counters, one per line, all starting at 0:
maxLen(the longest length so far),sum(the sum of the window) andlast(the index of the next element to try adding). - Loop over the start index.
for (first <- nums.indices)tries each position as the left end.lastis declared outside this loop on purpose, so the window keeps its right end whenfirstmoves. - Grow the window with
while (last < nums.length && sum + nums(last) <= S). The bounds check comes first:&&stops evaluating as soon as the left side is false, sonums(last)is never read past the end. - Add the element:
sum += nums(last). - Record a new best. The window now covers
firstthroughlast, so its length islast - first + 1. IfmaxLen < last - first + 1, updatemaxLenand setanswer = Array(first, last). The strict<keeps the leftmost window when two have the same length. - Move on with
last += 1, still inside thewhileloop. - Slide the window. After the
whileloop,sum -= nums(first), because the next start excludesnums(first). - Return
answeras the last expression.
The solution in Scala
class Solution {
def longestSubarray(nums: Array[Int], S: Int): Array[Int] = {
var answer = Array(0, 0)
var maxLen = 0
var sum = 0
var last = 0
for (first <- nums.indices) {
while (last < nums.length && sum + nums(last) <= S) {
sum += nums(last)
if (maxLen < last - first + 1) {
maxLen = last - first + 1
answer = Array(first, last)
}
last += 1
}
sum -= nums(first)
}
answer
}
}
The Scala details worth knowing:
- Array indexing uses parentheses. Scala writes
nums(last), notnums[last], because an array is accessed through a method call. An index outside the array throwsArrayIndexOutOfBoundsException, which is what thelast < nums.lengthcheck prevents. nums.indicesis the range0 until nums.length. Aforover it gives each valid index in order.- No
++. Scala has no increment operator. The code useslast += 1, andsum += xandsum -= xin the same way. varfor the answer.answeris reassigned to a new two-elementArrayeach time a longer window is found. The array holds twoInts, andIntis 32 bits and wraps silently on overflow, which would matter only if the sum could exceed about 2.1 billion.- Short-circuit
&&. The right-hand side of&&is evaluated only when the left is true, and that is what makes the order of the two conditions matter. - The last expression is the result.
answerneeds noreturn.
When one element is larger than S
If nums(first) alone is bigger than S, the window is empty: last equals first and the while loop doesn't run. The line sum -= nums(first) then still runs, so sum becomes negative. The code still works, because a negative sum is the signed sum of the window, and the next iteration adds the element back when last catches up. The window length last - first + 1 is never positive in that stretch, so no answer is recorded from it. For nums = [5, 6, 1, 1] and S = 2 the method returns [2, 3].
Complexity
Time: O(n). The outer loop runs n times. The pointer last only moves forward and never passes n, so the while loop runs at most n times across all iterations of the outer loop. The total work is at most about 2n steps.
Space: O(1). The method uses a handful of integers and the two-element answer array.
Edge cases and common mistakes
- The whole array fits.
nums = [1, 2, 3]withS = 100gives[0, 2]. - No element fits.
nums = [9, 9, 9]withS = 4returns the placeholder[0, 0]. That pair does not describe a valid subarray, sincenums(0)is above the limit, so a caller who needs to detect this case has to check separately. - Ties.
nums = [2, 2, 2]withS = 4has two windows of length 2. The strict<keeps the first,[0, 1]. - The best window is at the end.
[4, 1, 1, 1]withS = 3gives[1, 3]. The window gets there becauselastcarries over from one start to the next. - Resetting
lastorsuminside the loop. Doing that throws away the shared work and makes the methodO(n²). - Checking the sum after adding. The condition tests
sum + nums(last) <= Sbefore adding, so the window is always valid. - Using the idea with negative numbers. Shrinking the window no longer reduces the sum, so the method depends on the elements being positive.
- Off-by-one in the length. Both ends are inclusive here, so the length is
last - first + 1.
Testing
[3, 2, 5, 2, 2, 1, 1, 3, 1, 2]withS = 11gives[3, 8].[1, 2, 3]withS = 100gives[0, 2].[5, 1, 1]withS = 2gives[1, 2].[2, 2, 2]withS = 4gives[0, 1].[4, 1, 1, 1]withS = 3gives[1, 3].[9, 9, 9]withS = 4gives[0, 0].
