Find All Index Quadruples Summing to a Target Without Losing Positions
Company: Airwallex
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array `nums` and an integer `target`, return every quadruple of indices `(i, j, k, l)` with `i < j < k < l` such that `nums[i] + nums[j] + nums[k] + nums[l] == target`.
Answers are identified by position, not by value: indices refer to the original, unmodified array, and two quadruples that use equal values at different positions are different answers. The interviewer asked for the most efficient approach you can find, so aim to do better than examining every quadruple of indices.
### Function Signature
```python
def index_quadruples_with_sum(nums: list[int], target: int) -> list[list[int]]:
```
### Rules
- Each quadruple is returned as a list `[i, j, k, l]` of four distinct indices in strictly increasing order.
- Every valid quadruple appears exactly once.
- The outer list is sorted in ascending lexicographic order.
- Return an empty list if no quadruple exists, including when `len(nums) < 4`.
### Constraints
- `1 <= len(nums) <= 200`
- `-10^9 <= nums[i] <= 10^9`
- `-10^9 <= target <= 10^9`
- A sum of four elements can reach `4 * 10^9` in absolute value, which exceeds `2^31 - 1`; use 64-bit arithmetic in fixed-width languages. All values stay within `2^53`.
- The number of valid quadruples is at most `10^4`.
### Examples
**Example 1**
```text
Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[0, 1, 2, 3], [0, 2, 4, 5], [1, 3, 4, 5]]
```
The values are `1 + 0 + (-1) + 0`, `1 + (-1) + (-2) + 2` and `0 + 0 + (-2) + 2`, all equal to 0.
**Example 2**
```text
Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[0, 1, 2, 3], [0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 3, 4], [1, 2, 3, 4]]
```
Every choice of four of the five positions sums to 8. The values are identical, but the index sets differ, so all five are separate answers.
**Example 3**
```text
Input: nums = [1, 2, 3], target = 6
Output: []
```
The array has fewer than four elements.
Overview: Given an integer array and a target, return every quadruple of original indices i < j < k < l whose values sum to the target, in lexicographic order. Tests an efficient search beyond brute force, index-based deduplication, overflow awareness and handling of repeated values without losing positions.
Given an integer array `nums` and an integer `target`, return every quadruple of indices `(i, j, k, l)` with `i < j < k < l` such that `nums[i] + nums[j] + nums[k] + nums[l] == target`.
Answers are identified by position, not by value: indices refer to the original, unmodified array, and two quadruples that use equal values at different positions are different answers. Aim for an approach that does better than examining every quadruple of indices.
**Output rules**
- Each quadruple is returned as a list `[i, j, k, l]` of four distinct indices in strictly increasing order.
- Every valid quadruple appears exactly once.
- The outer list is sorted in ascending lexicographic order.
- Return an empty list if no quadruple exists, including when `len(nums) < 4`.
**Constraints**
- `1 <= len(nums) <= 200`
- `-10^9 <= nums[i] <= 10^9`
- `-10^9 <= target <= 10^9`
- Every input value fits in a 32-bit signed integer, but a sum of four elements can reach `4 * 10^9` in absolute value, which exceeds `2^31 - 1`; use 64-bit arithmetic for sums (`long` in Java, `long long` in C++). All values stay within `2^53`.
- The number of valid quadruples is at most `10^4`.
**Example 1**
```text
Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[0, 1, 2, 3], [0, 2, 4, 5], [1, 3, 4, 5]]
```
The values are `1 + 0 + (-1) + 0`, `1 + (-1) + (-2) + 2` and `0 + 0 + (-2) + 2`, all equal to 0.
**Example 2**
```text
Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[0, 1, 2, 3], [0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 3, 4], [1, 2, 3, 4]]
```
Every choice of four of the five positions sums to 8. The values are identical, but the index sets differ, so all five are separate answers.
Constraints
- 1 <= len(nums) <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- A sum of four elements can reach 4 * 10^9 in absolute value, which exceeds 2^31 - 1; use 64-bit arithmetic for sums (long in Java, long long in C++). All values stay within 2^53.
- The number of valid quadruples is at most 10^4.
Examples
Input: ([5], 5)
Expected Output: []
Explanation: A single element cannot form a quadruple.
Input: ([1, 2, 3], 6)
Expected Output: []
Explanation: Three elements are fewer than four, so the result is empty even though all of them sum to target.
Hints
- Answers are identified by position: equal values at different indices form separate quadruples, so never merge answers by value.
- Every input value fits in a 32-bit integer, but a sum of four of them may not; keep sums in 64-bit arithmetic.
- The output order is fixed by the statement: whatever order you find quadruples in, return them sorted ascending lexicographically by [i, j, k, l].