Number of pairs with sum K

Problem: You are given an integer array 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:

Input: nums = [1,3,5,7], k = 8
Output: 2
Explanation: Starting with nums = [1,3,5,7]:
- Remove numbers 1 and 7, then nums = [3,5]
- Remove numbers 3 and 5, then nums = []
There are no more pairs that sum up to 8, hence a total of 2 operations.

Approach: Basically this problem is an extension of finding two numbers whose sum equals k. Here we just need to find all the the pairs, instead of just one. 

We can sort the array and then apply the two pointers approach with one pointing at the start and second pointing at the end of the array but this will take O(nlogn) time. Let's use the hash only like we did in the previous problem. Here we also need to take care of duplicates. 

You can understand the solution by just looking at the code.

 

Implementation in C#:

    public int MaxOperations(int[] nums, int k)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        Dictionary<int, int> table = new Dictionary<int, int>();

        for (int i = 0; i < length; ++i)

        {

            if (!table.ContainsKey(nums[i]))

            {

                table[nums[i]] = 0;

            }

            ++table[nums[i]];

        }

        int totalOps = 0;

        for (int i = 0; i < length; ++i)

        {

            if (table.ContainsKey(nums[i]) && table.ContainsKey(k - nums[i]))

            {

                if (nums[i] * 2 == k && table[nums[i]] >= 2)

                {

                    ++totalOps;

                    table[nums[i]] -= 2;

                    this.CheckAndRemoveKeyIfRequired(table, nums[i]);

                }

                else if (nums[i] * 2 != k)

                {

                    ++totalOps;

                    --table[nums[i]];

                    --table[k - nums[i]];

                    this.CheckAndRemoveKeyIfRequired(table, nums[i]);

                    this.CheckAndRemoveKeyIfRequired(table, k - nums[i]);

                }

            }

        }

        return totalOps;

    }

    private void CheckAndRemoveKeyIfRequired(Dictionary<int, int> table,

                                            int key)

    {

        if (table[key] == 0)

        {

            table.Remove(key);

        }

    }

Complexity: O(n)