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:
∑i=indexindex+k−1nums[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.