1679. Max Number of K-Sum Pairs

MediumArrayHash TableTwo PointersSorting
Leetcode Link

Problem Description

You're provided with an integer array called nums and another integer k. The goal is to determine how many pairs of numbers you can find and remove from the array such that the sum of each pair equals k. The operation of picking and removing such a pair is counted as one operation. The task is to return the maximum number of such operations that you can perform on the given array.

Intuition

To solve this problem, we use a two-pointer technique, which is a common strategy in problems involving sorted arrays or sequences. First, we sort the array in ascending order. After sorting, we position two pointers: one at the beginning (l) and one at the end (r) of the array.

  • If the sum of the values at the two pointers is exactly k, we've found a valid pair that can be removed from the array. We increment our operation count (ans), and then move the left pointer to the right (l + 1) and the right pointer to the left (r - 1) to find the next potential pair.
  • If the sum is greater than k, we need to decrease it. Since the array is sorted, the largest sum can be reduced by moving the right pointer to the left (r - 1).
  • If the sum is less than k, we need to increase it. We do this by moving the left pointer to the right (l + 1).

We repeat this process, scanning the array from both ends towards the middle, until the two pointers meet. This approach ensures that we find all valid pairs that can be formed without repeating any number, as each operation requires removing the paired numbers from the array.

The reason this approach works efficiently is that sorting the array allows us to make decisions based on the sum comparison, ensuring that we do not need to reconsider any previous elements once a pair is found or the pointers have been moved.

Learn more about Two Pointers and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How many ways can you arrange the three letters A, B and C?

Solution Approach

The solution provided uses a two-pointer approach to implement the logic that was described in the previous intuition section. Below is a step-by-step walkthrough of the algorithm, referencing the provided Python code.

  1. Sort the nums list. This is a crucial step as it allows for the two-pointer approach to work efficiently. We need the array to be ordered so we can target sums that are too high or too low by moving the appropriate pointer.
1nums.sort()
  1. Initialize two pointers, l (left) and r (right), at the start and end of the array, respectively. Also, initialize an ans variable to count the number of operations.
1l, r, ans = 0, len(nums) - 1, 0
  1. Enter a while loop that will continue to execute as long as the left pointer is less than the right pointer, ensuring we do not cross pointers and recheck the same elements.
1while l < r:
  1. Within the loop, calculate the sum s of the elements at the pointers' positions.
1s = nums[l] + nums[r]
  1. Check if the sum s equals k. If it does:
    • Increment the ans variable because we found a valid operation.
    • Move the left pointer one step to the right to seek the next potential pair.
    • Move the right pointer one step to the left.
1if s == k:
2    ans += 1
3    l, r = l + 1, r - 1
  1. If the sum s is more significant than k, the right pointer must be decremented to find a smaller pair sum.
1elif s > k:
2    r -= 1
  1. If the sum s is less than k, the left pointer must be incremented to find a greater pair sum.
1else:
2    l += 1
  1. After the while loop concludes, return the ans variable, which now contains the count of all operations performed — the maximum number of pairs with the sum k that were removed from the array.
1return ans

This approach only uses the sorted list and two pointers without additional data structures. The space complexity of the algorithm is O(log n) due to the space required for sorting, with the time complexity being O(n log n) because of the sorting step; the scanning of the array using two pointers is O(n), which does not dominate the time complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's take an example to see how the two-pointer solution approach works. Assume we have the following integer array called nums and an integer k = 10:

1nums = [3, 5, 4, 6, 2]

Let's walk through the algorithm step-by-step:

  1. First, we sort the nums array:
1nums = [2, 3, 4, 5, 6] // Sorted array
  1. We initialize our pointers and answer variable:
1l = 0  // Left pointer index
2r = 4  // Right pointer index (nums.length - 1)
3ans = 0  // Number of pairs found

  1. Start the loop with while l < r. Our initial pointers are at positions nums[0] and nums[4].

  2. At the first iteration, the sum of the elements at the pointers' positions is s = nums[l] + nums[r] = nums[0] + nums[4] = 2 + 6 = 8.

  3. Since 8 is less than k, we increment the left pointer l to try and find a larger sum. The pointers are now l = 1 and r = 4.

  4. Now, s = nums[l] + nums[r] = nums[1] + nums[4] = 3 + 6 = 9.

  5. Since 9 is still less than k, we increment l again. The pointers are now l = 2 and r = 4.

  6. Now, s = nums[l] + nums[r] = nums[2] + nums[4] = 4 + 6 = 10.

  7. Since 10 is equal to k, we increment ans to 1 and move both pointers inward: l becomes 3, and r becomes 3.

  8. Since l is no longer less than r, the loop ends.

  9. We return the ans variable, which stands at 1, indicating we have found one pair (4, 6) that sums up to k.

Hence, using this approach, the maximum number of operations (pairs summing up to k) we can perform on nums is 1.

Solution Implementation

1from typing import List
2
3class Solution:
4    def max_operations(self, nums: List[int], k: int) -> int:
5        # Sort the array first to apply the two-pointer technique
6        nums.sort()
7      
8        # Initialize two pointers, one at the start and one at the end
9        left, right = 0, len(nums) - 1
10      
11        # Initialize a counter to keep track of valid operations
12        operations_count = 0
13      
14        # Iterate through the list with two pointers
15        while left < right:
16            # Calculate the sum of elements pointed by left and right
17            sum_of_pair = nums[left] + nums[right]
18          
19            # If the sum equals k, we found a valid pair
20            if sum_of_pair == k:
21                # Increment the count of valid operations
22                operations_count += 1
23                # Move both pointers towards the center
24                left += 1
25                right -= 1
26            # If the sum is too large, move the right pointer to the left
27            elif sum_of_pair > k:
28                right -= 1
29            # If the sum is too small, move the left pointer to the right
30            else:
31                left += 1
32      
33        # Return the total count of valid operations
34        return operations_count
35
1class Solution {
2    public int maxOperations(int[] nums, int k) {
3        // Sort the array to use two pointers approach
4        Arrays.sort(nums);
5      
6        // Initialize two pointers, one at the start (left) and one at the end (right) of the array
7        int left = 0, right = nums.length - 1;
8      
9        // Initialize the answer variable to count the number of operations
10        int answer = 0;
11      
12        // Use a while loop to move the two pointers towards each other
13        while (left < right) {
14            // Calculate the sum of the two-pointer elements
15            int sum = nums[left] + nums[right];
16          
17            // Check if the sum is equal to k
18            if (sum == k) {
19                // If it is, increment the number of operations
20                ++answer;
21                // Move the left pointer to the right and the right pointer to the left
22                ++left;
23                --right;
24            } else if (sum > k) {
25                // If the sum is greater than k, we need to decrease the sum
26                // We do this by moving the right pointer to the left
27                --right;
28            } else {
29                // If the sum is less than k, we need to increase the sum
30                // We do this by moving the left pointer to the right
31                ++left;
32            }
33        }
34        // Return the total number of operations
35        return answer;
36    }
37}
38
1#include <vector> // Include necessary header for vector
2#include <algorithm> // Include algorithm header for sort function
3
4class Solution {
5public:
6    int maxOperations(std::vector<int>& nums, int k) {
7        // Sort the vector to make two-pointer technique applicable
8        std::sort(nums.begin(), nums.end());
9      
10        int count = 0; // Initialize count of operations
11        int left = 0; // Initialize left pointer
12        int right = nums.size() - 1; // Initialize right pointer 
13
14        // Use two-pointer technique to find pairs that add up to k
15        while (left < right) {
16            // When the sum of the current pair equals k
17            if (nums[left] + nums[right] == k) {
18                left++; // Move left pointer to the right
19                right--; // Move right pointer to the left
20                count++; // Increment the count of valid operations
21            } else if (nums[left] + nums[right] > k) {
22                // If the sum is greater than k, move right pointer to the left
23                right--;
24            } else {
25                // If the sum is less than k, move left pointer to the right
26                left++;
27            }
28        }
29      
30        return count; // Return the total count of operations
31    }
32};
33
34// Example usage of the class:
35// Solution sol;
36// std::vector<int> nums = {3, 1, 3, 4, 3};
37// int k = 6;
38// int result = sol.maxOperations(nums, k);
39// std::cout << "Maximum operations to reach sum k: " << result << std::endl;
40
1function maxOperations(nums: number[], targetSum: number): number {
2    const countMap = new Map<number, number>();
3    let operationsCount = 0;
4  
5    // Iterate over each number in the array
6    for (const num of nums) {
7        const complement = targetSum - num; // Calculate the complement of the current number
8
9        // If the complement is already in the map, 
10        // we can form a pair whose sum is equal to targetSum
11        if (countMap.get(complement) > 0) {
12            countMap.set(complement, countMap.get(complement) - 1); // Decrement the count of complement in map
13            operationsCount++; // Increment the count of valid operations
14        } else {
15            // If the complement is not there, store/update the count of the current number
16            const currentCount = (countMap.get(num) || 0) + 1;
17            countMap.set(num, currentCount);
18        }
19    }
20  
21    return operationsCount; // Return the total number of operations
22}
23
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity

The given code has a time complexity of O(n log n).

Here's the breakdown:

  • Sorting the nums list takes O(n log n) time.
  • The while loop runs in O(n) time because it iterates through the list at most once by moving two pointers from both ends towards the center. In each iteration, one of the pointers moves, ensuring that the loop cannot run for more than n iterations.
  • The operations inside the while loop are all constant time checks and increments, each taking O(1).

Therefore, the combined time complexity is dominated by the sorting step, giving us O(n log n).

Space Complexity

The space complexity of the code is O(1) provided that the sorting algorithm used in place.

  • No additional data structures are used that depend on the input size of nums.
  • Extra variables l, r, and ans are used, but they occupy constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫