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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Citadel during technical interviews.

Implement two-pointer unique-pair sum search

Quick Overview

Implement two-pointer unique-pair sum search evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Citadel

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a nondecreasing integer array nums and an integer target, return all unique value pairs [a, b] with a <= b such that a + b == target. Use the two-pointer technique to achieve O(n) time and O( 1) extra space beyond the output, and ensure duplicates in nums do not produce duplicate pairs. Additionally: a) Describe how you would return indices instead of values and any implications for stability. b) Explain how you would adapt the method if nums arrives as a stream that cannot be fully stored in memory. c) Analyze time and space complexity.

Quick Answer: Implement two-pointer unique-pair sum search evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a **nondecreasing** integer array `nums` and an integer `target`, return all **unique value pairs** `[a, b]` with `a <= b` such that `a + b == target`. Because `nums` is already sorted, use the **two-pointer technique** (one pointer from each end) to achieve **O(n)** time and **O(1)** extra space beyond the output array. Duplicate values in `nums` must **not** produce duplicate pairs in the result. Return the pairs in order of increasing `a` (which falls out naturally from a single left-to-right/right-to-left sweep). **Example 1** ``` nums = [1, 2, 3, 4, 5, 6], target = 7 => [[1, 6], [2, 5], [3, 4]] ``` **Example 2** ``` nums = [1, 1, 2, 2, 3, 3], target = 4 => [[1, 3], [2, 2]] ``` Even though `1` and `3` each appear twice, the pair `[1, 3]` is reported only once. **Follow-ups to think about (discussion only, not graded by the tests):** - **a)** How would you return *indices* instead of values, and what does that imply for stability when duplicates exist? (Returning indices makes the output sensitive to *which* duplicate you pick; you would typically fix it by always taking the first/last occurrence, but then the "unique pair" guarantee is about index pairs, not value pairs.) - **b)** How would you adapt the method if `nums` arrives as a stream too large to store? (The two-pointer trick needs random access to both ends, so a pure stream breaks it. You would fall back to a hash set of complements seen so far — O(n) time, O(n) space — or, if values fit a bounded range, a counting array. External sort + two-pointer is an option if you can buffer to disk.) - **c)** Analyze the time and space complexity of your two-pointer solution.

Constraints

0 <= len(nums) <= 10^5
nums is sorted in nondecreasing order
-10^9 <= nums[i], target <= 10^9
Each unique VALUE pair [a, b] with a <= b must appear at most once
Use O(1) extra space beyond the returned list (no hash set)

Examples

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

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

Explanation: Three pairs sum to 7; emitted in increasing order of the smaller element.

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

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

Explanation: Despite duplicate 1s and 3s, the value pair [1, 3] is reported once; [2, 2] uses two distinct equal elements.

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

Expected Output: [[2, 2]]

Explanation: All elements equal; only the single unique value pair [2, 2] is returned, not one per duplicate.

Input: ([], 5)

Expected Output: []

Explanation: Empty array — no pairs possible.

Input: ([3], 6)

Expected Output: []

Explanation: A single element cannot form a pair (need i < j).

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

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

Explanation: Works with negatives; the two-pointer logic is unchanged.

Input: ([1, 2, 3, 9, 10], 100)

Expected Output: []

Explanation: No pair reaches the target; pointers converge with no matches.

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

Expected Output: [[0, 0]]

Explanation: Target 0 with all zeros yields exactly one unique pair [0, 0].

Hints

Because the array is sorted, you don't need a hash set: start one pointer at the left end and one at the right end, and move them toward each other based on whether the current sum is too small or too large.
When nums[i] + nums[j] == target, record the pair, then skip over ALL duplicates of both nums[i] and nums[j] before continuing — this is what prevents duplicate value pairs.
If the sum is less than target, the only way to grow it is to move the left pointer right; if it's greater, move the right pointer left. The pointers never cross, giving O(n).

Quick Overview