O(1) Range Queries: Are All Elements of a Subarray Distinct?
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an integer array `nums` and a range `[l, r]` of indices. Determine whether the elements `nums[l], nums[l + 1], ..., nums[r]` are all distinct, that is, whether no value appears twice in the range.
The interviewer then extended the task: many different ranges will be queried against the same array, so precompute information about `nums` once, with the best preprocessing time you can achieve, such that every query is answered in O(1) time. Implement the extended version, which receives all the queries at once.
### Function Signature
```python
def ranges_distinct(nums: list[int], queries: list[list[int]]) -> list[bool]:
```
### Rules
- Each query is `[l, r]` with 0-indexed, inclusive bounds.
- The answer to a query is `True` if no value occurs more than once among `nums[l..r]`, and `False` otherwise. A range with one element is always `True`.
- Return the answers in the order of `queries`.
- The preprocessing may depend only on `nums`, and each query must then be answered in O(1) time.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- `1 <= len(queries) <= 10^5`
- `0 <= l <= r < len(nums)` for every query
### Examples
**Example 1**
```text
Input: nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
queries = [[0, 2], [0, 3], [4, 7], [2, 8], [5, 5]]
Output: [True, False, True, False, True]
```
`nums[0..3]` contains `1` twice (indices 1 and 3), and `nums[2..8]` contains `5` twice (indices 4 and 8). The other three ranges have no repeated value.
**Example 2**
```text
Input: nums = [2, 2]
queries = [[0, 0], [0, 1], [1, 1]]
Output: [True, False, True]
```
Each single-element range is distinct, while the whole array repeats `2`.
Overview: Given an integer array and many index ranges, report for each range whether all of its elements are distinct, using preprocessing that lets every query be answered in constant time. It tests turning a per-range question into a per-index precomputation and weighing preprocessing cost against query cost.
Read the full Google Software Engineer interview experience this question came from
You are given an integer array `nums` and a list `queries`, where each query is a range `[l, r]` of 0-indexed, inclusive indices. For a single range, the question is whether the elements `nums[l], nums[l + 1], ..., nums[r]` are all distinct, that is, whether no value appears twice in the range.
Many different ranges are queried against the same array, so precompute information about `nums` once, with the best preprocessing time you can achieve, such that every query is then answered in O(1) time. The preprocessing may depend only on `nums`. Implement this extended version, `ranges_distinct(nums, queries)`, which receives all the queries at once.
**Output.** Return a list of booleans with exactly one answer per query, in the order of `queries` (a query that is listed several times gets an answer at each of its positions). The answer to a query `[l, r]` is `True` if no value occurs more than once among `nums[l..r]`, and `False` otherwise. A range with one element is always `True`.
Every value and index fits in a signed 32-bit integer (nothing exceeds 2^31 - 1 in magnitude), so a 32-bit `int` is sufficient in Java and C++.
**Example 1**
```text
Input: nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
queries = [[0, 2], [0, 3], [4, 7], [2, 8], [5, 5]]
Output: [True, False, True, False, True]
```
`nums[0..3]` contains `1` twice (indices 1 and 3), and `nums[2..8]` contains `5` twice (indices 4 and 8). The other three ranges have no repeated value.
**Example 2**
```text
Input: nums = [2, 2]
queries = [[0, 0], [0, 1], [1, 1]]
Output: [True, False, True]
```
Each single-element range is distinct, while the whole array repeats `2`.
**Constraints**
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- `1 <= len(queries) <= 10^5`
- `0 <= l <= r < len(nums)` for every query
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= len(queries) <= 10^5
- 0 <= l <= r < len(nums) for every query [l, r]
- Preprocessing may depend only on nums, and each query must then be answered in O(1) time
- Every value and index fits in a signed 32-bit integer
Examples
Input: ([7], [[0, 0]])
Expected Output: [True]
Explanation: Minimum valid input: one element and the single-element query [0, 0], which is always distinct.
Input: ([3, 1, 4, 1, 5, 9, 2, 6, 5], [[0, 2], [0, 3], [4, 7], [2, 8], [5, 5]])
Expected Output: [True, False, True, False, True]
Explanation: Source Example 1: 1 repeats at indices 1 and 3, and 5 repeats at indices 4 and 8.
Hints
- Check Example 1 by hand: for each False answer, find the two equal values inside the range and note where they sit relative to l and r.
- If a range contains a repeated value, every larger range that contains it does too, and a single-element range is always True.
- Values span -10^9 to 10^9, so treat them as arbitrary integers: x and -x are different values.