Question Bank
JavaScript Pair-Sum Finder: Two Approaches Quiz
Difficulty: Medium
Two seeded ways to test whether two numbers in an array add up to a target (nested loop and Set complement), plus two companions on time complexity and on returning the actual pair instead of a boolean.
JavaScript Pair-Sum Finder: Two Approaches Quiz
Two seeded ways to test whether two numbers in an array add up to a target (nested loop and Set complement), plus two companions on time complexity and on returning the actual pair instead of a boolean.
1,147 views
35
Implement sumFinder(arr, target) with a nested loop that returns true if any two distinct indices in arr sum to target, otherwise false.
Examples
Example 1:
Input: sumFinder([2, 3, 6, 1, 4, 5], 9)
Output: true
Explanation: 3 + 6 = 9 and 4 + 5 = 9, so the function returns true on the first matching pair.Implement sumFinder(arr, target) in O(n) time using a Set that stores the complements of values you have already seen.
Examples
Example 1:
Input: sumFinder([2, 3, 6, 1, 4, 5], 9)
Output: true
Explanation: when 5 is read, the complement 4 has already been inserted from a previous iteration, so the pair is detected immediately.Compare the asymptotic time and space of the nested-loop pair-sum finder against the Set-based finder, and explain when each is the right tool.
Examples
Example 1:
Input: arr of length n
Output:
nested loop: O(n^2) time, O(1) extra space
set-based: O(n) time, O(n) extra space
Explanation: trade memory for speed when n is large; pick the loop when n is tiny or memory is tight.Adapt the Set-based scanner so it returns the actual pair as a tuple [a, b] (in scan order) when a match exists, or null otherwise.
Examples
Example 1:
Input: findPair([2, 4, 1, 5], 9)
Output: [4, 5]
Explanation: When 5 is read, the complement 4 is already in the Set from an earlier iteration; the function short-circuits and returns the pair in scan order.