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

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

Comments

[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

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

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

[Alkesh Ghorpade]

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