Find Array Elements Uniquely Determined by Known Range Sums

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

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

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

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

Input:  n = 1, queries = [(1, 1)]
Output: [1]

The only element is a listed range by itself.

Recoverable Elements from Known Range Sums

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

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

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.

Hints

1. 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.
2. 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.
3. A single element A[i] is itself the difference of two consecutive prefix sums.

Approach

Let P[0] = 0 and P[k] = A[1] + ... + A[k] be the prefix sums, so a listed range [L, R] reveals exactly the difference P[R] - P[L-1], and A[i] = P[i] - P[i-1]. Build a graph on the n + 1 nodes 0..n with one edge L-1 -- R per listed range, maintained with a union-find structure (path compression). Invariant: after processing the ranges, two nodes share a component exactly when the listed sums determine the difference of their prefix values. If i-1 and i are in the same component, summing the signed range sums along the connecting path yields P[i] - P[i-1] = A[i], so A[i] is recoverable. If they are in different components, at least one of those components does not contain node 0; adding any integer t to every prefix value in that component keeps P[0] = 0 and every listed difference unchanged (each edge lies inside one component), yet changes A[i] by t, giving two integer arrays that agree on all listed sums but differ at i, so A[i] is not recoverable. Scanning i = 1..n therefore yields the recoverable positions already in ascending, 1-indexed order. Edge cases: repeated or redundant ranges merely re-join the same component; a component need not contain node 0 for its interior positions to be recoverable (for example a singleton range [3, 3]); when the scan finds nothing the function returns [-1]; n = 1 with [1, 1] returns [1]. All values stay below 2^31 - 1.

• Time complexity: O((n + q) log n), where q = len(queries)
• Space complexity: O(n)