Maximize disjoint k-sum pairs
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given an integer array nums and an integer k. In one operation you may remove two indices i < j if nums[i] + nums[j] == k; each index can be used at most once. Return the maximum number of operations you can perform. Design an O(n) or O(n log n) solution, discuss space–time trade-offs, and provide code in C, C++, Java, or JavaScript.
Quick Answer: This question evaluates proficiency in array algorithms, pairing logic, data structure selection, and complexity analysis, focusing on maximizing disjoint k-sum pairs and reasoning about space–time trade-offs.
You are given an integer array `nums` and an integer `k`. In one operation you may remove two indices i < j if `nums[i] + nums[j] == k`; each index can be used at most once. Return the maximum number of operations you can perform.
The order in which you pick pairs does not change the maximum count, so a single linear pass that greedily matches each value with a previously-seen complement is optimal. Maintain a count of unused values seen so far; for each new value `x`, if its complement `k - x` has an unused occurrence, pair them and increment the answer, otherwise record `x` as available.
Design an O(n) or O(n log n) solution and discuss the space–time trade-offs.
Constraints
- 1 <= nums.length (problem-level); the function must also handle nums.length == 0 by returning 0
- Values and k may be negative or zero
- Each index may participate in at most one operation
- 1 <= nums.length <= 10^5 (typical interview bound)
Examples
Input: ([1, 2, 3, 4], 5)
Expected Output: 2
Explanation: Pair (1,4) and (2,3), both summing to 5. Two operations, no index reused.
Input: ([3, 1, 3, 4, 3], 6)
Expected Output: 1
Explanation: Only 3+3 = 6 works; there are three 3's, so one pair is formed and the remaining 3, plus 1 and 4, cannot be paired.
Hints
- The maximum number of disjoint pairs is independent of pairing order, so a greedy single pass suffices — no backtracking is needed.
- Keep a hash map of unused values seen so far. For each value x, look up k - x; if an unused copy exists, consume it and count one operation, otherwise store x.
- Self-complement values (where x == k - x, e.g. x = k/2, or x = 0 with k = 0) just pair up among themselves naturally because the map count is decremented as you match.
- Sorting plus two pointers (one from each end moving toward a target sum) is an O(n log n) alternative with O(1) extra space — useful when memory is tight.