Scale Engineer

Max Number of K-Sum Pairs

Med
#1540Time: O(n^2), where n is the number of elements in the array. The nested loops result in a quadratic number of comparisons in the worst case.Space: O(n), where n is the number of elements in the array. This space is used for the `used` boolean array to track which elements have been paired.1 company
Patterns
Two Pointers
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
DE Shaw

Prompt

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

 

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a brute-force method to find all possible pairs. It involves iterating through the array with two nested loops to check every unique pair of numbers. To prevent using the same number in multiple pairs, a boolean array is used to mark numbers that have been included in a pair.

Algorithm

  • Initialize operations to 0.
  • Create a boolean array used of the same size as nums, and initialize all its values to false.
  • Iterate through the nums array with an index i from 0 to n-1.
  • If used[i] is true, it means the number has already been paired, so we continue to the next element.
  • Inside the first loop, start a second, nested loop with an index j from i + 1 to n-1.
  • If used[j] is true, continue to the next element.
  • Check if nums[i] + nums[j] == k.
  • If the sum is equal to k, we have found a pair. Increment operations, set used[i] and used[j] to true, and break from the inner loop since nums[i] has now been used.
  • After the loops complete, return the total operations count.

Walkthrough

The core idea is to examine every possible pair of elements (nums[i], nums[j]) in the array. We use a primary loop to pick the first element nums[i] and a nested loop to pick the second element nums[j], ensuring j > i to avoid duplicate pairs and self-pairing.

To handle the constraint that each number can only be used once, we maintain a boolean array used of the same size as nums. When we find a pair (nums[i], nums[j]) that sums to k, and neither element has been used before (i.e., used[i] and used[j] are both false), we increment our operation count and set both used[i] and used[j] to true. We then break the inner loop for the current i because nums[i] is now part of a pair and cannot be used again.

import java.util.Arrays; class Solution {    public int maxOperations(int[] nums, int k) {        int operations = 0;        int n = nums.length;        boolean[] used = new boolean[n];                for (int i = 0; i < n; i++) {            if (used[i]) {                continue;            }            for (int j = i + 1; j < n; j++) {                if (used[j]) {                    continue;                }                if (nums[i] + nums[j] == k) {                    operations++;                    used[i] = true;                    used[j] = true;                    break; // Move to the next i since nums[i] is now used                }            }        }        return operations;    }}

Complexity

Time

O(n^2), where n is the number of elements in the array. The nested loops result in a quadratic number of comparisons in the worst case.

Space

O(n), where n is the number of elements in the array. This space is used for the `used` boolean array to track which elements have been paired.

Trade-offs

Pros

  • Simple to understand and implement.

  • Works correctly for small input sizes.

Cons

  • Extremely inefficient for large arrays, likely resulting in a 'Time Limit Exceeded' error on competitive programming platforms.

Solutions

class Solution {public  int maxOperations(int[] nums, int k) {    Arrays.sort(nums);    int l = 0, r = nums.length - 1;    int ans = 0;    while (l < r) {      int s = nums[l] + nums[r];      if (s == k) {        ++ans;        ++l;        --r;      } else if (s > k) {        --r;      } else {        ++l;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem