How to solve Leetcode 1679. Max Number of K-Sum Pairs

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: Starting with nums = [1,2,3,4]:
- 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: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, 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.

Solution: Count the appearances

You can use a map to count the appearances of the elements of nums.

Example 2

For nums = [3,1,3,4,3] and k = 6:

Initialize count = 0.
For i = 0: m[3] = 1; k - 3 = 3 but m[3] is only 1, not enough to have two numbers.
For i = 1: m[1] = 1; k - 1 = 5 and m[5] = 0.
For i = 2: m[3] = 2; k - 3 = 3 and m[3] = 2 just enough to have two numbers to perform the sum. count = 1. Erase those two values 3's from the map: m[3] = 0.
For i = 3: m[4] = 1; k - 4 = 2 and m[2] = 0.
For i = 4: m[3] = 1; k - 3 = 3 but m[3] is only 1, not enough to have two numbers.
Final count = 1.

Code

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
int maxOperations(vector<int>& nums, int k) {
    unordered_map<int,int> m;
    int count = 0;
    for (int a : nums) {
        m[a]++;
        if (m[k - a] > 0) {
            if (a != k - a || m[a] >= 2) {
                count++;
                m[a]--;
                m[k - a]--;
            }
        }
    }
    return count;
}
int main() {
    vector<int> nums{1,2,3,4};
    cout << maxOperations(nums, 5) << endl;
    nums = {3,1,3,4,3};
    cout << maxOperations(nums, 6) << endl;
}

Output:
2
1

Complexity

Runtime: O(N), where N = nums.length.
Extra space: O(N).

References

Get my FREE book "10 Classic Coding Challenges"

How to solve Leetcode 1679. Max Number of K-Sum Pairs

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Constraints

Solution: Count the appearances

Example 2

Code

Complexity

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Constraints

Solution: Count the appearances

Example 2

Code

Complexity

References