LESSON 237 OF 414 · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in Scala: O(n^2) 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

SCALA · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in Scala, explained

Problem overview

The method longestSubarray receives an Array[Int] of positive integers, nums, and a number S. It must find the longest continuous subarray whose sum is at most S, and return its start and end indices as a two-element array.

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 to 8 are 2, 2, 1, 1, 3, 1, which add up to 10. That is six elements. Adding one more element on either side, a 5 on the left or a 2 on the right, would push the sum over 11.

The statement asks for O(n^2) time and O(1) extra space, which is exactly what two nested loops give.

Approach: try every start, extend the end

Every subarray is fixed by its start i and its end j. The outer loop picks the start. The inner loop moves the end to the right one element at a time, and the sum grows by one addition at each step instead of being recomputed.

After each addition, two things decide whether the subarray becomes the new best:

its sum must be at most S, and
it must be longer than the longest valid subarray found so far.

The number of elements from i to j inclusive is j - i + 1. The comparison uses a strict "longer than", so among subarrays of equal length the first one found, the one with the smallest start, is kept.

Because the numbers are positive, the inner loop could stop as soon as the sum passes S: adding more positive numbers can only make it bigger. The lesson's version doesn't stop early, and the condition sum <= S handles those cases anyway. Stopping early is an optimization, and it doesn't change the worst-case bound.

Step by step

Create answer as a var holding an empty Array[Int](). It will hold the best start and end found so far. It is replaced by a new two-element array every time a longer valid subarray turns up.
Create maxLen as a var starting at 0. It stores the length of the best subarray. Starting at 0 means that any valid subarray, which has at least one element, is longer.
Loop i over nums.indices. Each index is a possible start. The expression nums.indices is the range of valid indices, from 0 until the length of the array.
Declare sum as a var equal to 0 inside that loop. It holds the sum of the subarray from i to j, and declaring it inside the outer loop resets it for each new start.
Loop j over i until nums.size. Each j is a possible end for the subarray that starts at i. Starting at i makes the one-element subarray the first one tried.
Add nums(j) to sum. Now sum is the sum of the elements from i to j.
Check both conditions with sum <= S && maxLen < (j - i + 1).
Update maxLen to j - i + 1 inside the if.
Update answer to Array(i, j). A later, longer subarray overwrites it.
Return answer after both loops.

The solution in Scala

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

The Scala details worth knowing:

nums.indices and nums.size. For an array, size and length are the same number. indices is a range, so for (i <- nums.indices) is the same loop as for (i <- 0 until nums.length). On a two-element array, indices prints as Range 0 until 2.
Array[Int]() is an empty array. The type in square brackets is needed, since there are no elements to infer it from.
A parameter called S. Scala parameters can start with a capital letter. The usual style is lower case, but here the name matches the problem statement.
Short-circuit &&. The right side is only evaluated when the left side is true. Both sides here are cheap, so the order doesn't change the result.
Array literals. Array(i, j) creates a new Array[Int]. Since answer is a var, it simply points at the new array.

Complexity

Time: O(n^2). For each of the n starts, the inner loop visits up to n - i ends, so the total is about n * (n + 1) / 2 steps. Each step does a constant amount of work, because the sum is extended by one element and not recomputed.

Space: O(1). The variables are single integers, and the answer array always has at most two elements.

Edge cases and common mistakes

No valid subarray. If every element is bigger than S, nothing satisfies the condition and the method returns the empty array. For example, [5, 6, 7] with S = 4 gives [].
The whole array fits. [1, 2, 3] with S = 100 gives [0, 2].
Ties. [1, 2, 1, 2] with S = 3 has several subarrays of length 2 with sum 3. The strict comparison keeps the first, [0, 1].
One element. [4] with S = 4 gives [0, 0]. The end index equals the start index, and the length is 1.
Length off by one. The length is j - i + 1. Writing j - i would give 0 for a single element, and it would never beat maxLen = 0.
Declaring sum outside the outer loop. The sum would carry over from the previous start and include elements that aren't in the current subarray.
Using < instead of <= for S. The statement says "at most", so a sum equal to S is allowed.
An empty array. The loops never run and the method returns an empty array.

Testing

[3, 2, 5, 2, 2, 1, 1, 3, 1, 2] with S = 11 gives [3, 8].
[5, 6, 7] with S = 4 gives [].
[1, 2, 3] with S = 100 gives [0, 2].
[1, 2, 1, 2] with S = 3 gives [0, 1].
[4] with S = 4 gives [0, 0].

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

Start learning free