Determine If Two Numbers Sum to Target

Scenario

Live CodeShare Python/Java question during the same LendingClub interview assessing basic algorithmic fluency.

Question

Given an integer array nums and an integer target, return true if any two distinct numbers in nums sum to target; otherwise return false.

Hints

An O(n) hash-set solution is acceptable; explain trade-offs vs. sorting.

Determine If Two Numbers Sum to Target

Given an integer array nums and an integer target, return true if any two distinct elements (at different indices) in nums sum to target; otherwise return false.

Note: the two elements must be at different positions, but they may have equal values (e.g. nums = [3, 3], target = 6 returns true).

Example 1:

Input: nums = [2, 7, 11, 15], target = 9
Output: true   (2 + 7 = 9)

Example 2:

Input: nums = [1, 2, 3], target = 7
Output: false  (no pair sums to 7)

Example 3:

Input: nums = [3, 3], target = 6
Output: true   (the two 3s are at different indices)

An O(n) single-pass hash-set solution is expected; be ready to discuss the trade-off versus sorting then two-pointer (O(n log n) time, O(1) extra space if sorting in place).

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• -2 * 10^9 <= target <= 2 * 10^9
• The two chosen elements must be at different indices (but may have equal values).

Hints

1. Brute force checks every pair in O(n^2). Can you avoid re-scanning the array for each element?
2. As you iterate, for the current value x the partner you need is target - x. If you have already seen that partner, you have a valid pair.
3. Use a hash set of values seen so far. Check membership BEFORE inserting the current value so you never pair an element with itself.
4. Alternative: sort the array (O(n log n)) and use two pointers from both ends, moving inward based on the running sum — trades time for O(1) extra space.