Check Array Pairs Divisible by K

▶

Steps

setup

Check if array length is even

The algorithm first checks if the length of nums is even. Since pairing requires two elements per pair, an odd length means immediate failure.

💡 This step quickly eliminates impossible cases, saving computation.

Line:

if len(nums) % 2 != 0:
    return False

💡 Only arrays with even length can be partitioned into pairs.

setup

Initialize empty frequency map

Create an empty hash map to count frequencies of remainders of nums modulo k.

💡 This map will track how many numbers fall into each remainder category.

Line:

freq = {}

💡 Starting with an empty map prepares for frequency counting.

fill_cells

Process first number: 1

Calculate remainder of 1 modulo 5, which is 1, then increment frequency of remainder 1 in the map.

💡 Counting remainder frequencies helps identify pairing possibilities.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 1 count increases to 1.

fill_cells

Process second number: 2

Calculate remainder of 2 modulo 5, which is 2, then increment frequency of remainder 2.

💡 Each number's remainder frequency is tracked to check pairing conditions later.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 2 count increases to 1.

fill_cells

Process third number: 3

Calculate remainder of 3 modulo 5, which is 3, then increment frequency of remainder 3.

💡 Tracking all remainders builds the frequency profile needed for pairing checks.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 3 count increases to 1.

fill_cells

Process fourth number: 4

Calculate remainder of 4 modulo 5, which is 4, then increment frequency of remainder 4.

💡 Each remainder count helps verify if pairs can be formed with complementary remainders.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 4 count increases to 1.

fill_cells

Process fifth number: 5

Calculate remainder of 5 modulo 5, which is 0, then increment frequency of remainder 0.

💡 Remainder 0 is special because pairs must be formed within this group evenly.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 0 count increases to 1.

fill_cells

Process sixth number: 10

Calculate remainder of 10 modulo 5, which is 0, then increment frequency of remainder 0 again.

💡 Incrementing remainder 0 frequency tracks how many numbers are divisible by k.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 0 count increases to 2.

fill_cells

Process seventh number: 6

Calculate remainder of 6 modulo 5, which is 1, then increment frequency of remainder 1.

💡 Updating remainder 1 frequency helps check if it matches remainder 4 frequency later.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 1 count increases to 2.

fill_cells

Process eighth number: 7

Calculate remainder of 7 modulo 5, which is 2, then increment frequency of remainder 2.

💡 Remainder 2 frequency must match remainder 3 frequency for valid pairing.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 2 count increases to 2.

fill_cells

Process ninth number: 8

Calculate remainder of 8 modulo 5, which is 3, then increment frequency of remainder 3.

💡 Remainder 3 frequency must match remainder 2 frequency for valid pairing.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 3 count increases to 2.

fill_cells

Process tenth number: 9

Calculate remainder of 9 modulo 5, which is 4, then increment frequency of remainder 4.

💡 Remainder 4 frequency must match remainder 1 frequency for valid pairing.

Line:

r = ((num % k) + k) % k
freq[r] = freq.get(r, 0) + 1

💡 Remainder 4 count increases to 2.

compare

Check if frequency of remainder 0 is even

Verify that the count of numbers with remainder 0 is even, since they must pair among themselves.

💡 An odd count here means pairing is impossible for remainder 0 group.

Line:

if freq.get(0, 0) % 2 != 0:
    return False

💡 Remainder 0 group can be paired internally.

compare

Check pairs of complementary remainders

For each remainder r (excluding 0), check if freq[r] equals freq[k - r]. This ensures pairs can be formed between complementary remainders.

💡 Matching frequencies of complementary remainders is essential for valid pairing.

Line:

for r in freq:
    if r != 0:
        complement = (k - r) % k
        if freq.get(r, 0) != freq.get(complement, 0):
            return False

💡 Complementary remainder groups can be paired perfectly.

compare

Check if k is even and remainder k/2 frequency is even

Since k=5 is odd, this step is skipped. For even k, remainder k/2 must have even frequency to form pairs.

💡 This condition applies only for even k to ensure pairs within the middle remainder group.

Line:

if k % 2 == 0 and freq.get(k // 2, 0) % 2 != 0:
    return False

💡 No special middle remainder condition applies here.

reconstruct

Return true as all conditions are met

Since all frequency checks passed, the algorithm returns true indicating the array can be paired as required.

💡 The final result confirms the input array meets all pairing criteria.

Line:

return True

💡 The frequency map analysis guarantees valid pairs exist.

def canArrange(nums, k):
    # STEP 1
    if len(nums) % 2 != 0:
        return False
    # STEP 2
    freq = {}
    for num in nums:
        # STEP 3-12
        r = ((num % k) + k) % k  # Adjust modulo for negatives
        freq[r] = freq.get(r, 0) + 1
    # STEP 13
    if freq.get(0, 0) % 2 != 0:
        return False
    # STEP 14
    for r in freq:
        if r != 0:
            complement = (k - r) % k
            if freq.get(r, 0) != freq.get(complement, 0):
                return False
    # STEP 15
    if k % 2 == 0 and freq.get(k // 2, 0) % 2 != 0:
        return False
    # STEP 16
    return True

if __name__ == '__main__':
    print(canArrange([1,2,3,4,5,10,6,7,8,9], 5))  # True

📊

Check Array Pairs Divisible by K - Watch the Algorithm Execute, Step by Step

Watching the algorithm update the frequency map and check conditions step-by-step reveals how modular arithmetic and frequency matching solve the problem efficiently.

check

empty map

insert

empty map

insert

Lookup: 1→ 0

1→1lookup

insert

Lookup: 2→ 0

1→1

2→1lookup

insert

Lookup: 3→ 0

1→1

2→1

3→1lookup

insert

Lookup: 4→ 0

1→1

2→1

3→1

4→1lookup

insert

Lookup: 0→ 0

0→1lookup

1→1

2→1

3→1

4→1

increment

Lookup: 0→ 1

0→2lookup

1→1

2→1

3→1

4→1

increment

Lookup: 1→ 1

0→2

1→2lookup

2→1

3→1

4→1

increment

Lookup: 2→ 1

0→2

1→2

2→2lookup

3→1

4→1

increment

Lookup: 3→ 1

0→2

1→2

2→2

3→2lookup

4→1

increment

Lookup: 4→ 1

0→2

1→2

2→2

3→2

4→2lookup

check

Lookup: 0→ 2

0→2lookup

1→2

2→2

3→2

4→2

check

0→2

1→2

2→2

3→2

4→2

check

0→2

1→2

2→2

3→2

4→2

check

0→2

1→2

2→2

3→2

4→2

Result: true

Key Takeaways

✓ The frequency map of remainders modulo k is the core data structure enabling efficient pairing checks.

It's hard to see from code alone how remainder counts directly relate to pairing feasibility without visualizing the map.

✓ Pairs form between complementary remainders r and k-r, so their frequencies must match exactly.

This insight clarifies why the algorithm checks freq[r] == freq[k-r], which might seem arbitrary without visualization.

✓ Special handling of remainder 0 (and k/2 if k even) ensures pairs within these groups are even in count.

This condition is subtle and easy to overlook in code, but critical for correctness.

Practice

1. Given a string s and a pattern p, you need to find all start indices of p's anagrams in s. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with two frequency counters and a match count to track when all character frequencies match.

B. Brute force checking all substrings of length equal to p and comparing frequency maps each time.

C. Dynamic programming to build a table of substring matches based on previous computations.

D. Greedy approach that tries to match characters from left to right without backtracking.

Solution

1. Step 1: Understand the problem constraints

   We need to find all anagrams of p in s efficiently, which requires checking character frequencies in substrings of length len(p).

2. Step 2: Identify the optimal approach

   Sliding window with two frequency counters and a match count allows updating counts in O(1) per step and checking matches in O(1), leading to O(n) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with match count is known optimal for this problem [OK]

Hint: Sliding window with match count -> O(n) time [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP applicability
• Believing greedy works for anagrams

2. You are given an integer array and two bounds left and right. You need to count the number of contiguous subarrays where the maximum element lies between left and right inclusive. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and use binary search to find valid subarrays within bounds.

B. Use a brute force nested loop to check every subarray and track its maximum.

C. Use a sliding window that expands and contracts based on the current maximum element.

D. Count subarrays with max ≤ right and subtract those with max < left using a single pass.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting subarrays with maximum elements bounded between left and right, which can be done efficiently by counting subarrays with max ≤ right and subtracting those with max < left.

2. Step 2: Identify the optimal approach

   The approach that counts subarrays with max ≤ right and subtracts those with max < left uses a single linear pass and constant space, guaranteeing O(n) time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal linear approach uses subtraction of two counts [OK]

Hint: Subtract counts of subarrays bounded by right and left-1 [OK]

Common Mistakes:

• Assuming sliding window can track max efficiently
• Trying to sort and binary search subarrays
• Using brute force for optimal solution

3. 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

4. The following code attempts to solve the Continuous Subarray Sum problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: updating remainder_map[running_sum] = i before checking condition

B. Line 11: verifying subarray length > 1

C. Line 9: checking if running_sum in remainder_map

D. Line 3: initializing running_sum to 0

Solution

1. Step 1: Understand remainder_map update timing

   The original code updated remainder_map[running_sum] = i before checking if running_sum already exists, overwriting the earliest index.

2. Step 2: Identify consequence of overwriting

   Overwriting earliest index causes missing longer subarrays that satisfy the condition, leading to false negatives.

3. Step 3: Correct the code

   Update remainder_map[running_sum] = i only if running_sum is not already in remainder_map, preserving earliest occurrence.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct code inserts remainder only if not present to preserve earliest index [OK]

Hint: Earliest remainder index must be preserved to find valid subarrays [OK]

Common Mistakes:

• Updating remainder map on every occurrence
• Not checking subarray length >= 2
• Modulo by zero errors

5. 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