Two Sum - Pair with Given Sum

Time: O(n)

Space: O(n)

Intuition

Two pointers on sorted array: if sum < target, advance left; if sum > target, retreat right; if equal, found the pair. For unsorted, use a HashSet: for each element, check if (targetâˆ’element) is in the set.

Algorithm

1Sort arr. lo=0, hi=n-1.
2While lo < hi: sum=arr[lo]+arr[hi]. If sum==target: return true. If sum<target: lo++. Else: hi--.
3Return false.

Example Walkthrough

Input: arr=[2,7,11,15], target=9

1.lo=0(2), hi=3(15): 17>9â†’hi--. hi=2(11): 13>9â†’hi--. hi=1(7): 9==9 âœ“.

Output: true

Common Pitfalls

•Sorting changes indices â€” if you need to return original indices, use a HashMap approach instead.

Two Sum - Pair with Given Sum.java

Java

// Approach: HashSet approach: for each element check if (target - element) is in set.
// Time: O(n) Space: O(n)

class Solution {
    boolean twoSum(int arr[], int target) {
        HashMap<Integer, Integer> mm = new HashMap<>();
        for (int x : arr) {
            if (mm.get(target - x) != null)
                return true;
            mm.put(x, 1);
        }
        return false;
    }
}

Was this solution helpful?