Max Number of K-Sum Pairs – LeetCode Solution in Java

Problem Overview

Given an integer array nums and an integer k, find the maximum number of pairs whose sum equals k.

Each array element can be used in at most one pair. Once an element is paired, it cannot be used again.

Example 1

Input:

nums = [1, 2, 3, 4]
k = 5

Output:

2

Explanation:

We can form two pairs:

• (1, 4) → sum = 5

• (2, 3) → sum = 5

Therefore, the maximum number of pairs is 2.

Example 2

Input:

nums = [3, 1, 3, 4, 3]
k = 6

Output:

1

Explanation:

We can form only one pair (3, 3). Although the array contains three occurrences of 3, each occurrence can be used only once, and the value 3 requires another 3 to form a valid pair.

Approach 1: Brute Force

Intuition

The simplest approach is to select each element and check whether another element can form a pair with it whose sum equals k.

We use two nested loops:

• The outer loop selects the first element.

• The inner loop searches for a matching second element.

When a valid pair is found, we increment the count and mark both elements as used.

Java Solution

class Solution {
    public int maxOperations(int[] nums, int k) {
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            }

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] != 0 && nums[i] + nums[j] == k) {
                    count++;
                    nums[i] = 0;
                    nums[j] = 0;
                    break;
                }
            }
        }

        return count;
    }
}

Note: Using 0 as a marker is unsafe when zero is a valid input value. A separate boolean[] used array is a safer implementation of this brute-force approach.

Complexity Analysis

• Time Complexity: O(n²) because each element may be compared with the remaining elements.

• Space Complexity: O(1) for the marker-based version, excluding the input array.

This approach is easy to understand but may result in Time Limit Exceeded for large inputs.

Approach 2: HashMap – Two Passes

Intuition

Instead of searching the entire array for every element, we can use a HashMap to store the frequency of each number.

For a current number x, its required complement is:

complement = k - x

If the complement exists, we can form a pair. Since duplicate values are possible, we must track frequencies rather than simply storing whether a number exists.

Algorithm

1. Build a frequency map of all elements.

2. Iterate through the array.

3. Find the complement k - current.

4. If both required elements are available, form a pair and reduce their frequencies.

5. Count every valid pair and return the total.

Java Solution

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int count = 0;

        for (int num : nums) {
            int complement = k - num;

            if (map.getOrDefault(num, 0) > 0 &&
                map.getOrDefault(complement, 0) > 0) {

                if (num == complement &&
                    map.get(num) < 2) {
                    continue;
                }

                count++;

                map.put(num, map.get(num) - 1);
                map.put(complement,
                        map.get(complement) - 1);
            }
        }

        return count;
    }
}

Complexity Analysis

• Time Complexity: O(n) on average, assuming constant-time HashMap operations.

• Space Complexity: O(n) because the map may store every distinct element.

Approach 3: HashMap – Single Pass
Intuition

We can improve the previous approach by building the map and finding pairs simultaneously.

For each element:

1. Calculate its complement: k - current.

2. If the complement is already in the map, we have found a pair. Remove one occurrence of the complement.

3. Otherwise, store the current element for a possible future pair.

The map contains only elements that have not yet been paired.

Java Solution

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;

        for (int num : nums) {
            int complement = k - num;

            if (map.getOrDefault(complement, 0) > 0) {
                map.put(complement,
                        map.get(complement) - 1);
                count++;
            } else {
                map.put(num,
                        map.getOrDefault(num, 0) + 1);
            }
        }

        return count;
    }
}

Dry Run

Consider:

nums = [3, 1, 3, 4, 3, 2, 4]
k = 6

Current	Complement	Action	Count
3	3	Store 3	0
1	5	Store 1	0
3	3	Pair with previous 3	1
4	2	Store 4	1
3	3	Store 3	1
2	4	Pair with previous 4	2
4	2	Store 4	2

Output:

2

Complexity Analysis

• Time Complexity: O(n) on average.

• Space Complexity: O(n) in the worst case.

This is an efficient solution when you want to avoid sorting the array.

Approach 4: Sorting and Two Pointers

Intuition

Another efficient approach is to sort the array and use two pointers.

• left points to the smallest remaining element.

• right points to the largest remaining element.

Calculate their sum:

• If the sum is less than k, increment left to obtain a larger sum.

• If the sum is greater than k, decrement right to obtain a smaller sum.

• If the sum equals k, we have found a pair. Increment left, decrement right, and increase the count.

Because each element is used at most once, both pointers move inward after a valid pair is found.

Java Solution

import java.util.Arrays;

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);

        int left = 0;
        int right = nums.length - 1;
        int count = 0;

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum < k) {
                left++;
            } else if (sum > k) {
                right--;
            } else {
                count++;
                left++;
                right--;
            }
        }

        return count;
    }
}

Dry Run

Input:

nums = [3, 1, 9, 3, 2, 2, 4]
k = 6

After sorting:

nums = [1, 2, 2, 3, 3, 4, 9]

Left value	Right value	Sum	Action
1	9	10	Move right left
1	4	5	Move left right
2	4	6	Pair found
2	3	5	Move left right
3	3	6	Pair found

Output:

2

Complexity Analysis

• Time Complexity: O(n log n) because sorting takes O(n log n) and the two-pointer traversal takes O(n).

• Space Complexity: The auxiliary space depends on the sorting implementation. For Java primitive arrays, Arrays.sort(int[]) uses an in-place Dual-Pivot Quicksort implementation; its stack space is typically O(log n).

Comparing All Approaches

Approach	Time Complexity	Extra Space
Brute Force	O(n²)	O(1) with a safe marker strategy
HashMap – Two Pass	O(n) average	O(n)
HashMap – Single Pass	O(n) average	O(n)
Sorting + Two Pointers	O(n log n)	Sorting-dependent

Which Approach Should You Choose?

For this problem, the single-pass HashMap approach is an excellent choice when average linear time is the priority.

The sorting and two-pointer approach is also a strong option when you want to avoid an additional frequency map, provided modifying the array by sorting it is acceptable.

Key Takeaways

• A pair must use two distinct array elements.

• Each element can participate in only one pair.

• A complement is calculated as k - current.

• A HashMap helps find complements efficiently.

• A single-pass HashMap approach combines searching and frequency tracking.

• Sorting enables a two-pointer solution with O(n log n) overall time complexity.