LESSON 214 OF 348 · PARTIAL SUMS #1

Longest Subarray With Sum at Most S in Kotlin: O(n²) Brute Force

Practice O(n²) Read the full explanation

Given an array of positive integers and a number S, find the longest contiguous subarray having the sum at most S.

Return the start and end indices denoting this subarray.

Example

Input: nums = [3, 2, 5, 2, 2, 1, 1, 3, 1 , 2], S = 11
Output: [3, 8]
Explanation:the subarray nums[3...8] of sum 10

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.

STEP 1 OF 10

Guided

Ctrl + Enter to check

KOTLIN · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in Kotlin, explained

Problem overview

The function longestSubarray receives an IntArray of positive integers, nums, and a number S. It must find the longest contiguous subarray whose sum is at most S, and return its first and last index as a two-element IntArray.

In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11. The subarray at indices 3 to 8 is [2, 2, 1, 1, 3, 1]. It has six elements and a sum of 10. Adding the next element, 2, would make the sum 12, which is over the limit. The answer is [3, 8].

The statement allows O(n²) time and O(1) extra space. That is the budget of the approach below: try every start, extend it one element at a time and keep the longest valid result.

Approach: every start, every end

A subarray is determined by its first index i and its last index j. There are about n²/2 such pairs, so checking each of them is affordable here. The only question is how to get each sum cheaply. If every sum were computed by looping from i to j, the total would be O(n³).

The fix is to fix i first and then let j move right one step at a time. Going from j to j + 1 adds a single element, so the sum is updated with one addition instead of being recomputed. Each start therefore costs O(n), and all starts together cost O(n²).

For each pair, two things must hold for the pair to become the new answer: its sum is at most S, and it is longer than the best found so far. The length of the subarray from i to j is j - i + 1, because both ends are included.

Here is how the example unfolds. Starting at index 0, the sums are 3, 5, 10 and then 12, so the longest valid subarray is [0, 2] with three elements. Starting at 1, the sums 2, 7, 9, 11 and then 13 give [1, 4] with four elements. Starting at 2 gives [2, 6] with five, and starting at 3 gives [3, 8] with six. Starting at 4 also reaches length 6, with the subarray [4, 9] and sum 10, but it is not longer than the best so far, so the answer stays [3, 8]. The remaining starts give shorter results.

Step by step

Declare answer with var as IntArray(0). It holds the start and end of the longest valid subarray found so far, and it is replaced each time a longer one turns up.
Declare maxLen with var, starting at 0. It stores the best length so far. Starting at 0 means any valid subarray, of any length, beats it.
Loop i over nums.indices. This range is 0 to nums.size - 1, and each i is a possible start.
Declare sum inside that loop, starting at 0. It must restart for every new start, and declaring it inside the loop does that automatically.
Loop j over i until nums.size. Each j is a possible end for the subarray that starts at i. Starting j at i makes the single element nums[i] the first candidate.
Add nums[j] to sum. Now sum is the total of the elements from i to j.
Test both conditions with &&: sum <= S (the subarray is valid) and maxLen < (j - i + 1) (it is longer than the best).
Record the new length by setting maxLen to j - i + 1.
Record the indices by setting answer to intArrayOf(i, j).
Return answer after both loops.

The solution in Kotlin

class Solution {
    fun longestSubarray(nums: IntArray, S: Int): IntArray {
        var answer = IntArray(0)
        var maxLen = 0
        for (i in nums.indices) {
            var sum = 0
            for (j in i until nums.size) {
                sum += nums[j]
                if (sum <= S && maxLen < (j - i + 1)) {
                    maxLen = j - i + 1
                    answer = intArrayOf(i, j)
                }
            }
        }
        return answer
    }
}

The Kotlin details worth a closer look:

nums.indices. This property gives the range of valid indices, 0 until nums.size. It is the idiomatic way to loop over positions and avoids writing the bound by hand.
A parameter named S. Kotlin is case-sensitive, so S and s are different names. The uppercase S is the parameter's name in the starter code.
&& short-circuits. If sum <= S is false, the second condition isn't evaluated. Here that makes no difference, since both conditions are cheap and have no side effects.
IntArray(0). It creates an array with zero elements, all of the right type. If no subarray is valid, which happens when every element alone exceeds S, this empty array is what the function returns.
The loop keeps going after the sum passes S. Since all numbers are positive, no longer subarray from the same start can come back under S, so a break there would save time. The lesson's version doesn't need it for its O(n²) limit.

Complexity

Time: O(n²). The outer loop runs n times, and for start i the inner loop runs n - i times. That adds up to n(n + 1) / 2 iterations, each doing a constant amount of work. This is within the statement's limit, though a linear-time approach exists for positive numbers, and it is much faster on large arrays. The other lesson on this problem covers a faster version.

Space: O(1). The function stores a few integers and one two-element array.

Edge cases and common mistakes

Ties. The comparison maxLen < (j - i + 1) is strict, so a later subarray of the same length doesn't replace the earlier one. In the example, [4, 9] has length 6 like [3, 8], and the answer stays [3, 8]. Using <= would return [4, 9].
No valid subarray. For [20, 30] and S = 11 the result is an empty array.
The whole array fits. When the total is at most S, the answer is [0, nums.size - 1].
Length formula. The length is j - i + 1. Writing j - i misses one element and compares the wrong lengths.
Not resetting the sum. If sum were declared above the outer loop, each new start would begin with the leftover total of the previous one.
Starting j at i + 1. This skips single-element subarrays, so an array like [3] with S = 5 would return an empty array instead of [0, 0].
Checking only the length. The sum must be tested in the same condition. A long subarray with a sum over S is not valid.

Testing

nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2], S = 11 gives [3, 8].
nums = [1, 2, 3, 1, 2, 3], S = 6 gives [0, 2]: the subarrays at 0 to 2 and 1 to 3 both have three elements and sum 6, and the earlier one wins.
nums = [20, 30], S = 11 gives [].

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free