Skip to main content

Max Number of K-Sum Pairs (Leetcode)

Problem Description

Problem StatementSolution LinkLeetCode Profile
Max Number of K-Sum PairsMax Number of K-Sum Pairs Solution on LeetCodeAaradhya Singh

Problem Description

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

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

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

Examples

Example 1

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

Example 2

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

Constraints

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

Intuition

The code finds the maximum number of pairs in nums that sum to kk by first sorting the array and then using the two-pointer technique. Pointers start and end check pairs: if their sum equals kk, the count is incremented and both pointers move inward. If the sum is greater than kk, end moves left; if less, start moves right. This approach efficiently identifies pairs with a sum of kk in O(nlogn)O(nlog⁡n) time due to sorting and O(n)O(n) time for the two-pointer traversal.

Approach

  1. Sorting the Array:

    • The first step is to sort the given array nums using std::sort. This step ensures that elements are in ascending order, which is crucial for the two-pointer technique.
  2. Initializing Pointers and Count:

    • Initialize three variables: count to keep track of the number of valid pairs, start pointing to the beginning of the sorted array, and end pointing to the end of the array.
  3. Two-Pointer Technique:

    • Use the two-pointer technique within a while loop until start is less than end.
    • Check if the sum of elements at nums[start] and nums[end] equals the target value k.
      • If it does, increment count and move both pointers inward (start++ and end--).
      • If the sum is greater than k, decrement end to reduce the sum.
      • If the sum is less than k, increment start to increase the sum.
  4. Return Count:

    • After the while loop, return the final value of count, which represents the maximum number of pairs in nums that sum to k.

Solution Code

Python

class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
nums.sort() # Sort the array in ascending order
count = 0
start, end = 0, len(nums) - 1 # Initialize two pointers

while start < end:
if nums[start] + nums[end] == k:
count += 1
start += 1
end -= 1
elif nums[start] + nums[end] > k:
end -= 1
else:
start += 1

return count

Java

import java.util.Arrays;

class Solution {
public int maxOperations(int[] nums, int k) {
Arrays.sort(nums); // Sort the array in ascending order
int count = 0;
int start = 0, end = nums.length - 1; // Initialize two pointers

while (start < end) {
if (nums[start] + nums[end] == k) {
count++;
start++;
end--;
} else if (nums[start] + nums[end] > k) {
end--;
} else {
start++;
}
}

return count;
}
}

C++

class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
std::sort(nums.begin() , nums.end());
int count = 0;
int start = 0;
int end = nums.size() - 1;

while (start < end){
if (nums[start] + nums[end] == k){
count ++;
end--;
start++;
}
else if (nums[start] + nums[end] > k){
end--;
}
else{start++;}
}
return count;
}
};

Conclusion

The code effectively calculates the maximum number of pairs in an array nums that sum up to the given value kk using the two-pointer technique. It first sorts the array in ascending order, which enables efficient pair finding. The two pointers start and end traverse the sorted array, checking pairs. If the sum of elements at these pointers equals kk, a valid pair is found, and both pointers move inward. If the sum is greater than kk, end moves left to reduce the sum; if less, start moves right to increase the sum. This approach optimally identifies pairs with a sum of kk, with a time complexity of O(nlogn)O(n log n) due to sorting and O(n)O(n) for the two-pointer traversal, making it efficient for large arrays.