Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5

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.

Solution

This is problem is close to Two Sum.

Method 1 - Using Hashmap but two pass

Here is the approach:

  1. Use a frequency map (or dictionary) to count the occurrences of each element in the array.
  2. Iterate through the array, and for each element, check if its complement (k - num) exists in the frequency map with a sufficient count.
  3. If both the element and its complement have valid counts, decrement the counts of both elements in the frequency map and increment the operation count.
  4. Continue this until all possible pairs are exhausted.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public int maxOperations(int[] nums, int k) {
        // Create a frequency map of elements in the array
        Map<Integer, Long> freqMap = Arrays.stream(nums).boxed().collect(
            Collectors.groupingBy(
                Function.identity(),
                HashMap::new,
                Collectors.counting()
            )
        );

        int ans = 0;

        for (int num : nums) {
            // Check if the current number and its complement have valid counts
            if (freqMap.get(num) >= 1 && freqMap.containsKey(k - num) && freqMap.get(k - num) >= 1) {
                freqMap.put(num, freqMap.get(num) - 1);
                if (freqMap.get(k - num) < 1) {
                    continue;
                }
                freqMap.put(k - num, freqMap.get(k - num) - 1);
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def max_operations(self, nums: List[int], k: int) -> int:
        # Create a frequency map of elements in the array
        freq_map = defaultdict(int)
        for num in nums:
            freq_map[num] += 1

        ans = 0

        for num in nums:
            # Check if the current number and its complement have valid counts
            if freq_map[num] >= 1 and freq_map[k - num] >= 1:
                freq_map[num] -= 1
                if freq_map[k - num] < 1:
                    continue
                freq_map[k - num] -= 1
                ans += 1

        return ans

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Using Hashmap and One Pass

Here is the approach:

  1. Use a HashMap (or dictionary) to keep track of the occurrences of each element.
  2. As you iterate through the array, calculate the complement (k - nums[i]).
  3. Check if the complement exists in the HashMap.
  4. If it exists, increment the count and decrement the occurrence of the complement in the HashMap. Remove the complement from the HashMap if its count reaches zero.
  5. If the complement does not exist, update the HashMap with the current element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();  // HashMap to store counts of elements
        int count = 0;  // Counter for number of operations

        for (int i = 0; i < nums.length; i++) {
            int rem = k - nums[i];  // Calculate the complement
            if (map.containsKey(rem)) {
                count++;  // Increment count if complement is found
                map.put(rem, map.get(rem) - 1);  // Decrement the occurrence count of the complement
                if (map.get(rem) == 0) {
                    map.remove(rem);  // Remove the complement from HashMap if its count reaches zero
                }
            } else {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);  // Update HashMap with the current element
            }
        }
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def max_operations(self, nums: List[int], k: int) -> int:
        count = 0  # Counter for number of operations
        num_map = defaultdict(int)  # Dictionary to store counts of elements

        for num in nums:
            rem = k - num  # Calculate the complement
            if num_map[rem] > 0:
                count += 1  # Increment count if complement is found
                num_map[rem] -= 1  # Decrement the occurrence count of the complement
                if num_map[rem] == 0:
                    del num_map[rem]  # Remove the complement from dictionary if its count reaches zero
            else:
                num_map[num] += 1  # Update dictionary with the current element

        return count

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)