Start learning free

LESSON 213 OF 347 · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in C#: O(n²) Brute Force

Practice O(n2) 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
    Ctrl + Enter to check

    C# · PARTIAL SUMS #1

    Longest Subarray With Sum At Most S in C#, explained

    Problem overview

    The method LongestSubarray receives an array of positive integers nums and a number S. It must find the longest contiguous subarray whose sum is at most S, and return its start and end indices as an int[].

    In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11. The subarray from index 3 to index 8 is [2, 2, 1, 1, 3, 1]. It has 6 elements and sums to 10, which is within the limit. No subarray of 7 elements fits under 11, so the answer is [3, 8].

    The statement asks for O(n²) time and O(1) extra space. That allows checking every subarray, as long as each check costs constant time.

    Approach: every start, every end, running sum

    A subarray is determined by its start index i and its end index j. The brute force tries every pair with j >= i. That is about n²/2 pairs, so O(n²) overall, as long as the sum of each subarray is available without another loop.

    It is. For a fixed i, moving j one step right extends the subarray by one element, so the sum grows by exactly nums[j]. A running sum, reset to 0 for each new start, gives every subarray's sum with a single addition. Without the running sum, adding up each subarray separately would cost O(n³).

    The rest is bookkeeping: whenever a subarray fits (sum <= S) and is longer than the best one so far, remember its length and its indices.

    Here is how the example plays out for the start i = 3. The running sum grows as j moves: 2, 4, 5, 6, 9, 10 for j from 3 to 8, all within 11, so the best length becomes 6. At j = 9 the sum is 12, which is too large, so that subarray is skipped. No later start finds a longer subarray. The start i = 4 ties it with [4, 9], which also has 6 elements and sums to 10, but the strict comparison keeps [3, 8].

    Step by step

    1. Prepare the result. answer starts as an empty array. It is replaced by a new two-element array whenever a longer valid subarray is found.
    2. Track the best length. maxLen starts at 0, so the first valid subarray, even a single element, is longer than it.
    3. Choose a start. The outer loop runs i from 0 while i < nums.Length.
    4. Restart the sum. Inside it, sum is declared as 0. Because it is declared inside the outer loop, it begins at 0 for every new start.
    5. Choose an end. The inner loop runs j from i, so the first subarray tried is the single element nums[i].
    6. Extend the sum. Add nums[j] to sum. Now sum is the total of nums[i..j].
    7. Check both conditions. The subarray must be valid, sum <= S, and longer than the best, maxLen < (j - i + 1). The length of the range from i to j inclusive is j - i + 1.
    8. Record it. Set maxLen to the new length, and answer to new int[]{i, j}.
    9. Return answer after both loops.

    The solution in C#

    class Solution {
    public int[] LongestSubarray(int[] nums, int S) {
        int[] answer = new int[]{};
        int maxLen = 0;
        for (int i = 0; i < nums.Length; i++) {
            int sum = 0;
            for (int j = i; j < nums.Length; j++) {
                sum += nums[j];
                if (sum <= S && maxLen < (j - i + 1)) {
                    maxLen = j - i + 1;
                    answer = new int[]{i, j};
                }
            }
        }
        return answer;
    }
}

    C# details worth noticing

    • The parameter is named S, in capitals. C# is case-sensitive, so S and s are different identifiers. Use the name exactly as the method declares it.
    • && short-circuits. If sum <= S is false, the length comparison isn't evaluated. Here it makes no difference to the result, but it is good to know.
    • Arrays are fixed-size. new int[]{i, j} creates a fresh two-element array each time a better subarray is found. The old one is simply dropped.

    Complexity

    Time: O(n²). For each of the n starts, the inner loop runs up to n - i times, and each iteration does constant work. In total that is about n(n + 1)/2 iterations.

    Space: O(1). There are a few int variables and one two-element result array, whose size doesn't depend on n.

    Because every number is positive, the sum can only grow as j moves right, so once it exceeds S no later j for that i can fit. The code doesn't exploit this and keeps looping, and that idea is what the faster two-pointer solution builds on.

    Edge cases and common mistakes

    • No subarray fits. If every element is greater than S, for example [5, 6] with S = 3, no condition ever succeeds and the method returns an empty array. Code that uses the result should check its length before indexing it.
    • The whole array fits. For [1, 2, 3] with S = 6, the answer is [0, 2].
    • Ties. The comparison is strict, so a later subarray of the same length doesn't replace an earlier one. The result is the leftmost longest subarray.
    • Length versus index. The length is j - i + 1. Forgetting the + 1 makes single-element subarrays look like length 0.
    • Not resetting sum. Moving the declaration of sum outside the outer loop would leak the previous start's total into the next one.
    • Returning a length. The method returns the two indices, not the length of the subarray.

    Testing

    • [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] with S = 11 returns [3, 8].
    • [1, 2, 3] with S = 6 returns [0, 2].
    • [5, 6] with S = 3 returns an empty array.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free