mediumSliding WindowPattern: Sliding Window

Longest Subarray With Sum Exceeding Threshold Solution

Problem Statement

You are given a 0-indexed array of integers `nums` and an integer `threshold`. Find the length of the longest contiguous subarray whose sum is strictly greater than `threshold`.

Examples

Example 1:

Input:{"nums":"[1, 3, 2, 4, 5]","threshold":6}

Output:3

Explanation: The subarray [2, 4, 5] has a sum of 11, which is greater than 6. Its length is 3. The subarray [4, 5] has sum 9 > 6 (length 2). The subarray [5] has sum 5 <= 6. The subarray [3, 2, 4] has sum 9 > 6 (length 3). The subarray [3, 2, 4, 5] has sum 14 > 6 (length 4). The longest such subarray is [3, 2, 4, 5] with length 4.

Example 2:

Input:{"nums":"[1, 2, 3]","threshold":10}

Output:0

Explanation: No subarray has a sum strictly greater than 10. The sum of the entire array is 6.

Example 3:

Input:{"nums":"[10, 5, 1, 2, 8]","threshold":12}

Output:3

Explanation: The subarray [5, 1, 2, 8] has a sum of 16 > 12 (length 4). The subarray [1, 2, 8] has a sum of 11 <= 12. The subarray [2, 8] has a sum of 10 <= 12. The subarray [10, 5] has a sum of 15 > 12 (length 2). The subarray [10, 5, 1] has a sum of 16 > 12 (length 3). The subarray [10, 5, 1, 2] has a sum of 18 > 12 (length 4). The subarray [10, 5, 1, 2, 8] has sum 26 > 12 (length 5). The longest is length 5.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= threshold <= 10^9

Time: O(N log N) or O(N) with sliding window Space: O(N) for prefix sums or O(1) with sliding window

Calculate the prefix sums of the array. For each possible ending index `j`, we need to find the smallest starting index `i` (i <= j) such that the sum of the subarray `nums[i...j]` is greater than `threshold`. This can be done efficiently using binary search on the prefix sums or by maintaining a sliding window where the sum is tracked.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

def longest_subarray_with_sum_exceeding_threshold(nums, threshold):
    n = len(nums)
    if n == 0:
        return 0

    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]

    max_length = 0

    for j in range(n):
        # We are looking for the smallest i (0 <= i <= j) 
        # such that prefix_sum[j+1] - prefix_sum[i] > threshold
        # which means prefix_sum[i] < prefix_sum[j+1] - threshold
        
        target = prefix_sum[j + 1] - threshold
        
        # Binary search for the smallest index 'i' in prefix_sum[0...j+1]
        # such that prefix_sum[i] < target
        
        low, high = 0, j + 1
        best_i = -1

        while low < high:
            mid = (low + high) // 2
            if prefix_sum[mid] < target:
                best_i = mid  # Found a potential start index
                high = mid    # Try to find an even smaller index
            else:
                low = mid + 1

        if best_i != -1:
            # best_i is the smallest index in prefix_sum array such that prefix_sum[best_i] < target.
            # This means the subarray starting at index 'best_i' in nums and ending at 'j' 
            # has a sum greater than threshold.
            # The length of this subarray is (j - best_i + 1).
            max_length = max(max_length, j - best_i + 1)

    return max_length