1679. Max Number of K-Sum Pairs

Intro

In this article, we will explore a problem and walk through various solutions. If you are looking for the solutions directly, feel free to scroll down to the respective sections.

Problem Statement

Summary

First thing we do is summarise the problem statement and remove all the fluff.

1. Find out how many combinations add up to `k`
2. The combinations have to be unique
3. The array is always going to be more than 1 in length and made up of positive integers
4. `k` will always be more than 1

With this summary, we can get started crafting our brute force solution for this problem. A lot of people start trying to find the most optimized solution. In the beginning(of your ds&A journey), it is better to first craft brute force and then optimize

Brute Force Solution

An easy way I have found that helps people come up with a solution is imagining how you would do it in real life. If you see the input and you were asked the question.

If someone had to do this in real life, these are the things we do:

1. pick element A (starting at the first) and check against all elements.
2. If there is a match(equals to K), we mentally add 1 to the count of operations
3. We can then set element A to the next variable
4. We will have to delete the elements at those index

Now we can start coding!!

First we have to build the logic for adding and checking each elements of the arr with others

const maxOperations =(nums, k) => {
    for(let i = 0; i < nums.length; i++){
        for(let j = i; j < nums.length; j++){
            if(nums[i] + nums[j] === k){
                console.log(nums[i], i, 'maxOperations', nums[j], j)
            }
        }
    }
}
maxOperations([3,1,3,4,3], 6)

We are comparing all elements with other elements and check if it equals k. When you run this code, you will notice it console.log 6 times even though the expected answer is 1.

That is because we did not handle the removal of elements from the array, so we basically are double/triple counting. Lets fix that.

What we have to do is remove the two elements from the logic. The simplest way to do that is making both the elements equal to something else. I will make those elements as NaN.

   nums[i] = NaN;
   nums[j] = NaN;

Lets put it all together with the counter logic.

const maxOperations = (nums, k) => {
    let counter = 0
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === k) {
                counter += 1

                nums[i] = NaN;
                nums[j] = NaN;
            }
        }
    }
    return counter
};

The time complexity is O(N^2)

Alternative Solutions

There are different solutions that we can do that are more optimized.

Approach 1: Hash Table - Time: O(N)

function maxOperationsHashMap(nums, k) {
    const frequencyMap = new Map();
    let operationsCount = 0;

    for (const num of nums) {
        const complement = k - num;
        if (frequencyMap.has(complement) && frequencyMap.get(complement) > 0) {
            operationsCount++;
            frequencyMap.set(complement, frequencyMap.get(complement) - 1);
        } else {
            frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
        }
    }

    return operationsCount;
}

Approach 2: Two Pointers - Time: O(N)

function maxOperationsTwoPointers(nums, k) {
    nums.sort((a, b) => a - b);

    let left = 0;
    let right = nums.length - 1;
    let operationsCount = 0;

    while (left < right) {
        const sum = nums[left] + nums[right];

        if (sum === k) {
            operationsCount++;
            left++;
            right--;
        } else if (sum < k) {
            left++;
        } else {
            right--;
        }
    }

    return operationsCount;
}

Approach 3: Count Frequencies with a Hash Table - Time: O(N)

function maxOperationsCountFrequencies(nums, k) {
    const frequencyMap = new Map();
    let operationsCount = 0;

    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    for (const num of nums) {
        const complement = k - num;

        if (frequencyMap.has(complement) && frequencyMap.get(complement) > 0 && frequencyMap.get(num) > 0) {
            operationsCount++;
            frequencyMap.set(num, frequencyMap.get(num) - 1);
            frequencyMap.set(complement, frequencyMap.get(complement) - 1);
        }
    }
    return operationsCount;
}

Summary

All of the three solutions we talked about here are O(N). I just wanted to show the different ways to solve. It helps to know that in case there are variations to the problem.

Thank you for reading! I hope this information proves helpful.