Max Number of K-Sum Pairs - Practice Coding Problems

Max Number of K-Sum Pairs - 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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: We can form pairs (1,4) and (2,3), both sum to 5. Total operations: 2.

Example 2 — Duplicates

$ Input: nums = [3,1,3,4,3], k = 6

› Output: 1

💡 Note: We can form one pair (3,3) that sums to 6. The remaining elements [1,4,3] cannot form valid pairs.

Example 3 — No Valid Pairs

$ Input: nums = [1,1,1,1], k = 3

› Output: 0

💡 Note: No two elements sum to 3 (1+1=2), so no operations possible.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of numbers and target sum k

Process

Find pairs that sum to k and remove them

Output

Maximum number of operations (pairs removed)

Key Takeaway

🎯 Key Insight: Each number can only be used once, so we need to efficiently count available numbers and match them with their complements.

Asked in

a Amazon 42 f Facebook 38 G Google 31 M Microsoft 25

The key insight is that each number can only be used once, so we need to efficiently track which numbers are available for pairing. The hash map approach is optimal: count frequencies, then for each number find its complement (k - num) and form as many pairs as possible. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all pairs of elements to find those that sum to k
Hash Map (Frequency Count)	O(n)	O(n)	Count frequency of each number and pair them optimally
Two Pointers (After Sorting)	O(n log n)	O(1)	Sort array then use two pointers from ends to find pairs

Brute Force — Algorithm Steps

Step 1: Use nested loops to check all pairs
Step 2: When pair sums to k, mark as used and count operation

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Pairs

Compare each element with every other element

Mark Used

When sum equals k, mark both elements as used

Count Operations

Count successful pair formations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int numsSize, int k) {
    bool* used = (bool*)calloc(numsSize, sizeof(bool));
    int operations = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (used[i]) continue;
        for (int j = i + 1; j < numsSize; j++) {
            if (used[j]) continue;
            if (nums[i] + nums[j] == k) {
                used[i] = used[j] = true;
                operations++;
                break;
            }
        }
    }
    
    free(used);
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all n×n pairs of elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

89.4K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler