Pair Sum Finder

Problem

Given an integer array nums and an integer target, return all unique pairs of indices [i, j] such that nums[i] + nums[j] == target and i < j.

The result should be returned as a list of pairs, where each pair is a list [i, j] with i < j. The pairs themselves should be sorted in ascending order by the first index, and if two pairs have the same first index, by the second index.

Input / Output Format

Input:

• nums: a list of integers (may contain duplicates)
• target: an integer representing the desired sum

Output:

• A list of [i, j] index pairs (sorted as described above)

Examples

Example 1

Input:  nums = [2, 7, 11, 15], target = 9
Output: [[0, 1]]

Explanation: nums[0] + nums[1] = 2 + 7 = 9. Only one pair exists.

Example 2

Input:  nums = [1, 3, 2, 4, 3, 2], target = 5
Output: [[0, 3], [1, 2], [1, 5], [2, 4], [3, 4]]

Explanation: Multiple valid index pairs sum to 5: (1+4), (3+2), (3+2), (2+3), (4+... wait — let's enumerate: indices (0,3)→1+4=5, (1,2)→3+2=5, (1,5)→3+2=5, (2,4)→2+3=5, (3,4)→4+... no. (3,4)→ not valid. Let me recalculate: nums=[1,3,2,4,3,2], indices giving sum 5: (0,3)=1+4, (1,2)=3+2, (1,5)=3+2, (2,4)=2+3.

Example 3

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

Explanation: No two elements sum to 10, so the result is an empty list.

Hints

• Brute force uses O(n²) time by checking every pair — acceptable, but can you do better?
• Consider using a hash map to store previously seen values and their indices, enabling an O(n) scan.
• Be careful with duplicate values: the same index must not be used twice, but two different indices with the same value are valid.
• Pay attention to the output ordering requirement.