Pair with Given Sum

Solved

Difficulty: Easy Accuracy: — Submissions: 0 Points: 2

Given an array arr[] and an integer target, decide whether there are two different positions in the array whose values add up to target. Return true if such a pair exists and false otherwise.

Examples:

Input: arr[] = [0, -1, 2, -3, 1], target = -2

Output: true

Explanation: -3 + 1 = -2.

Input: arr[] = [1, -2, 1, 0, 5], target = 0

Output: false

Explanation: No two elements add up to 0.

Constraints:

1 ≤ arr.size() ≤ 10^5
-10^5 ≤ arr[i] ≤ 10^5
-10^5 ≤ target ≤ 10^5

Expected Complexities

Time Complexity: O(n) Auxiliary Space: O(n)

Company Tags

Amazon Flipkart Zoho

Topic Tags

Arrays Easy

For each element x you need to know whether target – x appeared earlier. A hash set answers that in constant time: check the set, then insert x. Checking before inserting guarantees the two elements come from different positions, which matters when target is exactly twice some value.

class Solution {
    public boolean hasPairWithSum(int[] arr, long target) {
        Set<Long> seen = new HashSet<>();
        for (int x : arr) {
            if (seen.contains(target - x)) return true;
            seen.add((long) x);
        }
        return false;
    }
}