DEV Community


Find a pair in an array with a sum equal to the target using sorting.

Alkesh Ghorpade
Ruby on Rails and Golang consultant
・1 min read

Discussion (2)

davidkroell profile image
David Kröll

Hi, nice solution you pointed out. I solved a similar problem back at AdventOfCode. I leveraged a HashMap to solve this problem in a time complexity of O(n), but slightly increased space complexity (given the array is already present and not to be computed or serialized from storage).

Given the following input:

Input: nums = {0, -1, 2, -3, 1}, target = -2
Enter fullscreen mode Exit fullscreen mode

Loop through the map and check if target - currentItem (since lookup is possible in constant time) exists also in the map -> sum found

Example (-3 is currentItem):
-2 - (-3) = -2 + 3 = 1
1 exists --> sum found
Enter fullscreen mode Exit fullscreen mode

Looping through whole map (worst case) sums up to a time complexity of O(n) as stated above.

_alkesh26 profile image
Alkesh Ghorpade Author

Hey thanks for the above solution. I have posted about this approach in my first blog