Maximize operations by removing target-sum pairs
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given an integer array nums and an integer T, in one operation you may remove two elements whose sum equals T. Return the maximum number of operations you can perform. Provide an algorithm with O(n) expected time using a hash map or O(n log n) time using sorting and two pointers, prove correctness, and discuss edge cases (duplicates, negatives, large values).
Quick Answer: This question evaluates a candidate's ability to design and analyze efficient array algorithms and use appropriate data structures and techniques such as hash maps or sorting with two-pointer strategies, with attention to time and space complexity.
Given an integer array `nums` and an integer `T`, in one operation you may remove two elements whose sum equals `T`. Each element can be used in at most one operation. Return the maximum number of operations you can perform.
The greedy claim is that pairing is unconstrained: any element equal to `x` can pair with any element equal to `T - x`, so for `x != T - x` the number of pairs is `min(count[x], count[T-x])`, and for `x == T - x` (i.e. `2x == T`) it is `count[x] // 2`. Aim for O(n) expected time with a hash map (or O(n log n) with sort + two pointers).
Edge cases to consider: duplicates, negative values, large values, an empty array, and when `T` is even so `x` pairs with itself.
Constraints
- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- -2*10^9 <= T <= 2*10^9
- Each element may be used in at most one operation
Examples
Input: ([1, 2, 3, 4], 5)
Expected Output: 2
Explanation: Pair (1,4) and (2,3), both sum to 5 — 2 operations.
Input: ([3, 1, 3, 4, 3], 6)
Expected Output: 1
Explanation: Three 3's pair with each other: 3+3=6 gives floor(3/2)=1 op. The leftover 3, 1, and 4 cannot form another sum of 6.
Hints
- Reorder the array freely — only the multiset of values matters, not their positions, because any two elements summing to T may be paired.
- Count the frequency of each value. For a value x, its partner is T - x.
- If x != T - x, the pairs you can form are limited by the scarcer of the two counts: min(count[x], count[T-x]). Visit each unordered pair {x, T-x} once (e.g. only when x < T-x) to avoid double counting.
- If x == T - x (this happens exactly when 2x == T), you pair the value with itself, giving count[x] // 2 pairs.
- Watch the self-pairing case: zeros with T = 0, or any value v with T = 2v.