Skip to content

1679. Max Number of K-Sum Pairs

SourceWeekly Contest 218 Q2DifficultyMediumRating1345

Description

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Solutions

Solution 1: Sorting

Thinking

Pairs must sum to \(k\) and each value is used once. \(n\) is \(10^5\); after sorting, two pointers pair on sum \(k\), move the right end when too large, and the left when too small.

We sort \(nums\). Then \(l\) and \(r\) point to the first and last elements of \(nums\) respectively, and we compare the sum \(s\) of the two integers with \(k\).

  • If \(s = k\), it means that we have found two integers whose sum is \(k\). We increment the answer and then move \(l\) and \(r\) towards the middle;
  • If \(s > k\), then we move the \(r\) pointer to the left;
  • If \(s < k\), then we move the \(l\) pointer to the right;
  • We continue the loop until \(l \geq r\).

After the loop ends, we return the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        l, r, ans = 0, len(nums) - 1, 0
        while l < r:
            s = nums[l] + nums[r]
            if s == k:
                ans += 1
                l, r = l + 1, r - 1
            elif s > k:
                r -= 1
            else:
                l += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        int ans = 0;
        while (l < r) {
            int s = nums[l] + nums[r];
            if (s == k) {
                ++ans;
                ++l;
                --r;
            } else if (s > k) {
                --r;
            } else {
                ++l;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int cnt = 0;
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            if (nums[i] + nums[j] == k) {
                i++;
                j--;
                cnt++;
            } else if (nums[i] + nums[j] > k) {
                j--;
            } else {
                i++;
            }
        }
        return cnt;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func maxOperations(nums []int, k int) int {
    sort.Ints(nums)
    l, r, ans := 0, len(nums)-1, 0
    for l < r {
        s := nums[l] + nums[r]
        if s == k {
            ans++
            l++
            r--
        } else if s > k {
            r--
        } else {
            l++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maxOperations(nums: number[], k: number): number {
    const cnt = new Map();
    let ans = 0;
    for (const x of nums) {
        if (cnt.get(k - x)) {
            cnt.set(k - x, cnt.get(k - x) - 1);
            ++ans;
        } else {
            cnt.set(x, (cnt.get(x) | 0) + 1);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
        let mut nums = nums.clone();
        nums.sort();
        let (mut l, mut r, mut ans) = (0, nums.len() - 1, 0);
        while l < r {
            match nums[l] + nums[r] {
                sum if sum == k => {
                    ans += 1;
                    l += 1;
                    r -= 1;
                }
                sum if sum > k => {
                    r -= 1;
                }
                _ => {
                    l += 1;
                }
            }
        }
        ans
    }
}

Solution 2: Hash Table

Thinking

Solution 1 sorts. A frequency map of unpaired values pairs \(x\) with \(k-x\) when a leftover exists, otherwise stores \(x\), in linear time.

We use a hash table \(cnt\) to record the current remaining integers and their occurrence counts.

We iterate over \(nums\). For the current integer \(x\), we check if \(k - x\) is in \(cnt\). If it exists, it means that we have found two integers whose sum is \(k\). We increment the answer and then decrement the occurrence count of \(k - x\); otherwise, we increment the occurrence count of \(x\).

After the iteration ends, we return the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        ans = 0
        for x in nums:
            if cnt[k - x]:
                ans += 1
                cnt[k - x] -= 1
            else:
                cnt[x] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int x : nums) {
            if (cnt.containsKey(k - x)) {
                ++ans;
                if (cnt.merge(k - x, -1, Integer::sum) == 0) {
                    cnt.remove(k - x);
                }
            } else {
                cnt.merge(x, 1, Integer::sum);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int ans = 0;
        for (int& x : nums) {
            if (cnt[k - x]) {
                --cnt[k - x];
                ++ans;
            } else {
                ++cnt[x];
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func maxOperations(nums []int, k int) (ans int) {
    cnt := map[int]int{}
    for _, x := range nums {
        if cnt[k-x] > 0 {
            cnt[k-x]--
            ans++
        } else {
            cnt[x]++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
        let mut cnt = std::collections::HashMap::new();
        let mut ans = 0;
        for x in nums {
            let m = k - x;
            if let Some(v) = cnt.get_mut(&m) {
                ans += 1;
                *v -= 1;
                if *v == 0 {
                    cnt.remove(&m);
                }
            } else if let Some(v) = cnt.get_mut(&x) {
                *v += 1;
            } else {
                cnt.insert(x, 1);
            }
        }
        ans
    }
}

Comments