Longest Subarray with Sum Divisible by K

▶

Steps

setup

Initialize earliest array and variables

Create an array 'earliest' of size k initialized with -2 to mark unseen remainders. Set earliest[0] = -1 to represent prefix sum remainder 0 before starting. Initialize max_length and prefix_sum to 0.

💡 This setup allows us to track the earliest index where each remainder appears, which is key to finding subarrays divisible by k.

Line:

earliest = [-2] * k
earliest[0] = -1
max_length = 0
prefix_sum = 0

💡 We prepare to record the earliest occurrence of each remainder to quickly find subarray lengths later.

traverse

Process first number: 2

Add nums[0] = 2 to prefix_sum, prefix_sum becomes 2. Compute remainder = 2 % 3 = 2. Check if remainder 2 was seen before in earliest array.

💡 Calculating remainder helps us identify if a subarray sum divisible by k ends here.

Line:

prefix_sum += num
remainder = prefix_sum % k

💡 We find the remainder of the prefix sum to check if this remainder appeared before.

insert

Store earliest index for remainder 2

Since remainder 2 was not seen before (value is -2), store current index 0 as earliest occurrence for remainder 2.

💡 Recording earliest index for a remainder lets us calculate subarray lengths later if we see this remainder again.

Line:

earliest[remainder] = i

💡 Earliest occurrence of remainder 2 is index 0, marking start of potential subarrays.

traverse

Process second number: 7

Add nums[1] = 7 to prefix_sum, prefix_sum becomes 9. Compute remainder = 9 % 3 = 0. Check if remainder 0 was seen before.

💡 A remainder of 0 means the prefix sum itself is divisible by k, potentially a subarray from start.

Line:

prefix_sum += num
remainder = prefix_sum % k

💡 We check if remainder 0 appeared before to find subarray length.

compare

Update max_length for remainder 0 hit

Remainder 0 was seen before at index -1. Calculate subarray length = current index 1 - (-1) = 2. Update max_length from 0 to 2.

💡 Finding a previously seen remainder means the subarray between those indices sums to a multiple of k.

Line:

max_length = max(max_length, i - earliest[remainder])

💡 We found a longer subarray divisible by k ending at index 1.

traverse

Process third number: 6

Add nums[2] = 6 to prefix_sum, prefix_sum becomes 15. Compute remainder = 15 % 3 = 0. Check if remainder 0 was seen before.

💡 Again remainder 0 means prefix sum divisible by k, check for subarray length update.

Line:

prefix_sum += num
remainder = prefix_sum % k

💡 We check remainder 0 to find if a longer subarray exists.

compare

Update max_length for remainder 0 hit again

Remainder 0 seen before at index -1. Calculate subarray length = 2 - (-1) = 3. Update max_length from 2 to 3.

💡 Longer subarray found ending at index 2 with sum divisible by k.

Line:

max_length = max(max_length, i - earliest[remainder])

💡 max_length grows as we find longer valid subarrays.

traverse

Process fourth number: 1

Add nums[3] = 1 to prefix_sum, prefix_sum becomes 16. Compute remainder = 16 % 3 = 1. Check if remainder 1 was seen before.

💡 New remainder means we may need to store earliest index for remainder 1.

Line:

prefix_sum += num
remainder = prefix_sum % k

💡 We check if remainder 1 is new or seen before.

insert

Store earliest index for remainder 1

Remainder 1 not seen before, store current index 3 as earliest occurrence for remainder 1.

💡 Recording earliest index for remainder 1 allows future subarray length calculations.

Line:

earliest[remainder] = i

💡 Earliest occurrence of remainder 1 is index 3.

traverse

Process fifth number: 4

Add nums[4] = 4 to prefix_sum, prefix_sum becomes 20. Compute remainder = 20 % 3 = 2. Check if remainder 2 was seen before.

💡 Remainder 2 seen before at index 0, so we can calculate subarray length.

Line:

prefix_sum += num
remainder = prefix_sum % k

💡 We check remainder 2 to find if a longer subarray exists.

compare

Update max_length for remainder 2 hit

Remainder 2 seen before at index 0. Calculate subarray length = 4 - 0 = 4. Update max_length from 3 to 4.

💡 Found a longer subarray [7,6,1,4] with sum divisible by k.

Line:

max_length = max(max_length, i - earliest[remainder])

💡 max_length updated to longest subarray length found so far.

traverse

Process sixth number: 5

Add nums[5] = 5 to prefix_sum, prefix_sum becomes 25. Compute remainder = 25 % 3 = 1. Check if remainder 1 was seen before.

💡 Remainder 1 seen before at index 3, check for subarray length update.

Line:

prefix_sum += num
remainder = prefix_sum % k

💡 Check remainder 1 to update max_length if possible.

compare

Update max_length for remainder 1 hit

Remainder 1 seen before at index 3. Calculate subarray length = 5 - 3 = 2. max_length remains 4 as 2 < 4.

💡 Subarray length 2 is shorter than current max_length, so no update.

Line:

max_length = max(max_length, i - earliest[remainder])

💡 Not all hits increase max_length; only longer subarrays update it.

reconstruct

Return final max_length

All numbers processed. Return max_length = 4 as the length of the longest subarray with sum divisible by k.

💡 The algorithm outputs the longest valid subarray length found during iteration.

Line:

return max_length

💡 max_length holds the final answer after processing all elements.

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k  # STEP 1
    earliest[0] = -1    # STEP 1
    max_length = 0      # STEP 1
    prefix_sum = 0      # STEP 1
    for i, num in enumerate(nums):  # STEP 2 onwards
        prefix_sum += num          # STEP 2,4,6,8,10,12
        remainder = prefix_sum % k # STEP 2,4,6,8,10,12
        if remainder < 0:          # (not triggered here)
            remainder += k
        if earliest[remainder] != -2:  # STEP 5,7,11,13
            max_length = max(max_length, i - earliest[remainder])  # STEP 5,7,11,13
        else:
            earliest[remainder] = i  # STEP 3,9
    return max_length  # STEP 14

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

📊

Longest Subarray with Sum Divisible by K - Watch the Algorithm Execute, Step by Step

Watching each step reveals how prefix sums and remainders help identify subarrays efficiently without checking every subarray explicitly.

insert

0→-1

1→-2

2→-2

Result: 0

check

Lookup: 2→ -2

0→-1

1→-2

2→-2lookup

Result: 0

insert

Lookup: 2→ -2

0→-1

1→-2

2→0lookup

Result: 0

check

Lookup: 0→ -1

0→-1lookup

1→-2

2→0

Result: 0

lookup

Lookup: 0→ -1

0→-1lookup

1→-2

2→0

Result: 2

check

Lookup: 0→ -1

0→-1lookup

1→-2

2→0

Result: 2

lookup

Lookup: 0→ -1

0→-1lookup

1→-2

2→0

Result: 3

check

Lookup: 1→ -2

0→-1

1→-2lookup

2→0

Result: 3

insert

Lookup: 1→ -2

0→-1

1→3lookup

2→0

Result: 3

check

Lookup: 2→ 0

0→-1

1→3

2→0lookup

Result: 3

lookup

Lookup: 2→ 0

0→-1

1→3

2→0lookup

Result: 4

check

Lookup: 1→ 3

0→-1

1→3lookup

2→0

Result: 4

lookup

Lookup: 1→ 3

0→-1

1→3lookup

2→0

Result: 4

check

0→-1

1→3

2→0

Result: 4

Key Takeaways

✓ Tracking earliest occurrence of each remainder lets us find subarrays divisible by k in O(n) time.

Without visualization, it's hard to see how prefix sums and remainders map to subarray lengths efficiently.

✓ A remainder hit means the subarray between earliest index and current index sums to a multiple of k.

This insight explains why we update max_length only on remainder hits, not misses.

✓ Not all remainder hits increase max_length; only when the subarray length is longer than current max_length.

This clarifies why max_length sometimes stays the same despite multiple hits.

Practice

1. You are given an integer array and a target sum k. You need to find the number of continuous subarrays whose sum equals k. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a sliding window technique to expand and shrink the window until the sum matches k.

B. Use nested loops to check all subarrays and sum their elements to count matches.

C. Use dynamic programming to store sums of all subarrays and count those equal to k.

D. Use prefix sums combined with a hash map to track frequencies of prefix sums and count valid subarrays in one pass.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting continuous subarrays summing to k efficiently.

2. Step 2: Evaluate approaches

   Sliding window (A) fails with negative numbers. Nested loops (D) are correct but O(n²). DP (C) is inefficient here. Prefix sum + hash map (B) tracks prefix sums and counts in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + hash map is the classic O(n) solution [OK]

Hint: Prefix sums + hash map handles negatives and counts efficiently [OK]

Common Mistakes:

• Assuming sliding window works with negative numbers
• Confusing DP with prefix sums
• Using nested loops for optimality

2. What is the time complexity of the optimal character frequency counting approach for grouping anagrams, given n strings each of length k?

medium

A. O(n * k log k)

B. O(n^2 * k log k)

C. O(n * k)

D. O(n * k^2)

Solution

1. Step 1: Identify loops in the algorithm

   Outer loop runs n times, inner loop counts characters in each string of length k.

2. Step 2: Analyze operations inside loops

   Counting frequency is O(k), creating tuple key is O(26) constant, appending to map is O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(n * k) [OK]

Hint: Frequency counting is linear in string length [OK]

Common Mistakes:

• Confusing sorting cost with counting
• Assuming k log k due to sorting
• Mistaking quadratic complexity

3. Consider the following buggy code for detecting if a number is happy. Which line contains the subtle bug that can cause incorrect results or infinite loops?

def sum_of_squares(num):
    return sum(int(d) ** 2 for d in str(num))

UNHAPPY_CYCLE = {4, 16, 37, 58, 89, 145, 42, 20}

def isHappy(n: int) -> bool:
    while n != 1 and n not in UNHAPPY_CYCLE:
        n = sum_of_squares(n)
    return true

medium

A. Line 8: return true statement

B. Line 6: while loop condition

C. Line 2: sum_of_squares function implementation

D. Line 7: updating n with sum_of_squares(n)

Solution

1. Step 1: Analyze return statement

   The function returns true unconditionally after loop ends, ignoring if n is in unhappy cycle.

2. Step 2: Identify correct return logic

   Should return n == 1 to distinguish happy from unhappy numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect return causes false positives [OK]

Hint: Return must check if n == 1 after loop [OK]

Common Mistakes:

• Returning true always after loop
• Ignoring unhappy cycle detection

4. What is the average time complexity of the remove operation in the optimal Insert Delete GetRandom data structure that uses a hash map and an array with the swap-delete trick?

medium

A. O(n), because removing an element requires shifting elements in the array

B. O(log n), because hash map operations take logarithmic time on average

C. O(1), because swapping with the last element and updating the hash map takes constant time

D. O(1) amortized, but worst-case O(n) due to occasional resizing of the array

Solution

1. Step 1: Identify operations in remove

   Remove finds index in O(1) via hash map, swaps with last element, updates hash map, and pops last element.

2. Step 2: Analyze time per step

   All steps are O(1) average time; no shifting of elements occurs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Swap-delete avoids O(n) shifting, ensuring O(1) remove [OK]

Hint: Swap-delete avoids shifting, so remove is O(1) [OK]

Common Mistakes:

• Assuming array remove requires shifting O(n)
• Confusing hash map average O(1) with O(log n)
• Ignoring that resizing is amortized and rare

5. Suppose the input strings can contain uppercase letters and digits in addition to lowercase letters. Which modification to the optimal frequency counting approach correctly handles this scenario?

hard

A. Use a frequency array of size 62 (26 lowercase + 26 uppercase + 10 digits) and map characters accordingly.

B. Use a frequency array of size 26 and convert all characters to lowercase before counting.

C. Sort each string and use the sorted string as the hash map key.

D. Use a hash map with character counts stored as a dictionary instead of an array.

Solution

1. Step 1: Identify character set

   Input includes lowercase, uppercase, and digits, total 62 distinct characters.

2. Step 2: Adjust frequency counting

   Frequency array size must be 62, mapping each character to an index to count correctly.

3. Step 3: Evaluate alternatives

   Converting to lowercase loses information, sorting is slower, dictionary counts add overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency array size matches character set size [OK]

Hint: Frequency array size must cover all possible characters [OK]

Common Mistakes:

• Lowercasing loses info
• Using smaller array size
• Assuming sorting is always best