FastPrepRecoverable Elements from Range-Sum Measurements
Problem · Array

Recoverable Elements from Range-Sum Measurements

Learn this problem
● HardEthos Life logoEthos LifeFULLTIMEOA

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 numeric sums are consistent but are not included in the callable interface because whether an individual element is uniquely determined depends only on which ranges were measured, not on their values.

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^5
  • 1 <= left.length == right.length <= 10^5
  • 1 <= left[j] <= right[j] <= n
  • All reported range sums are mutually consistent.
  • Indices in the returned array must be strictly increasing.
drafts saved locally
public int[] recoverableIndices(int n, int[] left, int[] right) {
    // write your code here
}
n3
left[1,1]
right[3,2]
expected[3]
checking account