Distinct Pair Sum Checker — Problem Statement & Solution Guide

HashingEasyTwo Sum / Hash Set

TimeO(n)

SpaceO(n)

Problem Description

You are provided with an array of integers named numbers and a target integer targetSum. Your goal is to evaluate whether there exists at least one pair of elements located at two distinct positions i and j (where i != j) such that their sum equals targetSum.

If such a pair exists within the array, return the string "YES". Otherwise, if no pair satisfies this condition, return "NO".

DSA Pattern Breakdown

"Distinct Pair Sum Checker"

easy

WHY DOES IT MATTER?

Detecting a pair with a given sum is a foundational pattern for membership queries, collision detection, and constraint satisfaction, appearing in everything from financial fraud checks to recommendation engines.

OPTIMIZATION CHALLENGE

The breakthrough is realizing you don’t need to compare every pair; by storing seen values you turn the problem into a constant‑time complement lookup, collapsing O(n²) to O(n).

REAL-WORLD CONNECTION

Think of a real‑time payment gateway that must instantly verify whether two pending transactions can offset each other to balance a ledger – a hash‑based lookup provides that constant‑time verification across a massive stream of events.

During an interview, write the hash‑set solution first, then mention the two‑pointer alternative for sorted data – it shows you understand trade‑offs between time, space, and input ordering.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The classic two‑sum problem asks whether any two distinct elements in a list add up to a given target. A naïve double‑loop checks every pair, leading to O(n²) time which quickly becomes infeasible for n in the millions because the number of comparisons grows quadratically. The optimal solution leverages hashing: as we scan the array we store each value in a hash set and simultaneously ask whether the complement (target‑value) has already been seen. This reduces the search for a matching partner to O(1) average time per element, yielding overall linear time. The hash‑based approach also naturally handles duplicate values and unordered input without needing to sort, preserving O(n) time while using O(n) extra space for the set.

Interview Questions on This Problem

Q1How would you modify the two‑sum solution to return the indices of the pair instead of just a yes/no answer?

Maintain a hash map from value to its index (or list of indices for duplicates); when you encounter a value, compute complement and check the map – if present, return the stored index and the current index.

Q2If the input array is sorted, can you solve the problem without extra space?

Yes, use the two‑pointer technique: start one pointer at the beginning and one at the end, move them inward based on the sum compared to the target, achieving O(1) space and O(n) time.

Q3In a distributed system where the array is sharded across multiple nodes, how can you detect a pair that spans shards?

Each node can emit its local hash set of values; a coordinator merges these sets (or uses a Bloom filter) and checks for cross‑shard complements, ensuring the overall complexity stays linear in the total data size.

Examples

Example 1

Input

numbers = [4, 7, 1, -2, 9], targetSum = 5

Output

YES

Explanation: The element at index 1 (7) and the element at index 3 (-2) sum up to 7 + (-2) = 5. Since indices 1 and 3 are distinct, the requirement is satisfied.

Example 2

Input

numbers = [10, 15, 3, 7], targetSum = 20

Output

NO

Explanation: The possible distinct pair sums are 25, 13, 17, 18, 22, and 10. None of these equal 20, so no valid pair exists.

Example 3

Input

numbers = [6, 6], targetSum = 12

Output

YES

Explanation: The array contains identical values at indices 0 and 1. Summing numbers[0] and numbers[1] yields 6 + 6 = 12. Because index 0 is not equal to index 1, the condition is met.

Example 4

Input

numbers = [8], targetSum = 8

Output

NO

Explanation: The array contains only a single element, making it impossible to select two distinct indices.

Constraints

1 <= numbers.length <= 10^5
-10^9 <= numbers[i] <= 10^9
-10^9 <= targetSum <= 10^9

Optimal Approach & Strategy

Iterate once through the array, for each element look up its complement in a hash set, and if not found, insert the element into the set; if a complement is found, return "YES" immediately.

Brute Force Approach

Check every possible pair with two nested loops and return "YES" if any sum matches the target, otherwise return "NO" after all pairs are examined.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++] || 0;
const numbers = data.slice(pos, pos + n);
pos += n;
const targetSum = data[pos] || 0;

function hasPairSum(numbers, targetSum) {
    const seen = new Set();
    for (const x of numbers) {
        const need = targetSum - x;
        if (seen.has(need)) return true;
        seen.add(x);
    }
    return false;
}

console.log(hasPairSum(numbers, targetSum) ? 'YES' : 'NO');

#include <bits/stdc++.h>
using namespace std;

bool hasPairSum(const vector<int>& numbers, int targetSum) {
    unordered_set<int> seen;
    for (int x : numbers) {
        int need = targetSum - x;
        if (seen.count(need)) return true;
        seen.insert(x);
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> numbers(n);
    for(int i=0;i<n;++i) cin>>numbers[i];
    int targetSum; cin>>targetSum;
    cout << (hasPairSum(numbers, targetSum) ? "YES" : "NO") << "\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static boolean hasPairSum(int[] numbers, int targetSum) {
        Set<Integer> seen = new HashSet<>();
        for (int x : numbers) {
            int need = targetSum - x;
            if (seen.contains(need)) return true;
            seen.add(x);
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if (line == null || line.isEmpty()) return;
        int n = Integer.parseInt(line.trim());
        int[] numbers = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        int targetSum = Integer.parseInt(br.readLine().trim());
        System.out.println(hasPairSum(numbers, targetSum) ? "YES" : "NO");
    }
}

import sys

def has_pair_sum(numbers, target_sum):
    seen = set()
    for x in numbers:
        if target_sum - x in seen:
            return True
        seen.add(x)
    return False

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    numbers = [int(next(it)) for _ in range(n)]
    target_sum = int(next(it))
    print('YES' if has_pair_sum(numbers, target_sum) else 'NO')

if __name__ == '__main__':
    main()

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++] || 0;
const numbers = data.slice(pos, pos + n);
pos += n;
const targetSum = data[pos] || 0;

function hasPairSum(numbers, targetSum) {
    const seen = new Set();
    for (const x of numbers) {
        const need = targetSum - x;
        if (seen.has(need)) return true;
        seen.add(x);
    }
    return false;
}

console.log(hasPairSum(numbers, targetSum) ? 'YES' : 'NO');

Asked in Top Tech Interviews

Infosys

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Distinct Pair Sum Checker Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Distinct Pair Sum Checker — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor