1679-max-number-of-k-sum-pairs

Try it on leetcode

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

Solution(Python)

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        return self.hashing(nums, k)

    # Time Complexity: O(n^2*OP)
    # Space Comeplxity: O(n)
    def bruteforce(self, nums, k):
        s = Counter(nums)
        cnt = 0
        print(s)
        while True:
            change = 0
            for key in list(s):
                if change:
                    break
                if k - key in s:
                    s[key] -= 1
                    s[k - key] -= 1
                    if s[key] <= 0:
                        del s[key]
                    if s[k - key] <= 0:
                        del s[k - key]
                    change += 1
            print(s, cnt)
            if change > 0:
                cnt += change
            else:
                return cnt

    # Time Complexity: O(nlogn)
    # Space Complexity: O(1)
    def sorting(self, nums: List[int], k: int) -> int:
        nums.sort()
        i, j = 0, len(nums) - 1

        cnt = 0

        while i < j:
            if nums[i] + nums[j] == k:
                cnt += 1
                i += 1
                j -= 1

            elif nums[i] + nums[j] > k:
                j -= 1
            else:
                i += 1
        return cnt

    # Time Complexity: O(n)
    # Space Complexity: O(n)
    def hashing(self, nums: List[int], k: int) -> int:
        hash = defaultdict(int)
        cnt = 0

        for num in nums:
            target = k - num

            if hash[target] > 0:
                hash[target] -= 1
                cnt += 1
            else:
                hash[num] += 1

        return cnt