Max Number of K-Sum Pairs

▶

Steps

setup

Initialize frequency map and count

Create an empty frequency map to track counts of numbers and initialize the pair count to zero.

💡 Starting with an empty map and zero count sets the stage for tracking pairs efficiently.

Line:

freq = {}
count = 0

💡 The frequency map will store how many times each number is waiting to be paired.

traverse

Process first number: 1

Calculate complement = 5 - 1 = 4. Check if 4 is in freq with count > 0. It's not, so add 1 to freq with count 1.

💡 Since complement 4 is not found, we store 1 to wait for a future complement.

Line:

complement = k - num
if freq.get(complement, 0) > 0:
    ...
else:
    freq[num] = freq.get(num, 0) + 1

💡 Numbers are added to the map when their complement hasn't appeared yet.

traverse

Process second number: 2

Calculate complement = 5 - 2 = 3. Complement 3 not in freq, so add 2 with count 1.

💡 2 is stored waiting for a 3 to form a pair later.

Line:

complement = k - num
if freq.get(complement, 0) > 0:
    ...
else:
    freq[num] = freq.get(num, 0) + 1

💡 The map now tracks 1 and 2 waiting for their complements.

traverse

Process third number: 3

Calculate complement = 5 - 3 = 2. Complement 2 found with count 1, so decrement 2's count and increment pair count.

💡 Finding complement 2 means a pair (2,3) is formed and removed from waiting list.

Line:

complement = k - num
if freq.get(complement, 0) > 0:
    count += 1
    freq[complement] -= 1
else:
    freq[num] = freq.get(num, 0) + 1

💡 Pairs are counted by matching current number with a waiting complement.

traverse

Process fourth number: 4

Calculate complement = 5 - 4 = 1. Complement 1 found with count 1, decrement 1's count and increment pair count.

💡 Complement 1 found means pair (1,4) is formed and removed from waiting list.

Line:

complement = k - num
if freq.get(complement, 0) > 0:
    count += 1
    freq[complement] -= 1
else:
    freq[num] = freq.get(num, 0) + 1

💡 The last pair completes the total count of pairs summing to k.

reconstruct

End of iteration, return count

All numbers processed. Return the total count of pairs found, which is 2.

💡 Returning the count completes the algorithm, showing how many pairs sum to k.

Line:

return count

💡 The final count reflects the maximum number of k-sum pairs.

prune

Extra step: Confirm no leftover frequencies

Verify that no numbers remain waiting to be paired in the frequency map.

💡 Ensuring no leftover frequencies confirms all possible pairs were counted.

Line:

# implicit check after loop

💡 All frequencies are zero or removed, meaning no unmatched numbers remain.

finalize

Summary: Final frequency map empty

The frequency map is empty, and the total count of pairs is 2, the final answer.

💡 An empty map means all numbers were paired successfully.

Line:

# final return

💡 The algorithm efficiently pairs numbers by tracking frequencies and complements.

fill_cells

Optional: Visualize intermediate map states for clarity

Revisit the map states after each insertion and pairing to reinforce understanding.

💡 Seeing intermediate states helps solidify how the map evolves.

Line:

# visualization only, no code change

💡 The map entries reflect the algorithm's logic of waiting and pairing.

finalize

Wrap-up: Algorithm complete with answer 2

The algorithm has finished processing all numbers and returns the maximum number of k-sum pairs: 2.

💡 The final step confirms the answer and the algorithm's correctness.

Line:

return count

💡 The frequency map approach efficiently finds pairs without sorting or nested loops.

def maxOperations(nums, k):
    freq = {}  # STEP 1: Initialize frequency map
    count = 0  # STEP 1: Initialize count
    for num in nums:  # STEP 2-5: Process each number
        complement = k - num  # STEP 2-5: Calculate complement
        if freq.get(complement, 0) > 0:  # STEP 4: Check complement in freq
            count += 1  # STEP 4: Increment count on hit
            freq[complement] -= 1  # STEP 4: Decrement complement count
        else:
            freq[num] = freq.get(num, 0) + 1  # STEP 3: Insert num on miss
    return count  # STEP 6: Return total pairs

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

📊

Max Number of K-Sum Pairs - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how frequency tracking enables efficient pairing without sorting or nested loops.

insert

empty map

Result: 0

insert

Lookup: 4→ 0

1→1

Result: 0

insert

Lookup: 3→ 0

1→1

2→1

Result: 0

lookup

Lookup: 2→ 1

1→1

2→0lookup

Result: 1

lookup

Lookup: 1→ 1

1→0lookup

2→0

Result: 2

check

1→0

2→0

Result: 2

check

empty map

Result: 2

check

empty map

Result: 2

check

empty map

Result: 2

check

empty map

Result: 2

Key Takeaways

✓ Tracking frequencies of numbers allows pairing complements efficiently without sorting.

This insight is hard to see from code alone because the map updates and pair counting happen simultaneously and implicitly.

✓ Each number is either paired immediately if its complement exists or stored waiting for a future complement.

Visualizing the map entries clarifies how the algorithm decides to pair or store numbers.

✓ Decrementing the complement's count upon pairing ensures no double counting of pairs.

The trace shows exactly when and why counts are decremented, which is subtle in code but clear visually.

Practice

1. Consider the following code snippet implementing the optimal sliding window approach to find all anagrams of p in s. Given s = "abab" and p = "ab", what is the content of res after the loop completes?

easy

A. [0, 2]

B. [0, 1, 2]

C. [1, 2]

D. [0, 1]

Solution

1. Step 1: Initialize frequency counts for p = "ab" and first window in s = "ab"

   p_count and s_count both have counts for 'a' and 'b' as 1, so matches = 26 initially except for other letters.

2. Step 2: Slide window over s and update res

   At r=2, window is "ba" starting at index 1, matches == 26, append 0. At r=3, window is "ab" starting at index 2, matches == 26, append 1. After loop, append last index 2 if matches == 26. Final res = [0,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches found at indices 0 and 1 for "ab" and "ba" [OK]

Hint: Sliding window updates res at matches == 26 [OK]

Common Mistakes:

• Off-by-one errors in appending indices
• Forgetting last window check
• Miscounting matches after updates

2. You are given a sorted list of unique integers and need to summarize consecutive sequences as ranges (e.g., [0,1,2,4,5,7] -> ['0->2','4->5','7']). Which approach guarantees an optimal O(n) time solution with minimal extra space?

easy

A. Using two pointers to scan the list once, expanding the end pointer while consecutive numbers continue, then recording ranges.

B. Using nested loops to check every possible range start and end, appending ranges when sequences break.

C. Using dynamic programming to store the longest consecutive subsequence ending at each index and reconstruct ranges.

D. Using a greedy approach that picks the next number if it is consecutive, otherwise starts a new range, but restarts scanning from the beginning each time.

Solution

1. Step 1: Understand the problem constraints

   The input is sorted and unique, so consecutive sequences can be detected by checking if nums[end + 1] == nums[end] + 1.

2. Step 2: Identify the optimal approach

   Two pointers allow a single pass: one pointer marks the start of a range, the other expands until the sequence breaks, then record the range and move start pointer forward.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers scan once -> O(n) time and O(n) space for output [OK]

Hint: Two pointers scan sorted list once for consecutive ranges [OK]

Common Mistakes:

• Thinking nested loops are necessary
• Confusing DP with this linear scan
• Restarting scan repeatedly wastes time

3. What is the time complexity of the optimal prefix sum with hash map solution for the Subarray Sum Equals K problem, given an input array of length n?

medium

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

B. O(n) for iteration plus O(n) for prefix sum storage, total O(n) space and time

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n^2) due to nested loops over the array

Solution

1. Step 1: Identify main operations

   The algorithm iterates over the array once, updating running_sum and hash map counts.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are O(1) on average, so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) time complexity. [OK]

Hint: Hash map lookups are average O(1), not O(log n) [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming hash map operations are O(log n)
• Counting prefix sum storage as extra time

4. The following code attempts to implement summaryRanges but has a subtle bug. Which line contains the bug?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

medium

A. Line 7: The inner while loop condition misses the last element in some cases.

B. Line 4: Not checking if input list is empty causes crash on empty input.

C. Line 11: Updating start to end + 1 might skip elements if end is not updated correctly.

D. Line 9: Always appending 'start->end' even when start == end causes incorrect output for single elements.

Solution

1. Step 1: Identify output format issue

   When start == end, the code appends 'num->num' instead of just 'num', which is incorrect per problem spec.

2. Step 2: Confirm other lines are correct

   Inner loop condition and start update are correct; empty input handling is not shown but not the subtle bug here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single element ranges must be output as single numbers, not ranges [OK]

Hint: Single element ranges output as 'num', not 'num->num' [OK]

Common Mistakes:

• Appending 'start->end' even when start == end
• Off-by-one in inner loop
• Skipping last range due to loop condition

5. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best