DEV Community

loading...

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

https://alkeshghorpade.me/post/geeks-for-geeks-pair-in-array-with-sum-equal-to-target

Discussion (2)

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

Collapse
_alkesh26 profile image
Alkesh Ghorpade Author

Hey thanks for the above solution. I have posted about this approach in my first blog
alkeshghorpade.me/post/leetcode-tw...