Max number of K sum Pairs

XXX. Max Number of K-Sum Pairs

Hash Map

Array Manipulation

Problem Statement:

Given an array of integers nums and an integer k, return the maximum number of pairs of elements in the array that sum up to k. Each element can only be used in one pair.

Algorithm:

The algorithm uses a hash map to count occurrences of numbers and efficiently find pairs that sum up to k:

1. Create a hash map to track the count of each number.
2. Iterate through the array:
• For the current number, calculate the difference needed to reach k.
• If the difference exists in the hash map with a count greater than zero, a valid pair is found. Decrement the count of the difference in the map and increment the pair count.
• If the difference does not exist, increment the count of the current number in the hash map.
3. Return the total count of pairs.

Complexity:

Time Complexity: O(n), where n is the number of elements in the array. Each element is processed once.
Space Complexity: O(n), for the hash map used to store counts of numbers.

Java Implementation:

import java.util.*;

public class Solution {
    public int maxOperations(int[] nums, int k) {
        // Create a hash map to store the count of each number
        HashMap map = new HashMap<>();
        int count = 0;

        // Iterate through the array
        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            int diff = k - current;

            // Check if the complement (diff) exists in the map
            if (map.getOrDefault(diff, 0) > 0) {
                // Remove one occurrence of the complement
                map.put(diff, map.get(diff) - 1);
                count++;
            } else {
                // Add the current number to the map
                map.put(current, map.getOrDefault(current, 0) + 1);
            }
        }
        return count;
    }
}