Max Number of K-Sum Pairs solution and explanation
Google
TCS
9 more videos on this problem
Max Number of K-Sum Pairs | Live Coding with Explanation | Leetcode - 1679Algorithms Made Easy · 8:53 · 12K views
Leetcode - Max Number of K-Sum Pairs (Python)Timothy H Chang · 5:43 · 9K views
Max Number of K-Sum Pairs | Leetcode 1679 | leetcode solutionEasyLeetcode · 7:52 · 1K views
Max Number of K-Sum Pairs - Leetcode 1679 with step-by-step Explanation | PythonYaps World · 6:03 · 1K views
Max Number of K-Sum Pairs | Leetcode 1679 | Leetcode SolutionEasyLeetcode · 6:35 · 1K views
1679. Max Number of K-Sum Pairs (Leetcode Medium)Programming Live with Larry · 5:18 · 717 views
LeetCode 1679 | MaxNumber of K-Sum Pairs | JavaScript | Live CodingKun's Dev · 6:46 · 513 views
Leetcode 1679. Max Number of K-Sum Pairs | O(n) SolutionPlacement Corner · 7:51 · 512 views
💻Solving All LeetCode Problems with PYTHON 🐍 - 1679 Max Number of K-Sum PairsAlex Brou · 6:03 · 318 views
Max Number of K-Sum Pairs | LeetCode 1679 in C++ (Hash Map)LAN Academy · 4:02 · 318 views
The problem
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 <= 1051 <= nums[i] <= 1091 <= 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.
def maxOperations(nums, k):
count = {}
operations = 0
for num in nums:
complement = k - num
if count.get(complement, 0) > 0:
operations += 1
count[complement] -= 1
else:
count[num] = count.get(num, 0) + 1
return operations
# Example usage
nums = [1, 2, 3, 4]
k = 5
print(maxOperations(nums, k))import java.util.HashMap;
class Solution {
public int maxOperations(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int operations = 0;
for (int num : nums) {
int complement = k - num;
if (map.getOrDefault(complement, 0) > 0) {
operations++;
map.put(complement, map.get(complement) - 1);
} else {
map.put(num, map.getOrDefault(num, 0) + 1);
}
}
return operations;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
int k = 5;
System.out.println(sol.maxOperations(nums, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
int maxOperations(std::vector<int>& nums, int k) {
std::unordered_map<int, int> hashmap;
int operations = 0;
for (int num : nums) {
int complement = k - num;
if (hashmap[complement] > 0) {
operations++;
hashmap[complement]--;
} else {
hashmap[num]++;
}
}
return operations;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
int k = 5;
std::cout << maxOperations(nums, k) << std::endl;
return 0;
}function maxOperations(nums, k) {
let map = new Map();
let operations = 0;
for (let num of nums) {
let complement = k - num;
if (map.get(complement) > 0) {
operations++;
map.set(complement, map.get(complement) - 1);
} else {
map.set(num, (map.get(num) || 0) + 1);
}
}
return operations;
}
// Example Usage
let nums = [1, 2, 3, 4];
let k = 5;
console.log(maxOperations(nums, k));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
int maxOperations(int* nums, int numsSize, int k) {
int hash[MAX] = {0}, operations = 0;
for (int i = 0; i < numsSize; i++) {
int complement = k - nums[i];
if (complement >= 0 && hash[complement] > 0) {
operations++;
hash[complement]--;
} else {
hash[nums[i]]++;
}
}
return operations;
}
int main() {
int nums[] = {1, 2, 3, 4};
int size = sizeof(nums) / sizeof(nums[0]);
int k = 5;
printf("%d\n", maxOperations(nums, size, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxOperations(int[] nums, int k) {
Dictionary<int, int> map = new Dictionary<int, int>();
int operations = 0;
foreach (int num in nums) {
int complement = k - num;
if (map.ContainsKey(complement) && map[complement] > 0) {
operations++;
map[complement]--;
} else {
if (!map.ContainsKey(num)) map[num] = 0;
map[num]++;
}
}
return operations;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 4};
int k = 5;
Solution sol = new Solution();
Console.WriteLine(sol.MaxOperations(nums, k));
}
}The Python solution employs a dictionary to keep track of the number of times each complement is needed. It processes the array while adjusting the counts and tracking the number of operations.
Time Complexity: O(n) as it iteratively checks each element, with average constant-time operations for the dictionary.
Space Complexity: O(n), since the dictionary may store counts for up to n numbers.
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.
def maxOperations(nums, k):
nums.sort()
left, right = 0, len(nums) - 1
operations = 0
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == k:
operations += 1
left += 1
right -= 1
elif current_sum < k:
left += 1
else:
right -= 1
return operations
# Example usage
nums = [1, 2, 3, 4]
k = 5
print(maxOperations(nums, k))import java.util.Arrays;
class Solution {
public int maxOperations(int[] nums, int k) {
Arrays.sort(nums);
int operations = 0, left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
operations++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return operations;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
int k = 5;
System.out.println(sol.maxOperations(nums, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxOperations(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int operations = 0, left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
operations++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return operations;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
int k = 5;
std::cout << maxOperations(nums, k) << std::endl;
return 0;
}function maxOperations(nums, k) {
nums.sort((a, b) => a - b);
let left = 0, right = nums.length - 1;
let operations = 0;
while (left < right) {
let sum = nums[left] + nums[right];
if (sum === k) {
operations++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return operations;
}
// Example Usage
let nums = [1, 2, 3, 4];
k = 5;
console.log(maxOperations(nums, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int maxOperations(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
int left = 0, right = numsSize - 1, operations = 0;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
operations++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return operations;
}
int main() {
int nums[] = {1, 2, 3, 4};
int size = sizeof(nums) / sizeof(nums[0]);
int k = 5;
printf("%d\n", maxOperations(nums, size, k));
return 0;
}using System;
public class Solution {
public int MaxOperations(int[] nums, int k) {
Array.Sort(nums);
int operations = 0, left = 0, right = nums.Length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
operations++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return operations;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 4};
int k = 5;
Solution sol = new Solution();
Console.WriteLine(sol.MaxOperations(nums, k));
}
}Python's sorted inbuilt function is leveraged in this approach, maintaining scope for fast retrieval of pairs, followed by a classic two-pointer method for possible pair comprehension with reduced overhead.
Time Complexity: O(n log n) because sorting dominates the time complexity, while the two-pointer action runs in O(n).
Space Complexity: O(1), manipulating in-place only with auxiliary pointers involved.
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 isk. We increment the answer and then movelandrtowards the middle; - If
s > k, then we move therpointer to the left; - If
s < k, then we move thelpointer 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.
function maxOperations(nums: number[], k: number): number {
const cnt = new Map();
let ans = 0;
for (const x of nums) {
if (cnt.get(k - x)) {
cnt.set(k - x, cnt.get(k - x) - 1);
++ans;
} else {
cnt.set(x, (cnt.get(x) | 0) + 1);
}
}
return ans;
}func maxOperations(nums []int, k int) int {
sort.Ints(nums)
l, r, ans := 0, len(nums)-1, 0
for l < r {
s := nums[l] + nums[r]
if s == k {
ans++
l++
r--
} else if s > k {
r--
} else {
l++
}
}
return ans
}impl Solution {
pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
let mut nums = nums.clone();
nums.sort();
let (mut l, mut r, mut ans) = (0, nums.len() - 1, 0);
while l < r {
match nums[l] + nums[r] {
sum if sum == k => {
ans += 1;
l += 1;
r -= 1;
}
sum if sum > k => {
r -= 1;
}
_ => {
l += 1;
}
}
}
ans
}
}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.
func maxOperations(nums []int, k int) (ans int) {
cnt := map[int]int{}
for _, x := range nums {
if cnt[k-x] > 0 {
cnt[k-x]--
ans++
} else {
cnt[x]++
}
}
return
}impl Solution {
pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
let mut cnt = std::collections::HashMap::new();
let mut ans = 0;
for x in nums {
let m = k - x;
if let Some(v) = cnt.get_mut(&m) {
ans += 1;
*v -= 1;
if *v == 0 {
cnt.remove(&m);
}
} else if let Some(v) = cnt.get_mut(&x) {
*v += 1;
} else {
cnt.insert(x, 1);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using HashMap for Frequency Counting | Time Complexity: O(n) as it iteratively checks each element, with average constant-time operations for the dictionary. |
| Two Pointer Technique on Sorted Array | Time Complexity: O(n log n) because sorting dominates the time complexity, while the two-pointer action runs in O(n). |
| Sorting | – |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Frequency Counting | O(n) | O(n) | Best general solution for unsorted arrays and interview settings |
| Two Pointer on Sorted Array | O(n log n) | O(1) | Useful when array can be sorted or when minimizing extra memory |
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.