Skip to main content
Talentd

Max Number of K-Sum Pairs - Solution & Explanation

MediumArrayHash TableTwo PointersSorting22 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer array and a target value k, you need to form the maximum number of pairs such that each pair sums to k. Every element can be used at most once, so once two numbers form a valid pair they are removed from further consideration.

Approach 1: HashMap Frequency Counting (O(n) time, O(n) space)

This approach scans the array once while storing frequencies in a hash map. For each number x, compute its complement k - x. If the complement already exists in the map with a positive count, you found a valid pair and decrease its frequency. Otherwise, store the current number in the map for future matches. The key insight is that hash lookups are O(1), allowing you to check complements instantly while iterating the array only once. This method works for any unsorted input and is usually the expected optimal solution in interviews. It relies on the efficiency of a hash table combined with a single pass through the array.

Approach 2: Two Pointer Technique on Sorted Array (O(n log n) time, O(1) space)

Another approach sorts the array first, then uses two pointers: one starting at the beginning and the other at the end. At each step, compute the sum of the two values. If the sum equals k, a valid pair is found and both pointers move inward. If the sum is smaller than k, move the left pointer forward to increase the sum. If the sum is larger than k, move the right pointer backward to decrease it. Sorting takes O(n log n) time, but the two-pointer scan itself runs in O(n). This technique is common in problems involving pair sums and demonstrates mastery of the two pointers pattern combined with sorting.

Recommended for interviews: The HashMap approach is typically preferred because it achieves O(n) time without sorting and clearly demonstrates efficient use of a hash-based lookup. The two-pointer solution is also valuable because it shows understanding of sorted array techniques. Explaining both approaches signals strong problem-solving range: hash maps for optimal lookup and pointer techniques for space-efficient scanning.

Approach 1: Using HashMap for Frequency Counting

This approach involves using a hashmap to store the frequency of each number in the array. For each number in the array, check if the complement (k - current number) exists in the hashmap. If it does, form a pair and decrease the frequency of both the current number and its complement in the hashmap. This ensures that no number is reused in forming pairs, optimizing the number of operations possible.

The C solution utilizes a fixed-size array to simulate a hashmap because the constraints allow it. It iterates over all elements while checking if the complement needed to make up k exists in the hashmap. If it does, a pair is formed, and the operations count is increased.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because it involves a single pass through the array and constant-time operations for the hash table.
Space Complexity: O(n) to store the counts in the hash map.

Try this approach in the editor →

Approach 2: Two Pointer Technique on Sorted Array

First sort the array, which allows the use of a two-pointer technique to find pairs. One pointer starts at the beginning and the other at the end of the sorted array. If the sum of the elements at these pointers equals k, increase the operations count and move both pointers. If the sum is less than k, move the left pointer to increase the sum, otherwise, move the right pointer to decrease the sum, thus efficiently finding all possible pairs.

This C solution first sorts the array and then applies a two-pointer technique to count the number of k-sum pairs efficiently, adjusting pointers based on their summed value relative to k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, with a subsequent O(n) linear traversal using two pointers.
Space Complexity: O(1) for the additional pointers only.

Try this approach in the editor →

Approach 3: Sorting

We sort nums. Then l and r point to the first and last elements of nums respectively, and we compare the sum s of the two integers with k.

  • If s = k, it means that we have found two integers whose sum is k. We increment the answer and then move l and r towards the middle;
  • If s > k, then we move the r pointer to the left;
  • If s < k, then we move the l pointer to the right;
  • We continue the loop until l geq r.

After the loop ends, we return the answer.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Hash Table

We use a hash table cnt to record the current remaining integers and their occurrence counts.

We iterate over nums. For the current integer x, we check if k - x is in cnt. If it exists, it means that we have found two integers whose sum is k. We increment the answer and then decrement the occurrence count of k - x; otherwise, we increment the occurrence count of x.

After the iteration ends, we return the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of nums.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using HashMap for Frequency Counting

Time Complexity: O(n) because it involves a single pass through the array and constant-time operations for the hash table.
Space Complexity: O(n) to store the counts in the hash map.

Two Pointer Technique on Sorted Array

Time Complexity: O(n log n) due to sorting, with a subsequent O(n) linear traversal using two pointers.
Space Complexity: O(1) for the additional pointers only.

Sorting—
Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap Frequency CountingO(n)O(n)Best general solution for unsorted arrays and interview settings
Two Pointer on Sorted ArrayO(n log n)O(1)Useful when array can be sorted or when minimizing extra memory

Video Solution

Max Number of K-Sum Pairs | Live Coding with Explanation | Leetcode - 1679 • Algorithms Made Easy • 12,526 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Number of K-Sum Pairs easy or hard?
The problem is generally categorized as Medium difficulty. The core idea is straightforward once you recognize the complement pattern, but identifying the optimal O(n) HashMap strategy or the sorted two-pointer alternative requires familiarity with common array interview patterns.
Max Number of K-Sum Pairs Python/Java solution
Python and Java solutions typically implement the HashMap frequency method. Python uses a dictionary for constant-time lookups, while Java commonly uses HashMap<Integer, Integer>. Both implementations achieve O(n) time and O(n) space complexity.
How to solve Max Number of K-Sum Pairs in O(n)?
Use a HashMap to store counts of numbers seen so far. While iterating through the array, compute the complement k - x for each element. If the complement exists with a positive count, form a pair and decrease its frequency; otherwise store the current number. This guarantees a single pass with O(n) time.
What is the best approach for Max Number of K-Sum Pairs?
The most efficient approach uses a HashMap to track frequencies of numbers while scanning the array. For each value x, check if the complement k - x already exists in the map. This method runs in O(n) time with O(n) space and avoids the need to sort the array.
Is Max Number of K-Sum Pairs asked at Google/Amazon/Meta?
Pair-sum problems and hash-map complement patterns are frequently asked in interviews at companies like Amazon, Meta, and Google. Variations such as Two Sum, K-Sum, and pair counting problems are common because they test array processing and hash table usage.
What data structure is used in Max Number of K-Sum Pairs?
The optimal approach relies on a HashMap (or dictionary) to store frequencies of elements. Another common technique uses the two-pointer pattern after sorting the array, which avoids extra memory but increases time complexity due to sorting.
What is the time complexity of Max Number of K-Sum Pairs?
The optimal solution runs in O(n) time using a HashMap for constant-time complement lookups. A sorting-based solution using two pointers runs in O(n log n) time due to the sorting step, followed by an O(n) scan.

Ready to solve this problem?

Practice Max Number of K-Sum Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Good Meals

Next

Divide Players Into Teams of Equal Skill