Find max consecutive elements with sum below target
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given:
- An integer array `nums` of length `n`, sorted in non-decreasing order.
- An integer `index` such that `0 ≤ index < n`.
- An integer `target`.
Starting from position `index`, you may take a contiguous sequence of elements going to the right:
`nums[index], nums[index + 1], ..., nums[index + k - 1]` for some integer `k ≥ 0`.
You want the sum of the chosen elements to be **strictly less than** `target`:
\[
\sum_{i=index}^{index + k - 1} nums[i] < target.
\]
Find the **maximum possible value of `k`** (the maximum number of consecutive elements starting from `index` whose sum is `< target`). If even `nums[index] ≥ target`, then the answer should be `0`.
Design an efficient algorithm to compute this maximum `k`.
You may assume:
- `1 ≤ n`
- `nums` is sorted in non-decreasing order.
Describe the algorithm you would implement and its time and space complexity.
Quick Answer: This question evaluates algorithmic problem-solving with arrays, including reasoning about contiguous subsequences, handling sorted inputs and edge cases, and analyzing time and space complexity.
You are given an integer array `nums` of length `n`, sorted in non-decreasing order, an integer `index` with `0 <= index < n`, and an integer `target`.
Starting from position `index`, you may take a contiguous run of elements going to the right: `nums[index], nums[index+1], ..., nums[index+k-1]` for some integer `k >= 0`. You want the sum of the chosen elements to be **strictly less than** `target`:
nums[index] + nums[index+1] + ... + nums[index+k-1] < target
Return the **maximum possible value of `k`** (the maximum number of consecutive elements starting from `index` whose running sum stays strictly below `target`). If even `nums[index] >= target`, return `0`.
Note: because the array may contain negative or zero values, you cannot simply stop at the first element that is large; walk the prefix sum and count how many elements you can include before the running sum reaches `target`.
**Example:** `nums = [1, 2, 3, 4, 5]`, `index = 0`, `target = 7`. Running sums are 1, 3, 6, 10. The first three (1+2+3=6) stay below 7, but adding 4 gives 10 >= 7, so the answer is `3`.
Constraints
- 1 <= n (n = len(nums))
- nums is sorted in non-decreasing order
- 0 <= index < n
- nums may contain negative, zero, or positive integers
- The chosen run is contiguous and starts exactly at index, extending to the right
- The sum must be STRICTLY less than target (sum == target does not count)
Examples
Input: ([1, 2, 3, 4, 5], 0, 7)
Expected Output: 3
Explanation: Running sums 1, 3, 6 are < 7; adding 4 gives 10 >= 7, so k = 3.
Input: ([1, 2, 3, 4, 5], 2, 100)
Expected Output: 3
Explanation: From index 2: 3, 7, 12 all < 100 and the array ends, so all 3 remaining elements are taken; k = 3.
Hints
- Walk forward from `index`, maintaining a running sum. Increment a counter each time the running sum is still strictly below target.
- Stop the moment the running sum reaches or exceeds target — adding more elements can never reduce it back below target only if all values are non-negative, but since the array is sorted non-decreasing, once you stop you are done.
- Edge case: if `nums[index] >= target` the loop stops before incrementing the counter, so the answer is 0.
- Because the array is sorted, you could also binary-search the prefix-sum array for the first prefix that reaches target, giving O(log n) after an O(n) prefix-sum precompute — but the simple linear scan is already optimal at O(k).