How do you solve Max Number of K-Sum Pairs?

Iterate through nums once. For each num, check if the complement k - num exists in the hash map with a positive count. If yes, decrement the complement count and increment the operations count. Otherwise, increment the count of num in the map. Return the total operations count after processing all elements.

Max Number of K-Sum Pairs

Q: What is the time complexity of Max Number of K-Sum Pairs?

O(n). The algorithm iterates through the nums array once, performing O(1) average-time hash map operations for each element.

Q: What pattern does Max Number of K-Sum Pairs use?

The Pattern: Hash Maps (Frequency Counting for Complement Lookup) The Heuristic: When pairing elements based on a sum or difference condition, use a hash map to track frequencies of seen elements and check for complements in constant time to achieve a linear-time solution.

Medium Hash Maps

Problem

Given an integer array nums and an integer k, return the maximum number of operations where each operation consists of removing two elements from nums whose sum equals k.

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i], k ≤ 10⁹

Example

Input: nums = [1,2,3,4], k = 5

Output: 2

The brute-force approach would check all pairs to find sums equal to k, which is O(n^2) and inefficient for large inputs. Instead, the algorithm uses a hash map to track counts of numbers seen so far. For each number, it checks if its complement (k - num) exists in the map with a positive count. If so, it forms a valid pair, increments the operation count, and decrements the complement's count. Otherwise, it increments the count of the current number. This approach efficiently finds pairs in a single pass.

Approach

Straightforward Solution

A brute-force solution would check every pair of elements to see if they sum to k, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The problem reduces to finding pairs of numbers that sum to k, where each number can only be used once. This naturally suggests tracking frequencies of numbers and their complements.

Path to Optimal

Preview

Recognizing that for each number num, the complement needed is k - num, the problem can be transformed into a frequency lookup problem. Using a hash map to store counts of numbers seen so far allows checking for complements in O(1) average time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through nums once. For each num, check if the complement k - num exists in the hash map with a positive count…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the nums array once, performing O(1) average-time hash map operations for each element.

Space

O(n)

In the worst case, all elements are stored in the hash map if no pairs are found, requiring O(n) auxiliary space.

Pattern Spotlight

Hash Maps (Frequency Counting for Complement Lookup)

When pairing elements based on a sum or difference condition, use a hash map to track frequencies of seen elements and check for complements in constant time to achieve a linear-time solution.

Solution

Python

1class Solution:
  def maxOperations(self, nums: list[int], k: int) -> int:
      count = {}
      operations = 0
5
      for num in nums:
          complement = k - num
8
          if count.get(complement, 0) > 0:
              count[complement] -= 1
              operations += 1
          else:
              count[num] = count.get(num, 0) + 1
14
      return operations

Step-by-Step Solution

Initialize Frequency Map and Operation Counter

3count = {}
4operations = 0

Objective

To prepare data structures for tracking counts of numbers and the number of valid pairs found.

Key Insight

A hash map is used to store the frequency of numbers that have not yet been paired. The operations counter tracks how many valid pairs have been formed. This setup enables efficient complement checks during iteration.

Interview Quick-Check

Core Logic

The hash map stores counts of unpaired numbers, enabling O(1) average-time complement lookups.

State & Boundaries

The operations counter starts at zero and increments only when a valid pair is found.

Iterate Through Array and Count Valid K-Sum Pairs

To process each number, check for its complement, and update counts and operations accordingly.

Return Total Number of Valid Operations

To output the total count of valid pairs found after processing the entire array.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

if count.get(complement, 0) > 0:

Check if the complement exists with a positive count in the frequency map.

This condition identifies whether a valid pair can be formed with the current number and a previously seen complement.

Line 10 Critical

count[complement] -= 1

Decrement the count of the complement as it is now paired.

Reducing the complement's count prevents reuse of the same element in multiple pairs, ensuring correctness.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why do we check for the complement's existence before adding the current number to the hash map?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Max Number of K-Sum Pairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Max Number of K-Sum Pairs drill

or drill a free problem

1	`class Solution:`
2	`def maxOperations(self, nums: list[int], k: int) -> int:`
3	`count = {}`
4	`operations = 0`
5
6	`for num in nums:`
7	`complement = k - num`
8
9	`if count.get(complement, 0) > 0:`
10	`count[complement] -= 1`
11	`operations += 1`
12	`else:`
13	`count[num] = count.get(num, 0) + 1`
14
15	`return operations`