Max Number of K-Sum Pairs

📋

Max Number of K-Sum Pairs

Edge cases:

</>

IDE

def maxOperations(nums: list[int], k: int) -> int:public int maxOperations(int[] nums, int k)int maxOperations(vector<int>& nums, int k)function maxOperations(nums, k)

def maxOperations(nums, k):
    # Write your solution here
    pass

class Solution {
    public int maxOperations(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxOperations(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function maxOperations(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Overcounting pairs by reusing elements multiple timesNot decrementing frequency counts after forming a pair✅ After counting a pair, decrement frequency of both elements: freq[num] -= 1; freq[k - num] -= 1

Wrong: Returning non-zero for empty or single-element arraysNot handling base cases where array length < 2✅ Add checks to return 0 if nums is empty or has only one element

Wrong: Counting pairs that do not sum exactly to kNot verifying sum equals k before counting pairs✅ Only count pairs where num + complement == k

Wrong: TLE on large inputsUsing nested loops (O(n^2)) instead of frequency map (O(n))✅ Implement frequency map counting to achieve O(n) time complexity

✓

Test Cases

Try testing your solution on empty and minimal inputs to catch base case bugs.

Consider tricky cases with duplicates and sums that might trick greedy solutions.

Optimize your solution to linear or linearithmic time to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,2,3,4],"k":5}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Think about how to find pairs that sum to k efficiently.

💡 Use a frequency map to track counts of each number and their complements.

💡 Count pairs by matching each number with k - number and decrement counts accordingly.

Why it failed: Returned incorrect count - likely missed decrementing frequency after pairing. Fix by reducing counts of both elements after forming a pair.

✓ Correctly counts pairs using frequency map and complement logic.

t1_02basic

Input{"nums":[3,1,3,4,3],"k":6}

Expected1

⏱ Performance - must finish in 2000ms

Only one pair (3,3) sums to 6; extra 3s cannot be reused.

💡 Check how duplicates affect pairing when k is twice an element.

💡 Ensure each element is used at most once by tracking frequencies carefully.

💡 Pair only when frequency of complement is positive and decrement both frequencies.

Why it failed: Overcounted pairs by reusing elements multiple times. Fix by decrementing frequency counts after each pair is formed.

✓ Handles duplicates correctly and respects single-use constraint.

t2_01edge

Input{"nums":[],"k":5}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no pairs.

💡 Consider what happens when the input array is empty.

💡 Check if your code handles zero-length arrays without errors.

💡 Return 0 immediately if nums is empty.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty array and returning 0.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[5],"k":5}

Expected0

⏱ Performance - must finish in 2000ms

Single element cannot form a pair.

💡 What if the array has only one element?

💡 Pairs require two elements, so single element arrays yield zero pairs.

💡 Return 0 if length of nums is less than 2.

Why it failed: Returns non-zero for single element input. Fix by ensuring pairs require two distinct elements.

✓ Correctly returns 0 for single element input.

t2_03edge

Input{"nums":[2,2,2,2],"k":4}

Expected2

⏱ Performance - must finish in 2000ms

All elements are the same and k is twice that element; max pairs is floor(4/2)=2.

💡 When all elements are identical and k equals twice that element, how many pairs can form?

💡 Count pairs as floor of frequency divided by 2.

💡 Use integer division of frequency by 2 for such cases.

Why it failed: Incorrectly counts more pairs than possible by reusing elements. Fix by pairing elements only once and using floor division of frequency.

✓ Correctly handles identical elements and counts max pairs.

t2_04edge

Input{"nums":[1,2,3,4,5],"k":10}

Expected0

⏱ Performance - must finish in 2000ms

No two elements sum to 10; output is 0.

💡 Check if your code correctly returns 0 when no pairs sum to k.

💡 Verify that you do not count pairs with sums less or greater than k.

💡 Ensure frequency map lookups only count valid complements.

Why it failed: Returns non-zero count when no pairs sum to k. Fix by verifying sum equals k before counting pairs.

✓ Correctly returns 0 when no pairs sum to k.

t3_01corner

Input{"nums":[1,1,1,1,1],"k":2}

Expected2

⏱ Performance - must finish in 2000ms

Multiple identical elements with k=2; max pairs is floor(5/2)=2.

💡 Beware of greedy approaches that might overcount pairs.

💡 Use frequency counts and decrement after pairing to avoid reuse.

💡 Count pairs as min(freq[num], freq[k-num]) and handle num == k-num carefully.

Why it failed: Greedy approach overcounts pairs by reusing elements. Fix by decrementing frequencies after each pair and handling equal complements correctly.

✓ Handles greedy trap by correct frequency decrementing.

t3_02corner

Input{"nums":[1,2,3,4,5,6],"k":7}

Expected3

⏱ Performance - must finish in 2000ms

Pairs are (1,6), (2,5), (3,4); tests correct pairing without reuse.

💡 Check that each element is used at most once in one pair.

💡 Avoid counting pairs multiple times by careful frequency updates.

💡 Use a single pass frequency map approach to count pairs correctly.

Why it failed: Off-by-one or double counting pairs due to incorrect frequency updates. Fix by decrementing frequencies immediately after pairing.

✓ Correctly counts pairs without reuse or double counting.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7],"k":8}

Expected3

⏱ Performance - must finish in 2000ms

Pairs are (1,7), (2,6), (3,5); tests correct pairing with odd length array.

💡 Ensure no element is reused in multiple pairs.

💡 Check frequency map updates carefully for odd length arrays.

💡 Count pairs by matching complements and decrementing frequencies.

Why it failed: Incorrect pair count due to off-by-one errors in frequency updates. Fix by decrementing frequencies after each pair.

✓ Correctly handles odd length arrays and counts pairs.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":101}

Expected50

⏱ Performance - must finish in 2000ms

n=100, O(n) or O(n log n) solution must complete within 2s; brute force O(n^2) will TLE.

💡 Brute force O(n^2) will time out for n=100.

💡 Use a hash map frequency counting approach for O(n) time.

💡 Avoid nested loops; track frequencies and complements efficiently.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) frequency map solution.

✓ Efficient O(n) or O(n log n) solution confirmed by passing performance test.

Practice

1. Given the following Python code implementing the optimal approach for longest consecutive sequence, what is the value of max_len returned when the input is [1, 9, 3, 10, 4, 20, 2]?

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in num_set:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

easy

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify sequence starts

   Numbers without predecessor: 1 (0 not in set), 9 (8 not in set), 20 (19 not in set).

2. Step 2: Trace sequences from starts

   From 1: sequence is 1,2,3,4 -> length 4; from 9: 9,10 -> length 2; from 20: 20 -> length 1. Max length is 4.

3. Step 3: Re-examine carefully

   Check if 1,2,3,4 is the longest. Actually, 1,2,3,4 is length 4, but 1,2,3,4,5 is not present. So max length is 4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Longest consecutive sequence length is 4 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number
• Off-by-one in length calculation
• Ignoring duplicates

2. What is the time complexity of the optimal hash map with prefix sum remainders approach for the Continuous Subarray Sum problem, assuming the input array length is n and the divisor is k?

medium

A. O(n * k) due to nested loops over array and modulo values

B. O(n^2) because of checking all subarrays implicitly via prefix sums

C. O(n) because each element is processed once and hash map operations are O(1) on average

D. O(k) since the remainder map size is limited by k

Solution

1. Step 1: Analyze the loop and hash map operations

   The algorithm iterates over the array once (O(n)) and performs O(1) average-time hash map lookups and insertions.

2. Step 2: Consider the size of the remainder map

   The remainder map size is at most min(n, k), but this does not increase the iteration count beyond O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) time [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing prefix sums with nested loops
• Assuming modulo k adds multiplicative factor
• Ignoring average O(1) hash map operations

3. What is the time complexity of the optimal sliding window algorithm that uses two frequency arrays and a match count to find all anagrams of p in s?

medium

A. O(n * m), where n = length of s and m = length of p

B. O(n * 26), where n = length of s

C. O(n), where n = length of s

D. O(n + m), where n = length of s and m = length of p

Solution

1. Step 1: Analyze the main loop over string s

   The algorithm slides a window of size m = len(p) over s once, performing O(1) updates per step.

2. Step 2: Consider frequency array operations

   Frequency arrays are fixed size 26, so comparisons and updates are O(1) per iteration, not dependent on m.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window with fixed alphabet size -> O(n) time [OK]

Hint: Fixed alphabet size means frequency ops are O(1) [OK]

Common Mistakes:

• Confusing frequency array size with input size
• Assuming nested loops cause O(n*m)
• Ignoring constant alphabet size

4. Suppose the problem is modified so that elements can be reused multiple times in the subsequence (i.e., indices can be repeated). Which modification to the DP approach correctly handles this variant?

hard

A. Use a recursive memoized solution that tries all possible next elements including the current one

B. Keep the same DP but allow j to equal i in the inner loop to reuse elements

C. Modify DP to track counts per difference but reset dp[i][diff] to 1 each time to allow reuse

D. Use a graph-based BFS to explore sequences allowing repeated nodes

Solution

1. Step 1: Understand reuse means indices can repeat

   Standard DP assumes strictly increasing indices; allowing reuse breaks this assumption.

2. Step 2: Recognize recursive memoization can explore all sequences with repeated elements

   Recursive approach with memoization can try all next elements including current, correctly handling reuse.

3. Step 3: Evaluate other options

   Allowing j == i breaks DP indexing logic; resetting dp[i][diff] loses subsequence length info; BFS is inefficient and complex.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recursive memoization handles repeated indices correctly [OK]

Hint: Reuse requires recursion with memoization, not standard DP indexing [OK]

Common Mistakes:

• Allowing j == i in DP loops breaks monotonic index assumption
• Resetting dp values loses subsequence length info
• Trying BFS which is inefficient

5. Suppose the problem is modified so that elements can be removed multiple times (i.e., you can reuse elements from the ends infinitely) to reduce x to zero. Which approach correctly adapts to this variant?

hard

A. Use a dynamic programming approach to find the minimum number of removals with unlimited reuse, similar to coin change.

B. Apply a greedy approach removing the largest elements repeatedly from ends until x is zero.

C. Use the same sliding window approach on the original array once; it still works without changes.

D. Use prefix and suffix sums with a hash map but ignore overlapping since reuse is allowed.

Solution

1. Step 1: Understand the reuse variant

   Since elements can be reused infinitely, the problem becomes similar to coin change where you want minimum coins (elements) summing to x.

2. Step 2: Recognize sliding window limitation

   Sliding window relies on contiguous subarrays without reuse; it cannot handle infinite reuse.

3. Step 3: Use DP approach

   Dynamic programming can find minimum removals with unlimited reuse by building solutions for all sums up to x.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles reuse, sliding window does not [OK]

Hint: Reuse implies DP coin change pattern [OK]

Common Mistakes:

• Assuming sliding window works with reuse
• Ignoring infinite reuse changes problem nature
• Using greedy which fails on some sums