Find All Pairs In An Array That Sum To A Target Value In Ruby
Return every pair of distinct elements that add up to a target — a classic interview problem with an efficient hash-based O(n) solution.
Description
The naive approach checks every combination with combination(2) — O(n²). The efficient approach uses a hash (seen set): for each element, check if target - element has been seen; if yes, emit the pair. This runs in O(n).
combination(2) is cleaner for small arrays or when O(n²) is acceptable. The hash approach scales to large inputs without nested loops.
Both approaches return unique pairs. Sort the pair before storing to deduplicate [1, 4] vs [4, 1].
Sample input:
nums = [2, 7, 11, 4, 1, 5], target = 9
Sample Output:
[[2, 7], [4, 5]]
Answer
nums = [2, 7, 11, 4, 1, 5]
target = 9
# O(n) hash approach
def pairs_summing_to(nums, target)
seen = {}
pairs = []
nums.each do |n|
complement = target - n
if seen[complement]
pairs << [complement, n].sort
end
seen[n] = true
end
pairs.uniq
end
pairs_summing_to(nums, target)
# => [[2, 7], [4, 5]]
# O(n²) — clean for small inputs
nums.combination(2).select { |a, b| a + b == target }
# => [[2, 7], [4, 5]]
# With duplicates allowed (indices differ but values same)
[3, 3, 6].combination(2).select { |a, b| a + b == 6 }
# => [[3, 3]]
Check viewARU - Brand Newsletter!
Newsletter to DEVs by DEVs - boost your Personal Brand & career! 🚀
