Leetcode - Max Number of K-Sum Pairs

Leetcode : Max Number of K-Sum Pairs

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
# Remove numbers 1 and 4, then nums = [2,3]
# Remove numbers 2 and 3, then nums = []

Example 2

Input

nums = [3,1,3,4,3], k = 6

Output

1

Approach

Create a hash-table to contain each number and the target number (k - num) for every iteration. When the target number already exists in the hash-table, decrement the value by one and increment the answer.

Solution (Python)

class Solution(object):
    def maxOperations(self, nums, k):
        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 

Result

Runtime : 592ms
Memory Usage : 23.5MB
Runtime Beats 74.91% of Python Submission