Recoverable Elements from Range-Sum Measurements
Updated
Problem statement
An unknown integer array A has indices from 1 through n. You are told the sums of several inclusive ranges. The arrays left and right describe those measurements: measurement j gives the value of A[left[j]] + ... + A[right[j]].
The sums themselves are consistent. They are not given to you, because whether one element can be worked out depends only on which ranges were measured, not on the sums.
An index i is recoverable when every two integer arrays that agree with all measured range sums must have the same value at A[i]. Return all recoverable indices in increasing order. Return an empty array when no index is recoverable.
Function
recoverableIndices(n: int, left: int[], right: int[]) → int[]Examples
Example 1
n = 3left = [1,1]right = [3,2]return = [3]Subtracting the sum of indices 1..2 from the sum of 1..3 determines A[3]. Neither of the other two elements is determined individually.
Example 2
n = 5left = [1,4]right = [2,5]return = []The two measurements cover disjoint two-element ranges. Each pair can change internally while preserving its measured sum, so no single index is recoverable.
Example 3
n = 4left = [1,2,1]right = [2,4,4]return = [1,2]The three measurements determine the sums of 1..2, 2..4, and 1..4. Their differences determine A[1] and then A[2], while A[3] and A[4] can still vary together.
Constraints
1 <= n <= 10^51 <= left.length == right.length <= 10^51 <= left[j] <= right[j] <= n- All reported range sums are mutually consistent.
- Indices in the returned array must be strictly increasing.
Similar questions at other companies
- Optimal TransferSnowflake · OASnowflake interview questions
- Number of Islands IISpaceX · PHONE SCREENSpaceX interview questions
- Number of Islands IIAmazon · ONSITE INTERVIEW
- Find All People With SecretIDFC Bank · ONSITE INTERVIEWIDFC Bank interview questions
- Group Linked Merchant RecordsStripe · PHONE SCREENStripe interview questions
- Radar Barrier CrossingSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Accounts MergeOracle · ONSITE INTERVIEWOracle interview questions
- Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
- Largest Consistent Visiting GroupAuxoAI · OA
- Minimum Cost to Supply Water with Wells and PipesInfosys · OAInfosys interview questions