Problem overview
The function longestSubarray receives an array of positive integers, nums, and a limit S. It must find the longest contiguous stretch of the array whose sum is at most S, and return the start and end indices of that stretch as a two-element IntArray.
For nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11, the answer is [3, 8]. The elements at indices 3 through 8 are 2, 2, 1, 1, 3, 1. They sum to 10, and no longer stretch stays within 11.
The statement asks for O(n) time and O(1) extra space.
Approach: a window that never moves left
The brute force tries every start and extends the end until the sum exceeds S. That is O(n²). The waste is that, after finishing one start, it forgets everything and begins the next start from scratch.
Because every number is positive, adding an element can only increase a sum, and removing one can only decrease it. That gives the window a useful property. If the window first..last-1 fits within S, then moving the start to first + 1 also fits: the elements that remain can only add up to less. So the right end never has to move back. For each new start, the window keeps its right end and only needs to grow further.
Here the window is the set of elements from index first up to, but not including, index last. The variable last is the index of the next element to try adding. It only ever increases, so across the whole run it moves at most n times. The start also moves at most n times. The total work is linear.
Step by step
- Prepare the answer.
answeris avarholdingintArrayOf(0, 0). It is only a placeholder, replaced as soon as a valid stretch is found. - Declare three counters with
var:maxLen(the best length so far),sum(the sum of the window) andlast(the next index to add), all starting at 0. They are declared outside the loop so thatlastkeeps its position when the start moves. - Loop over each start,
first, innums.indices. - Grow the window with a
whileloop that runs whilelast < nums.sizeandsum + nums[last] <= S. The bounds check comes first:&&stops evaluating once the left side is false, sonums[last]is never read past the end. - Add
nums[last]tosum. - Record a new best. The window now holds the elements
firstthroughlast, so its length islast - first + 1. If that is larger thanmaxLen, updatemaxLenand setanswertointArrayOf(first, last). The strict<keeps the leftmost stretch when two have the same length. - Move on:
last++. - Slide the window. After the
whileloop, subtractnums[first]fromsum, since the next start no longer includes it. - Return
answerafter the loop.
The solution in Kotlin
class Solution {
fun longestSubarray(nums: IntArray, S: Int): IntArray {
var answer = intArrayOf(0, 0)
var maxLen = 0
var sum = 0
var last = 0
for (first in nums.indices) {
while (last < nums.size && sum + nums[last] <= S) {
sum += nums[last]
if (maxLen < last - first + 1) {
maxLen = last - first + 1
answer = intArrayOf(first, last)
}
last++
}
sum -= nums[first]
}
return answer
}
}
The Kotlin details worth knowing:
IntArrayandintArrayOf.IntArrayis Kotlin's array of primitiveintvalues on the JVM. It is created withintArrayOf(...), and it prints as an object reference rather than its contents, so useanswer.toList()when you want to look at it.nums.indices. It is the range0..nums.size - 1, so the loop is empty for an empty array.var answerand the array.varallowsanswerto refer to a new array each time a better stretch is found. A freshintArrayOf(first, last)is created only when the best length improves, which is rare enough not to matter.- The parameter name
S. A capital letter is legal, and the lesson's code keeps it from the statement. - Short-circuit
&&. The conditionlast < nums.size && sum + nums[last] <= Sonly readsnums[last]when the index is valid. Swapping the two conditions would throw anArrayIndexOutOfBoundsExceptionat the end of the array. - 32-bit sums.
sumis anInt, which wraps silently on overflow. That isn't a problem whileSand the elements stay far below about 2 billion.
Complexity
Time: O(n). The index last only increases, and the inner while loop moves it, so the loop body runs at most n times over the whole call. The outer loop runs n times. Together that is at most about 2n steps.
Space: O(1). The function keeps a few integers and the two-element answer array, regardless of the size of nums.
Edge cases and common mistakes
- An element larger than
S. For[5, 1, 1]withS = 3, the element 5 can't join any window. The result is[1, 2]. The subtractionsum -= nums[first]still happens for that start, and the sum goes negative for a moment. Whenlastlater passes over that element it is added back, so the sums stay consistent. - No valid stretch. If every element exceeds
S, as in[5]withS = 3, nothing replaces the placeholder and the function returns[0, 0]. An empty array returns[0, 0]too. - Ties. For
[4, 4]andS = 4, both stretches have length 1. The result is[0, 0], the leftmost, because of the strict<. - Whole array fits.
[1, 1, 1]withS = 100returns[0, 2]. - Resetting
lastinside the loop. That restores theO(n²)behaviour. Keepinglastoutside is what makes it linear. - Forgetting to subtract
nums[first]. The sum would keep elements that have left the window, and later windows would look too large. - Using it with negative numbers. The idea that a smaller window always fits depends on positive values. With negatives, the sum doesn't grow steadily as the window grows, and this approach no longer works.
Testing
nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2],S = 11gives[3, 8].nums = [9, 1, 1, 9, 1, 1],S = 2gives[1, 2].nums = [7, 1, 2],S = 3gives[1, 2].nums = [1, 1, 1],S = 100gives[0, 2].nums = [4, 4],S = 4gives[0, 0].