Max Number Of K Sum Pairs - Leetcode 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.

Solution:

Approach:

• Create a map to store the frequency of each element of the array.
• Iterate through the array and for each element in the array, check if k-current element exists in the map or not. If it exists, then increment the count of answer by 1 and decrement the frequency of both elements in the map.
• Return the count of answer.

Algorithm:

1. Initialize a map m to store the frequency of each element in the array.
2. Initialize the count of answer to 0.
3. Iterate over the array and perform the following steps: a) If m[k-nums[i]] > 0, increment the count of answer by 1 and decrement the frequency of nums[i] and k-nums[i] in the map m.
4. Return the count of answer.

Code:

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        int ans = 0;
        for(int i=0;i<nums.size();i++) {
            int diff = k - nums[i];
            if(m[diff] > 0) {
                ans++;
                m[diff]--;
            } else {
                m[nums[i]]++;
            }
        }
        return ans;
    }
};

Time Complexity:

The time complexity of the above solution is O(n) where n is the size of the array.

Space Complexity:

The space complexity of the above solution is O(n) where n is the size of the array. The map size can be maximum n.

1