BinarySearch 0836 Sum Pairs to Target

Problem statement

https://binarysearch.com/problems/Sum-Pairs-to-Target/

Solution

We can sort and use two pointers. However we can do better: keep counter for values and for each pair x, target - x take the smallest among frequencies.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, target):
        cnt, ans = Counter(nums), 0
        for x in cnt:
            if x*2 == target:
                ans += cnt[x]//2 * 2
            else:
                ans += min(cnt[x], cnt[target - x])

        return ans//2