How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find Unique Target-Sum Pairs | Amazon Coding Question

Find Unique Target-Sum Pairs

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given an integer array `nums` and an integer `target`, return all unique pairs of values whose sum equals `target`. Requirements: - Each returned pair should be sorted in nondecreasing order, for example `[2, 5]` instead of `[5, 2]`. - The output must not contain duplicate pairs, even if the input contains duplicate values. - The order of pairs in the output does not matter. - The array may contain negative numbers, zero, positive numbers, and duplicates. Example: - Input: `nums = [1, 3, 2, 2, 3, 4, -1, 5]`, `target = 5` - Output: `[[-1, 6], [1, 4], [2, 3]]` would be valid if `6` were present; for the given input, a valid output is `[[1, 4], [2, 3]]`. Interview tasks: 1. Explain your approach. 2. Implement a complete solution in Python. 3. Dry run the solution on a test case. 4. List unit test cases you would write. 5. Identify a test case that a naive or flawed solution may fail. 6. Follow-up: how would you modify the approach to return all unique triplets of values whose sum equals `target`? 7. Analyze the time and space complexity for both the pair and triplet versions.

Quick Answer: This question evaluates array-processing skills, correctness in handling duplicate values, and the ability to identify unique value pairs whose sums meet a numeric constraint, with attention to edge cases and result deduplication.

Part 1: Find All Unique Target-Sum Pairs

Given an integer array nums and an integer target, return all unique pairs of values whose sum equals target. Each pair must be sorted in nondecreasing order, and the final list of pairs must be sorted lexicographically for deterministic output. Do not include duplicate pairs, even if nums contains duplicate values.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Examples

Input: ([1, 2, 3, 4, 2, 3], 5)

Expected Output: [[1, 4], [2, 3]]

Explanation: The pairs that sum to 5 are (1,4) and (2,3). Even though 2 and 3 appear multiple times, [2, 3] is included only once.

Input: ([2, 2, 2, 2], 4)

Expected Output: [[2, 2]]

Explanation: There are many index combinations, but only one unique value pair: [2, 2].

Input: ([], 7)

Expected Output: []

Explanation: An empty array has no pairs.

Input: ([-2, -1, 0, 1, 2, 3], 1)

Expected Output: [[-2, 3], [-1, 2], [0, 1]]

Explanation: These are all unique pairs whose sums equal 1, already sorted lexicographically.

Input: ([5], 5)

Expected Output: []

Explanation: A single element cannot form a pair.

Hints

Sort the array first. Then compare the sum of the leftmost and rightmost values to the target.
When you find a valid pair, skip over repeated values on both sides so the same pair is not added again.

Part 2: Find All Unique Target-Sum Triplets

Given an integer array nums and an integer target, return all unique triplets of values whose sum equals target. Each triplet must be sorted in nondecreasing order, and the final list of triplets must be sorted lexicographically for deterministic output. Do not include duplicate triplets, even if nums contains duplicate values.

Constraints

0 <= len(nums) <= 3000
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Examples

Input: ([-1, 0, 1, 2, -1, -4], 0)

Expected Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: The only unique triplets summing to 0 are [-1, -1, 2] and [-1, 0, 1].

Input: ([0, 0, 0, 0], 0)

Expected Output: [[0, 0, 0]]

Explanation: Although there are multiple ways to pick three zeroes, they all form the same triplet [0, 0, 0].

Input: ([1, 2, 3, 4], 50)

Expected Output: []

Explanation: No three values sum to 50.

Input: ([], 0)

Expected Output: []

Explanation: An empty array cannot contain any triplet.

Input: ([1, 1, 2, 2, 3, 3, 4], 8)

Expected Output: [[1, 3, 4], [2, 2, 4], [2, 3, 3]]

Explanation: The unique triplets that sum to 8 are [1, 3, 4], [2, 2, 4], and [2, 3, 3].

Hints

Sort the array and fix one value at a time. For the remaining part of the array, use two pointers to find complementary pairs.
To avoid duplicate triplets, skip repeated values both for the fixed index and after finding a valid triplet.

Quick Overview

This question evaluates array-processing skills, correctness in handling duplicate values, and the ability to identify unique value pairs whose sums meet a numeric constraint, with attention to edge cases and result deduplication.