Max Number of K-Sum Pairs

🎯

Max Number of K-Sum Pairs

mediumHASH_MAPAmazonGoogle

Imagine you have a list of gift card balances and want to pair them up so that each pair sums exactly to a target amount, maximizing the number of such pairs.

💡 This problem is about efficiently counting pairs that sum to a target. Beginners often struggle because they try nested loops which are too slow, and don't realize how to track frequencies or complements to optimize.

📋

Problem Statement

Given an integer array nums and an integer k, return the maximum number of pairs of elements in the array that sum to k. Each element can be used at most once in one pair. Output the maximum number of such pairs.

1 ≤ nums.length ≤ 10^51 ≤ nums[i], k ≤ 10^9

💡

Example

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

Output2

Pairs are (1,4) and (2,3), both sum to 5.

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

Output1

Only one pair (3,3) sums to 6, even though there are multiple 3s.

• All elements are the same and k is twice that element → maximum pairs is floor(n/2)
• No two elements sum to k → output 0
• Array with only one element → output 0
• Large array with no duplicates but pairs exist → verify correctness and performance

⚠️

Common Mistakes

Not marking elements as used in brute force

Pairs counted multiple times, incorrect answer

✅ Use a visited array or frequency map to track used elements

Not sorting before two pointers

Two pointers won't work correctly, wrong output

✅ Always sort the array before applying two-pointer technique

Decrementing frequency incorrectly in hash map approach

May pair elements multiple times or miss pairs

✅ Decrement complement frequency only when a pair is formed

Using nested loops on large input without optimization

Time limit exceeded (TLE) in interviews

✅ Use sorting + two pointers or hash map approach for efficiency

Not handling edge cases like single element or no pairs

Code may crash or return wrong result

✅ Add checks or rely on loop conditions to handle these gracefully

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking all pairs explicitly, even though it's inefficient.

Intuition

Try every possible pair and count those that sum to k, marking used elements so they aren't reused.

Algorithm

1. Initialize a count to zero and a visited array to mark used elements.
2. Use two nested loops to check every pair (i, j) with i < j.
3. If nums[i] + nums[j] == k and neither is visited, increment count and mark both visited.
4. Return the count after checking all pairs.

💡 The nested loops make it easy to understand pairing but hard to scale; marking visited ensures no reuse.

</>

Code

def maxOperations(nums, k):
    n = len(nums)
    visited = [False] * n
    count = 0
    for i in range(n):
        if visited[i]:
            continue
        for j in range(i + 1, n):
            if not visited[j] and nums[i] + nums[j] == k:
                count += 1
                visited[i] = True
                visited[j] = True
                break
    return count

# Driver code
if __name__ == '__main__':
    print(maxOperations([1,2,3,4], 5))  # Output: 2
    print(maxOperations([3,1,3,4,3], 6))  # Output: 1

Line Notes

visited = [False] * nTrack which elements are already paired to avoid reuse

for i in range(n)Outer loop picks first element to pair

if visited[i]: continueSkip elements already used in a pair

for j in range(i + 1, n)Inner loop tries to find a complement for nums[i]

if not visited[j] and nums[i] + nums[j] == kCheck if pair sums to k and both unused

count += 1Increment count when a valid pair is found

visited[i] = True; visited[j] = TrueMark both elements as used to prevent reuse

import java.util.*;
public class Solution {
    public static int maxOperations(int[] nums, int k) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            for (int j = i + 1; j < n; j++) {
                if (!visited[j] && nums[i] + nums[j] == k) {
                    count++;
                    visited[i] = true;
                    visited[j] = true;
                    break;
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(maxOperations(new int[]{1,2,3,4}, 5)); // 2
        System.out.println(maxOperations(new int[]{3,1,3,4,3}, 6)); // 1
    }
}

Line Notes

boolean[] visited = new boolean[n];Track used elements to avoid pairing them again

for (int i = 0; i < n; i++)Outer loop selects first element

if (visited[i]) continue;Skip elements already paired

for (int j = i + 1; j < n; j++)Inner loop finds complement for nums[i]

if (!visited[j] && nums[i] + nums[j] == k)Check if pair sums to k and both unused

count++;Increment count for each valid pair

visited[i] = true; visited[j] = true;Mark elements as used

#include <iostream>
#include <vector>
using namespace std;

int maxOperations(vector<int>& nums, int k) {
    int n = nums.size();
    vector<bool> visited(n, false);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        for (int j = i + 1; j < n; j++) {
            if (!visited[j] && nums[i] + nums[j] == k) {
                count++;
                visited[i] = true;
                visited[j] = true;
                break;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums1 = {1,2,3,4};
    cout << maxOperations(nums1, 5) << "\n"; // 2
    vector<int> nums2 = {3,1,3,4,3};
    cout << maxOperations(nums2, 6) << "\n"; // 1
    return 0;
}

Line Notes

vector<bool> visited(n, false);Keep track of which elements are already paired

for (int i = 0; i < n; i++)Outer loop picks first element

if (visited[i]) continue;Skip elements already used

for (int j = i + 1; j < n; j++)Inner loop searches for complement

if (!visited[j] && nums[i] + nums[j] == k)Check sum and usage status

count++;Count valid pairs

visited[i] = true; visited[j] = true;Mark elements as paired

function maxOperations(nums, k) {
    const n = nums.length;
    const visited = new Array(n).fill(false);
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;
        for (let j = i + 1; j < n; j++) {
            if (!visited[j] && nums[i] + nums[j] === k) {
                count++;
                visited[i] = true;
                visited[j] = true;
                break;
            }
        }
    }
    return count;
}

// Test cases
console.log(maxOperations([1,2,3,4], 5)); // 2
console.log(maxOperations([3,1,3,4,3], 6)); // 1

Line Notes

const visited = new Array(n).fill(false);Track which elements are already paired

for (let i = 0; i < n; i++)Outer loop picks first element

if (visited[i]) continue;Skip elements already used

for (let j = i + 1; j < n; j++)Inner loop finds complement

if (!visited[j] && nums[i] + nums[j] === k)Check sum and usage

count++;Increment count for valid pairs

visited[i] = true; visited[j] = true;Mark elements as used

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops check all pairs, so O(n^2). The visited array uses O(n) space.

💡 For n=1000, this means about 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE on large inputs

This approach is too slow for big arrays but helps understand the problem and correctness before optimizing.

🧠

Sorting + Two Pointers

💡 Sorting the array lets us use two pointers to find pairs efficiently, reducing complexity from quadratic to linearithmic.

Intuition

Sort the array, then use two pointers from start and end to find pairs summing to k, moving pointers inward accordingly.

Algorithm

1. Sort the array in ascending order.
2. Initialize two pointers: left at 0, right at n-1.
3. While left < right, check sum of nums[left] + nums[right].
4. If sum == k, increment count and move both pointers inward.
5. If sum < k, move left pointer right to increase sum.
6. If sum > k, move right pointer left to decrease sum.
7. Return the count after pointers cross.

💡 Sorting allows a linear scan with two pointers, avoiding nested loops and repeated checks.

</>

Code

def maxOperations(nums, k):
    nums.sort()
    left, right = 0, len(nums) - 1
    count = 0
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == k:
            count += 1
            left += 1
            right -= 1
        elif current_sum < k:
            left += 1
        else:
            right -= 1
    return count

# Driver code
if __name__ == '__main__':
    print(maxOperations([1,2,3,4], 5))  # 2
    print(maxOperations([3,1,3,4,3], 6))  # 1

Line Notes

nums.sort()Sorting enables two-pointer technique

left, right = 0, len(nums) - 1Initialize pointers at array ends

while left < rightLoop until pointers cross

current_sum = nums[left] + nums[right]Calculate sum of current pair

if current_sum == kFound a valid pair

count += 1Increment count for valid pair

left += 1; right -= 1Move both pointers inward after pairing

elif current_sum < kSum too small, move left pointer to increase sum

else: right -= 1Sum too large, move right pointer to decrease sum

import java.util.*;
public class Solution {
    public static int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        int count = 0;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == k) {
                count++;
                left++;
                right--;
            } else if (sum < k) {
                left++;
            } else {
                right--;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(maxOperations(new int[]{1,2,3,4}, 5)); // 2
        System.out.println(maxOperations(new int[]{3,1,3,4,3}, 6)); // 1
    }
}

Line Notes

Arrays.sort(nums);Sort array to apply two-pointer approach

int left = 0, right = nums.length - 1;Initialize pointers at array ends

while (left < right)Loop until pointers meet or cross

int sum = nums[left] + nums[right];Calculate sum of current pair

if (sum == k)Found a valid pair

count++;Increment count for valid pair

left++; right--;Move pointers inward after pairing

else if (sum < k)Sum too small, move left pointer right

elseSum too large, move right pointer left

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxOperations(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int left = 0, right = nums.size() - 1;
    int count = 0;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == k) {
            count++;
            left++;
            right--;
        } else if (sum < k) {
            left++;
        } else {
            right--;
        }
    }
    return count;
}

int main() {
    vector<int> nums1 = {1,2,3,4};
    cout << maxOperations(nums1, 5) << "\n"; // 2
    vector<int> nums2 = {3,1,3,4,3};
    cout << maxOperations(nums2, 6) << "\n"; // 1
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array for two-pointer technique

int left = 0, right = nums.size() - 1;Initialize pointers at ends

while (left < right)Loop until pointers cross

int sum = nums[left] + nums[right];Calculate sum of pair

if (sum == k)Found valid pair

count++;Increment count

left++; right--;Move pointers inward after pairing

else if (sum < k)Sum too small, move left pointer right

elseSum too large, move right pointer left

function maxOperations(nums, k) {
    nums.sort((a, b) => a - b);
    let left = 0, right = nums.length - 1;
    let count = 0;
    while (left < right) {
        const sum = nums[left] + nums[right];
        if (sum === k) {
            count++;
            left++;
            right--;
        } else if (sum < k) {
            left++;
        } else {
            right--;
        }
    }
    return count;
}

// Test cases
console.log(maxOperations([1,2,3,4], 5)); // 2
console.log(maxOperations([3,1,3,4,3], 6)); // 1

Line Notes

nums.sort((a, b) => a - b);Sort array to enable two-pointer approach

let left = 0, right = nums.length - 1;Initialize pointers at array ends

while (left < right)Loop until pointers cross

const sum = nums[left] + nums[right];Calculate sum of current pair

if (sum === k)Found a valid pair

count++;Increment count for valid pair

left++; right--;Move pointers inward after pairing

else if (sum < k)Sum too small, move left pointer right

elseSum too large, move right pointer left

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(log n) depending on sort implementation

Sorting takes O(n log n), two-pointer scan is O(n), total O(n log n). Space is minimal aside from sort.

💡 For n=100000, this is about 1.5 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is efficient and easy to implement, a good choice if sorting is allowed.

🧠

Hash Map Frequency Counting (Optimal)

💡 Using a hash map to track frequencies of complements lets us find pairs in a single pass, achieving linear time.

Intuition

For each number, check if its complement (k - num) exists in the map with positive count; if yes, form a pair and decrement frequency; else add current number to map.

Algorithm

1. Initialize a frequency map (hash map) to count occurrences of numbers.
2. Initialize count to zero.
3. Iterate over each number in nums:
4. - Calculate complement = k - num.
5. - If complement exists in map with count > 0, decrement complement count and increment count.
6. - Else, increment count of current number in map.
7. Return count.

💡 This approach tracks what complements are needed and pairs them immediately, avoiding sorting and nested loops.

</>

Code

def maxOperations(nums, k):
    freq = {}
    count = 0
    for num in nums:
        complement = k - num
        if freq.get(complement, 0) > 0:
            count += 1
            freq[complement] -= 1
        else:
            freq[num] = freq.get(num, 0) + 1
    return count

# Driver code
if __name__ == '__main__':
    print(maxOperations([1,2,3,4], 5))  # 2
    print(maxOperations([3,1,3,4,3], 6))  # 1

Line Notes

freq = {}Initialize frequency map to track needed complements

for num in nums:Iterate over each number in array

complement = k - numCalculate complement needed to form pair

if freq.get(complement, 0) > 0Check if complement is available to pair

count += 1Increment count when pair is formed

freq[complement] -= 1Use one occurrence of complement

else: freq[num] = freq.get(num, 0) + 1Add current number to map if no complement found

import java.util.*;
public class Solution {
    public static int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int count = 0;
        for (int num : nums) {
            int complement = k - num;
            if (freq.getOrDefault(complement, 0) > 0) {
                count++;
                freq.put(complement, freq.get(complement) - 1);
            } else {
                freq.put(num, freq.getOrDefault(num, 0) + 1);
            }
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(maxOperations(new int[]{1,2,3,4}, 5)); // 2
        System.out.println(maxOperations(new int[]{3,1,3,4,3}, 6)); // 1
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>();Frequency map to track needed complements

for (int num : nums)Iterate over each number

int complement = k - num;Calculate complement needed

if (freq.getOrDefault(complement, 0) > 0)Check if complement available

count++;Increment count for formed pair

freq.put(complement, freq.get(complement) - 1);Use one complement occurrence

freq.put(num, freq.getOrDefault(num, 0) + 1);Add current number if no complement

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int maxOperations(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    int count = 0;
    for (int num : nums) {
        int complement = k - num;
        if (freq[complement] > 0) {
            count++;
            freq[complement]--;
        } else {
            freq[num]++;
        }
    }
    return count;
}

int main() {
    vector<int> nums1 = {1,2,3,4};
    cout << maxOperations(nums1, 5) << "\n"; // 2
    vector<int> nums2 = {3,1,3,4,3};
    cout << maxOperations(nums2, 6) << "\n"; // 1
    return 0;
}

Line Notes

unordered_map<int, int> freq;Hash map to track needed complements

for (int num : nums)Iterate over each number

int complement = k - num;Calculate complement

if (freq[complement] > 0)Check if complement available

count++;Increment count for pair

freq[complement]--;Use one complement occurrence

freq[num]++;Add current number if no complement

function maxOperations(nums, k) {
    const freq = new Map();
    let count = 0;
    for (const num of nums) {
        const complement = k - num;
        if (freq.get(complement) > 0) {
            count++;
            freq.set(complement, freq.get(complement) - 1);
        } else {
            freq.set(num, (freq.get(num) || 0) + 1);
        }
    }
    return count;
}

// Test cases
console.log(maxOperations([1,2,3,4], 5)); // 2
console.log(maxOperations([3,1,3,4,3], 6)); // 1

Line Notes

const freq = new Map();Map to track needed complements

for (const num of nums)Iterate over each number

const complement = k - num;Calculate complement

if (freq.get(complement) > 0)Check if complement available

count++;Increment count for pair

freq.set(complement, freq.get(complement) - 1);Use one complement occurrence

freq.set(num, (freq.get(num) || 0) + 1);Add current number if no complement

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass over array with O(1) average map operations, total O(n). Space for map up to O(n).

💡 For n=100000, this means about 100,000 operations, very efficient for interviews.

Interview Verdict: Accepted

This is the best approach for large inputs and is commonly expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the hash map approach in 95% of interviews for best balance of speed and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	Yes	Mention only - never code for large inputs
2. Sorting + Two Pointers	O(n log n)	O(1) or O(log n)	No	Yes	Good fallback if hash map not allowed
3. Hash Map Frequency Counting	O(n)	O(n)	No	Yes	Optimal approach to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Discuss sorting + two pointers as a better approach.Present the hash map frequency counting as the optimal solution.Write clean code for the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, code correctness, and handling of edge cases.

Common Follow-ups

• What if the array is sorted? → Use two pointers directly.
• Can you do it in one pass? → Use hash map frequency counting.
• What if elements can be reused multiple times? → Adjust frequency tracking accordingly.
• How to handle very large numbers? → Use appropriate data types and avoid overflow.

💡 These follow-ups test your flexibility and deeper understanding of the problem constraints and variants.

🔍

Pattern Recognition

When to Use

1) Problem asks for pairs summing to a target; 2) Elements used at most once; 3) Maximize number of pairs; 4) Large input size requiring efficient solution.

Signature Phrases

'maximum number of pairs that sum to k''each element can be used at most once'

NOT This Pattern When

Problems allowing unlimited reuse or requiring all pairs without maximum count are different.

Similar Problems

Two Sum - find if any pair sums to targetPair with Given Sum - count pairs without reuseCount Number of Pairs With Absolute Difference K - similar frequency tracking

Practice

1. You are given a binary array and need to find the length of the longest contiguous subarray with an equal number of 0s and 1s. Which approach guarantees an optimal O(n) time solution?

easy

A. Use a greedy approach to expand the window whenever the count of zeros equals ones.

B. Use a brute force nested loop to check all subarrays and count zeros and ones.

C. Use a prefix sum where 0s are treated as -1, and store earliest indices of prefix sums in a hash map.

D. Use dynamic programming to store the maximum length subarray ending at each index.

Solution

1. Step 1: Understand the problem requires tracking balance of 0s and 1s

   Transform 0s to -1s so that a prefix sum of zero indicates equal number of 0s and 1s.

2. Step 2: Use a hash map to store earliest indices of prefix sums

   When the same prefix sum repeats, the subarray between indices has equal 0s and 1s. This yields O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Brute force is O(n²), greedy fails on some cases, DP is not straightforward [OK]

Hint: Prefix sums with hash map track balance efficiently [OK]

Common Mistakes:

• Thinking greedy or DP solves this optimally
• Not transforming 0 to -1
• Using nested loops for large inputs

2. Identify the bug in the following code snippet for the Minimum Operations to Reduce X to Zero problem:

medium

A. Line with 'if target == 0: return -1' should return len(nums) instead.

B. The while loop condition should be 'current_sum >= target' instead of '>'.

C. The initialization of max_len should be 0 instead of -1.

D. The final return should be 'max_len' instead of 'len(nums) - max_len'.

Solution

1. Step 1: Understand the edge case when target == 0

   If target == 0, it means totalSum == x, so removing all elements is needed, so minimum operations = length of array.

2. Step 2: Identify incorrect return value

   The code returns -1 incorrectly, which signals no solution, but the correct answer is to remove all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning -1 here causes wrong output on full removal case [OK]

Hint: Check edge cases where x equals total sum [OK]

Common Mistakes:

• Returning -1 instead of full length when target == 0
• Misinterpreting no solution vs full removal
• Ignoring edge cases in initial checks

3. The following code attempts to find the longest subarray with equal number of 0s and 1s. What is the subtle bug causing incorrect results on some inputs?

medium

A. Missing initialization of first_occurrence[offset] = -1 before the loop

B. Incorrect prefix_sum update: should add 1 for 0 and -1 for 1

C. Updating max_length before checking if prefix_sum exists in first_occurrence

D. Using -2 as initial value in first_occurrence instead of -1

Solution

1. Step 1: Check initialization of first_occurrence array.

   It must have first_occurrence[offset] = -1 to handle subarrays starting at index 0.

2. Step 2: Without this initialization, subarrays starting at index 0 are missed.

   This causes off-by-one errors and underestimation of max_length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug causes failure on inputs where balanced subarray starts at index 0 [OK]

Hint: Initialize prefix sum 0 at index -1 to avoid off-by-one [OK]

Common Mistakes:

• Not initializing prefix sum 0 index
• Confusing prefix sum updates
• Wrong initial values in array

4. What is the time complexity of the optimal two-pointer approach for the Summary Ranges problem on an input list of length n?

medium

A. O(n log n) due to sorting the input before scanning for ranges.

B. O(n²) because the inner while loop can run up to n times for each start pointer.

C. O(n) because each element is visited at most twice by the two pointers combined.

D. O(n) but with O(n) auxiliary space for storing the output ranges.

Solution

1. Step 1: Analyze outer and inner loops

   The outer loop advances start pointer, inner loop advances end pointer; together they move forward without revisiting elements.

2. Step 2: Confirm total iterations

   Each element is visited at most twice (once by start, once by end), so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two pointers linear scan -> O(n) time [OK]

Hint: Two pointers each move forward once -> O(n) time [OK]

Common Mistakes:

• Assuming inner loop restarts fully causing O(n²)
• Confusing sorting cost if input is already sorted
• Ignoring that output space is separate from time complexity

5. Suppose the input array can contain negative numbers and you want to find the number of subarrays whose sum equals k, but now you want to find the count of subarrays with sum divisible by k instead. Which modification to the optimal prefix sum with hash map approach correctly solves this variant?

hard

A. Use a sliding window approach since divisibility allows shrinking the window easily.

B. Track prefix sums modulo k and count frequencies of each remainder in a hash map.

C. Sort the array and use two pointers to find subarrays with sum divisible by k.

D. Use the original prefix sum approach without changes, as sum equals k and sum divisible by k are equivalent.

Solution

1. Step 1: Understand the problem variant

   We want subarrays where sum % k == 0, not sum == k.

2. Step 2: Modify prefix sums to track remainders

   Compute prefix sums modulo k and count how many prefix sums have the same remainder, since difference of prefix sums with same remainder is divisible by k.

3. Step 3: Use hash map to count frequencies of remainders

   Increment count by frequency of current remainder seen so far.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Sliding window fails with negatives; sorting breaks subarray continuity; original approach doesn't handle divisibility. [OK]

Hint: Use prefix sums modulo k and count remainder frequencies [OK]

Common Mistakes:

• Trying sliding window with negatives
• Ignoring modulo operation
• Assuming sum equals k and divisible by k are same