Sponsored
Sponsored
This approach involves using a hashmap to store the frequency of each number in the array. For each number in the array, check if the complement (k - current number) exists in the hashmap. If it does, form a pair and decrease the frequency of both the current number and its complement in the hashmap. This ensures that no number is reused in forming pairs, optimizing the number of operations possible.
Time Complexity: O(n) because it involves a single pass through the array and constant-time operations for the hash table.
Space Complexity: O(n) to store the counts in the hash map.
1def maxOperations(nums, k):
2 count = {}
3 operations = 0
4 for num in nums:
5 complement = k - num
6 if count.get(complement, 0) > 0:
7 operations += 1
8 count[complement] -= 1
9 else:
10 count[num] = count.get(num, 0) + 1
11 return operations
12
13# Example usage
14nums = [1, 2, 3, 4]
15k = 5
16print(maxOperations(nums, k))The Python solution employs a dictionary to keep track of the number of times each complement is needed. It processes the array while adjusting the counts and tracking the number of operations.
First sort the array, which allows the use of a two-pointer technique to find pairs. One pointer starts at the beginning and the other at the end of the sorted array. If the sum of the elements at these pointers equals k, increase the operations count and move both pointers. If the sum is less than k, move the left pointer to increase the sum, otherwise, move the right pointer to decrease the sum, thus efficiently finding all possible pairs.
Time Complexity: O(n log n) due to sorting, with a subsequent O(n) linear traversal using two pointers.
Space Complexity: O(1) for the additional pointers only.
public class Solution {
public int MaxOperations(int[] nums, int k) {
Array.Sort(nums);
int operations = 0, left = 0, right = nums.Length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
operations++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return operations;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 4};
int k = 5;
Solution sol = new Solution();
Console.WriteLine(sol.MaxOperations(nums, k));
}
}In C#, this method capitalizes on `Array.Sort()` to preprocess input data, providing groundwork for efficient traversal by pointers to seek target sums swiftly, thereby achieving productive use of runtime resources.