Max Number of K-Sum Pairs

Introduction

Today, I tackled another intriguing problem from LeetCode 75: Max Number of K-Sum Pairs. This medium-level question requires an understanding of arrays and the two-pointer technique. The goal is to find the maximum number of operations you can perform where you pick two numbers from the array that sum up to k and remove them. Let's dive into the problem statement, approach, and solution.

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:

• 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:

• Remove the first two 3s, 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 <= 10^5

• 1 <= nums[i] <= 10^9

• 1 <= k <= 10^9

Approach to Solve the Problem

To solve this problem, we can use the two-pointer technique after sorting the array. Here’s the step-by-step approach:

1. Sort the Array: First, sort the array to bring all smaller elements to the front and larger elements to the back.

2. Initialize Two Pointers: Use two pointers, one starting from the beginning (i = 0) and the other from the end (j = nums.length - 1) of the array.

3. Find Pairs: Iterate through the array using these two pointers:

   • If the sum of the elements at the two pointers is equal to k, increment the count, and move both pointers inward.

   • If the sum is less than k, move the left pointer (i) to the right to increase the sum.

   • If the sum is greater than k, move the right pointer (j) to the left to decrease the sum.

4. Stop Condition: Stop when the two pointers cross each other.

Solution

Here’s the Java code that implements the above approach:

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

    int i = 0; 
    int j = nums.length-1;

    int count = 0;

    while (i < j){
        if(nums[i] + nums[j] == k){
            count++;
            i++;
            j--;

        } else if(nums[i] + nums[j] > k) {
            j--;
        }else{
            i++;
        }
    }

    return count;
}

Explanation

1. Sorting the Array: By sorting the array, we ensure that we can use the two-pointer technique effectively.

2. Two Pointers: i starts from the beginning and j starts from the end. By checking the sum of nums[i] and nums[j], we can decide whether to move the pointers inward or to count the pair.

3. Counting Pairs: If the sum is equal to k, it means we found a valid pair, so we increase the count and move both pointers inward. If the sum is less than k, it means we need a larger sum, so we move the left pointer (i) to the right. If the sum is greater than k, it means we need a smaller sum, so we move the right pointer (j) to the left.

Performance

The time complexity of this approach is O(n log n) due to the sorting step. The two-pointer traversal takes O(n), resulting in an overall time complexity dominated by the sorting step. This is efficient and performs well for the given constraints.

Conclusion

The "Max Number of K-Sum Pairs" problem is a classic example of how sorting and the two-pointer technique can be combined to solve problems involving pair sums efficiently. By sorting the array and using two pointers, we can find and count the maximum number of pairs that sum up to k with an optimal time complexity of O(n log n). This problem reinforces the importance of these fundamental techniques in array manipulation and problem-solving.

Feel free to share your thoughts and any alternative approaches you might have!