initial
I just didnt know how to set starting point. We can iterate number from lower to upper and see if when we add the differences along the way it is still in the range but it is n^2.
solution
The key is maths here.
et's go back to our example: differences = [1, -3, 4], lower = 1, upper = 6.
The hidden sequence has length 4. Let start be the first number. The sequence is:
hidden[0] = start
hidden[1] = start + 1
hidden[2] = start + 1 + (-3) = start - 2
hidden[3] = start - 2 + 4 = start + 2
Now, we need all of these to be within [1, 6]:
For hidden[0] = start:
1 <= start <= 6
For hidden[1] = start + 1:
1 <= start + 1 <= 6 => 0 <= start <= 5
For hidden[2] = start - 2:
1 <= start - 2 <= 6 => 3 <= start <= 8
For hidden[3] = start + 2:
1 <= start + 2 <= 6 => -1 <= start <= 4
Now, the start value we choose must satisfy all of these conditions simultaneously. We need to find the range of start that is valid for all four positions.
To do this, we find the most restrictive lower bound and the most restrictive upper bound from all the individual conditions.
The lower bounds for start are: 1, 0, 3, -1. The maximum of these is 3.
The upper bounds for start are: 6, 5, 8, 4. The minimum of these is 4.
It is the interval math where we find the max of the left lower boundary and the min of the right upper boundary. Those are our leftmost and rightmost boundary when we add those differences along the way. One edge case u have to consider is if diiferences=[0] , ans is 1. That is cuz if a valid range exists (max_start >= min_start), we do max_start-min_start+1, else we return 0 as there is no valid range.
complexity
n time
1 space
