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 Amazon.

What role is this question designed for?

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

Find all pairs summing to target in sorted array

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a non-decreasing array of integers nums and an integer target, return all unique pairs of indices (i, j) with i < j such that nums[i] + nums[j] == target. Use 0-based indices and list pairs in increasing order of i, then j. Each value may be used at most once per pair; if duplicates create the same value pair, include that pair only once. Aim for an O(n) two-pointer solution and analyze complexity.

Quick Answer: This question evaluates skills in array manipulation, handling duplicates, and algorithmic efficiency with attention to time and space complexity analysis.

Given a non-decreasing array of integers `nums` and an integer `target`, return all unique pairs of indices `(i, j)` with `i < j` such that `nums[i] + nums[j] == target`. Use 0-based indices and list pairs in increasing order of `i`, then `j`. Each value may be used at most once per pair; if duplicate values would create the same value pair, include that pair only once (return the first qualifying index pair for that value combination). Aim for an O(n) two-pointer solution and analyze the complexity. Example: - nums = [1, 1, 2, 2, 3, 3], target = 4 -> [[0, 5], [2, 3]] (value pairs (1,3) and (2,2), each counted once) - nums = [1, 2, 3, 4, 5], target = 6 -> [[0, 4], [1, 3]]

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9
Return index pairs [i, j] with i < j
Each distinct value-pair must appear at most once

Examples

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

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

Explanation: 1+5=6 -> [0,4]; 2+4=6 -> [1,3]; 3 alone (middle) cannot pair with itself.

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

Expected Output: [[0, 5], [2, 3]]

Explanation: Value pair (1,3) recorded once as [0,5]; value pair (2,2) recorded once as [2,3].

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

Expected Output: [[0, 3]]

Explanation: Only the (2,2) value pair exists; counted a single time.

Input: ([], 5)

Expected Output: []

Explanation: Empty array yields no pairs.

Input: ([5], 5)

Expected Output: []

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

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

Expected Output: []

Explanation: No two elements sum to 100.

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

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

Explanation: -3+4=1 -> [0,4]; -1+2=1 -> [1,3].

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

Expected Output: [[0, 2]]

Explanation: Value pair (0,0) recorded once as the outer index pair [0,2].

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

Expected Output: [[2, 3]]

Explanation: Only 4+4=8 from the two interior 4s, recorded once as [2,3].

Hints

Because the array is sorted, you can place one pointer at the start and one at the end and move them toward each other.
If the current sum is too small, advance the left pointer; if too large, retreat the right pointer; if equal, record the pair.
After recording a match, skip past all equal values on both sides so the same value combination is not recorded twice.

Quick Overview

This question evaluates skills in array manipulation, handling duplicates, and algorithmic efficiency with attention to time and space complexity analysis.