Find All Index Quadruples Summing to a Target 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. The interviewer asked for the most efficient approach you can find, so aim to do better than examining every quadruple of indices.

Function Signature

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

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

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

Input:  nums = [1, 2, 3], target = 6
Output: []

The array has fewer than four elements.

All Index Quadruples With a Given Sum

Hints

1. Answers are identified by position: equal values at different indices form separate quadruples, so never merge answers by value.
2. Every input value fits in a 32-bit integer, but a sum of four of them may not; keep sums in 64-bit arithmetic.
3. The output order is fixed by the statement: whatever order you find quadruples in, return them sorted ascending lexicographically by [i, j, k, l].

Approach

Split every quadruple i < j < k < l into a front pair (i, j) and a back pair (k, l), with j < k. Scan k from left to right while keeping a hash map from a pair sum to the list of front pairs (i, j) with i < j < k that have that sum. For each l > k, look up target - nums[k] - nums[l]: every pair in that bucket ends before k, so each one yields a valid quadruple (i, j, k, l). After all l for the current k are handled, insert the pairs (i, k) for every i < k, which restores the invariant for k + 1. Correctness: a valid quadruple is emitted when its back pair (k, l) is scanned, because its front pair was inserted at step j < k; each front pair is inserted exactly once and each back pair is scanned exactly once, so no quadruple is produced twice, and the bucket only ever holds pairs that end before k, so no index is reused. Discovery follows the back pair, not lexicographic order, so the collected quadruples are sorted lexicographically before returning. The lookup key target - nums[k] - nums[l] can reach 3 * 10^9 in magnitude and a four-element sum can reach 4 * 10^9, so fixed-width languages use 64-bit keys to avoid a wraparound false match. Edge cases: fewer than four elements return an empty list at once; equal values at different positions are kept as separate answers, so an all-equal array yields all C(n, 4) index sets.

• Time complexity: O(n^2 + R log R), where R <= 10^4 is the number of returned quadruples
• Space complexity: O(n^2 + R)