Find Array Elements Uniquely Determined by Known Range Sums
Company: Ethos
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
An integer array `A` of length `n` is hidden from you; its positions are numbered `1` to `n`. You are given a list of ranges `(L, R)`, and the sum `A[L] + A[L+1] + ... + A[R]` of every listed range is known. An element `A[i]` is **recoverable** if those range sums determine its value uniquely.
Return the positions of all recoverable elements.
### Function Signature
```python
def recoverable_positions(n: int, queries: list[tuple[int, int]]) -> list[int]:
```
`queries[j] = (L, R)` is the `j`-th range whose sum is known.
### Rules
- Only the ranges are passed in, not their sums, so recoverability is defined independently of the sum values: position `i` is recoverable if and only if every two integer arrays of length `n` that have equal sums on every listed range also have equal values at position `i`.
- Ranges may repeat, overlap or nest.
- Return the recoverable positions in ascending order. If no position is recoverable, return `[-1]`.
- In the original assessment, the input arrived on standard input (`n` and the number of ranges on the first line, then one `L R` pair per line) and the answer was printed as space-separated positions, or `-1`. Here the same data is passed in and returned directly.
### Constraints
- `1 <= n <= 10^5`
- `1 <= len(queries) <= 10^5`
- `1 <= L <= R <= n` for every range
### Examples
**Example 1**
```text
Input: n = 5, queries = [(1, 3), (1, 2), (4, 5), (5, 5)]
Output: [3, 4, 5]
```
`A[3]` is the sum over `(1, 3)` minus the sum over `(1, 2)`. `A[5]` is the sum over `(5, 5)`, and `A[4]` is the sum over `(4, 5)` minus `A[5]`. Only `A[1] + A[2]` is known, so raising `A[1]` by any amount and lowering `A[2]` by the same amount keeps every listed sum unchanged.
**Example 2**
```text
Input: n = 4, queries = [(1, 2), (3, 4), (1, 4), (2, 3)]
Output: [-1]
```
Adding any integer `t` to `A[1]` and `A[3]` and subtracting `t` from `A[2]` and `A[4]` leaves all four listed sums unchanged, so no element is determined.
**Example 3**
```text
Input: n = 1, queries = [(1, 1)]
Output: [1]
```
The only element is a listed range by itself.
Overview: Given only the index ranges whose sums are known for a hidden integer array, list every position whose value is uniquely determined by those sums, or report -1 if none is. Tests reasoning about how overlapping and nested range sums combine, plus an efficient solution for 100,000 ranges.
Read the full Ethos Software Engineer interview experience this question came from
An integer array `A` of length `n` is hidden from you; its positions are numbered `1` to `n`. You are given a list of ranges `[L, R]`, and the sum `A[L] + A[L+1] + ... + A[R]` of every listed range is known. An element `A[i]` is **recoverable** if those range sums determine its value uniquely.
Implement `recoverable_positions(n, queries)` and return the positions of all recoverable elements.
- `queries` is a single argument: a list of pairs, where `queries[j] = [L, R]` is the `j`-th range whose sum is known (1-indexed, inclusive on both ends).
- Only the ranges are passed in, not their sums, so recoverability is defined independently of the sum values: position `i` is recoverable if and only if every two integer arrays of length `n` that have equal sums on every listed range also have equal values at position `i`.
- Ranges may repeat, overlap or nest.
- Return the recoverable positions (1-indexed) in ascending order. If no position is recoverable, return `[-1]`.
### Constraints
- `1 <= n <= 10^5`
- `1 <= len(queries) <= 10^5`
- `1 <= L <= R <= n` for every range
- Every input and output value fits in a 32-bit signed integer; none can exceed 2^31 - 1.
### Example 1
```text
Input: n = 5, queries = [[1, 3], [1, 2], [4, 5], [5, 5]]
Output: [3, 4, 5]
```
`A[3]` is the sum over `[1, 3]` minus the sum over `[1, 2]`. `A[5]` is the sum over `[5, 5]`, and `A[4]` is the sum over `[4, 5]` minus `A[5]`. Only `A[1] + A[2]` is known, so raising `A[1]` by any amount and lowering `A[2]` by the same amount keeps every listed sum unchanged.
### Example 2
```text
Input: n = 4, queries = [[1, 2], [3, 4], [1, 4], [2, 3]]
Output: [-1]
```
Adding any integer `t` to `A[1]` and `A[3]` and subtracting `t` from `A[2]` and `A[4]` leaves all four listed sums unchanged, so no element is determined.
Constraints
- 1 <= n <= 10^5
- 1 <= len(queries) <= 10^5
- 1 <= L <= R <= n for every range [L, R] in queries
- Every input and output value fits in a 32-bit signed integer (none exceeds 2^31 - 1)
Examples
Input: (5, [[1, 3], [1, 2], [4, 5], [5, 5]])
Expected Output: [3, 4, 5]
Explanation: Source Example 1: A[3] = sum[1, 3] - sum[1, 2]; A[5] from [5, 5], then A[4] = sum[4, 5] - A[5]; only A[1] + A[2] is known.
Input: (4, [[1, 2], [3, 4], [1, 4], [2, 3]])
Expected Output: [-1]
Explanation: Source Example 2: adding t to A[1], A[3] and subtracting t from A[2], A[4] keeps all four sums, so nothing is recoverable.
Hints
- Recoverability depends only on which ranges are listed, not on their sums: to show a position is not recoverable, find two integer arrays that agree on every listed sum but differ at that position.
- Any range sum A[L] + ... + A[R] can be written as the difference of two prefix sums; ask which prefix-sum differences the listed ranges let you derive by adding and subtracting them.
- A single element A[i] is itself the difference of two consecutive prefix sums.