Frontend School

Count Unique Pairs for Target Sum

DSA
easy

Count Unique Pairs for Target Sum

Easy
Arrays
Hashing

Overview

In many data analysis scenarios, identifying specific relationships between data points is crucial. Imagine you're processing transaction logs or analyzing product compatibility. You might need to find all distinct pairs of items that, when combined, meet a certain target value. This problem challenges you to efficiently count such unique pairs within a given dataset.

What you need to do / Task

Given an array of integers nums and a target integer target, your task is to find the number of unique pairs (a, b) from nums such that a + b == target. A pair (a, b) is considered unique if the set of values {a, b} is distinct. For example, if nums = [1, 2, 1] and target = 3, the pair (1, 2) should only be counted once, even though 1 appears twice.

Deliverables:

  1. Implement a function countUniquePairs that takes nums and target as input.
  2. The function should return an integer representing the total count of unique value pairs that sum up to target.
  3. Ensure your solution handles duplicate numbers within nums correctly, counting each distinct value pair only once.

Input & output

  • Input:
    • nums: An array of integers. This array can contain positive, negative, or zero values, and may include duplicates.
    • target: An integer representing the sum we are looking for.
  • Output:
    • An integer, the count of unique pairs (a, b) from nums such that a + b == target.

Clarifications

  • Empty or single-element array: If nums is empty or contains only one element, no pairs can be formed, so the function should return 0.
  • Self-pairing: A number cannot pair with itself at the same index. However, if the array contains two distinct instances of the same value (e.g., nums = [2, 2, 4] and target = 4), then (2, 2) would form one unique pair. This means a and b in a + b = target refer to values, not necessarily distinct indices, but a and b must come from the nums array.
  • Order of pair elements: The order of elements in a pair does not matter. {a, b} is the same as {b, a}. The count should reflect this uniqueness (e.g., (1, 2) and (2, 1) are considered the same unique pair).

Examples

1

Example 1

Input:

nums = [1, 5, 3, 4, 2], target = 6

Output:

2

Note:

The unique pairs that sum to 6 are (1, 5) and (2, 4). The pair (3, 3) is not possible as 3 appears only once.

2

Example 2

Input:

nums = [1, 1, 2, 2], target = 3

Output:

1

Note:

The only unique pair that sums to 3 is (1, 2). Even though there are multiple ways to pick 1 and 2 from the array by index, the value pair {1, 2} is counted only once.

3

Example 3

Input:

nums = [0, 0, 0, 0], target = 0

Output:

1

Note:

The unique pair that sums to 0 is (0, 0). Since 0 appears multiple times, this pair is valid and counted once.

4

Example 4

Input:

nums = [-1, 0, 1, 2, -1], target = 0

Output:

2

Note:

The unique pairs are (-1, 1) and (0, 0). Note that -1 appears twice, but we only need one instance of each value for (-1,1) and 0 appears once so (0,0) is not possible unless 0 appears twice.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i], target <= 10^9
  • The solution should aim for optimal time and space complexity.

What interviewers evaluate

  • Correctness: The algorithm correctly identifies and counts all unique pairs for various inputs, including edge cases like duplicates, negative numbers, and target sums formed by identical numbers.
  • Efficiency: The solution demonstrates an understanding of time and space complexity, achieving an optimal or near-optimal solution (e.g., O(N) time complexity).
  • Code Quality: The code is clean, readable, well-structured, and uses appropriate data structures.
  • Problem-solving: Ability to break down the problem, choose an appropriate data structure (like hash maps/sets), and handle specific requirements like unique pair counting.

Loading editor...