Solution Approach

The solution uses a hash table combined with enumeration to efficiently count valid triplets.

Data Structure:

• cnt: A hash table (defaultdict) that stores the count of remainders. Specifically, cnt[r] represents how many elements we've processed so far that have remainder r when divided by d.

Algorithm Steps:

1. Initialize an empty hash table cnt and set ans = 0 to track the total count of valid triplets.

2. Iterate through the array with index j from 0 to n-1:

   • For each j, this element will serve as the middle element of our triplet

3. For each fixed j, iterate through all elements after it with index k from j+1 to n-1:

   • Calculate the sum (nums[j] + nums[k]) % d
   • Determine what remainder we need from nums[i] to make the total sum divisible by d:
     • x = (d - (nums[j] + nums[k]) % d) % d
     • The outer modulo operation handles the case when (nums[j] + nums[k]) % d = 0, ensuring x = 0 instead of x = d
   • Add cnt[x] to the answer, which represents how many valid i indices exist for this (j, k) pair

4. After processing all k values for the current j, update the hash table:

   • Add nums[j] % d to the hash table by incrementing cnt[nums[j] % d] += 1
   • This makes nums[j] available as a potential i value for future iterations

Why this works:

• When we're at position j, all elements before j (indices 0 to j-1) have already been recorded in the hash table
• These are exactly the valid candidates for index i since we need i < j
• By checking all k > j and looking up the required remainder in our hash table, we count all valid triplets with j as the middle element
• The order i < j < k is naturally maintained by this approach

Time Complexity: O(n²) - two nested loops Space Complexity: O(d) - the hash table can store at most d different remainders

Example Walkthrough

Let's walk through the solution with a concrete example:

• nums = [3, 3, 4, 7, 8]
• d = 5

We need to find triplets (i, j, k) where i < j < k and (nums[i] + nums[j] + nums[k]) % 5 == 0.

Initial State:

• cnt = {} (empty hash table)
• ans = 0

Iteration 1: j = 0 (nums[j] = 3)

• Check all k > 0:
  • k = 1: nums[k] = 3
    • Sum needed: (3 + 3) % 5 = 6 % 5 = 1
    • Required remainder: x = (5 - 1) % 5 = 4
    • cnt[4] = 0 (no elements with remainder 4 seen yet)
    • ans += 0
  • k = 2: nums[k] = 4
    • Sum needed: (3 + 4) % 5 = 7 % 5 = 2
    • Required remainder: x = (5 - 2) % 5 = 3
    • cnt[3] = 0 (no elements with remainder 3 seen yet)
    • ans += 0
  • k = 3: nums[k] = 7
    • Sum needed: (3 + 7) % 5 = 10 % 5 = 0
    • Required remainder: x = (5 - 0) % 5 = 0
    • cnt[0] = 0 (no elements with remainder 0 seen yet)
    • ans += 0
  • k = 4: nums[k] = 8
    • Sum needed: (3 + 8) % 5 = 11 % 5 = 1
    • Required remainder: x = (5 - 1) % 5 = 4
    • cnt[4] = 0
    • ans += 0
• Update hash table: 3 % 5 = 3, so cnt[3] = 1
• Current state: cnt = {3: 1}, ans = 0

Iteration 2: j = 1 (nums[j] = 3)

• Check all k > 1:
  • k = 2: nums[k] = 4
    • Sum needed: (3 + 4) % 5 = 2
    • Required remainder: x = (5 - 2) % 5 = 3
    • cnt[3] = 1 (we have one element with remainder 3: nums[0])
    • ans += 1 (found triplet: i=0, j=1, k=2)
  • k = 3: nums[k] = 7
    • Sum needed: (3 + 7) % 5 = 0
    • Required remainder: x = (5 - 0) % 5 = 0
    • cnt[0] = 0
    • ans += 0
  • k = 4: nums[k] = 8
    • Sum needed: (3 + 8) % 5 = 1
    • Required remainder: x = (5 - 1) % 5 = 4
    • cnt[4] = 0
    • ans += 0
• Update hash table: 3 % 5 = 3, so cnt[3] = 2
• Current state: cnt = {3: 2}, ans = 1

Iteration 3: j = 2 (nums[j] = 4)

• Check all k > 2:
  • k = 3: nums[k] = 7
    • Sum needed: (4 + 7) % 5 = 11 % 5 = 1
    • Required remainder: x = (5 - 1) % 5 = 4
    • cnt[4] = 0
    • ans += 0
  • k = 4: nums[k] = 8
    • Sum needed: (4 + 8) % 5 = 12 % 5 = 2
    • Required remainder: x = (5 - 2) % 5 = 3
    • cnt[3] = 2 (we have two elements with remainder 3: nums[0] and nums[1])
    • ans += 2 (found triplets: i=0, j=2, k=4 and i=1, j=2, k=4)
• Update hash table: 4 % 5 = 4, so cnt[4] = 1
• Current state: cnt = {3: 2, 4: 1}, ans = 3

Iteration 4: j = 3 (nums[j] = 7)

• Check all k > 3:
  • k = 4: nums[k] = 8
    • Sum needed: (7 + 8) % 5 = 15 % 5 = 0
    • Required remainder: x = (5 - 0) % 5 = 0
    • cnt[0] = 0
    • ans += 0
• Update hash table: 7 % 5 = 2, so cnt[2] = 1
• Current state: cnt = {3: 2, 4: 1, 2: 1}, ans = 3

Iteration 5: j = 4 (nums[j] = 8)

• No k > 4 exists, so no pairs to check
• Update hash table: 8 % 5 = 3, so cnt[3] = 3

Final Answer: 3

The three valid triplets are:

1. (0, 1, 2): nums[0] + nums[1] + nums[2] = 3 + 3 + 4 = 10, which is divisible by 5
2. (0, 2, 4): nums[0] + nums[2] + nums[4] = 3 + 4 + 8 = 15, which is divisible by 5
3. (1, 2, 4): nums[1] + nums[2] + nums[4] = 3 + 4 + 8 = 15, which is divisible by 5

Time and Space Complexity

Time Complexity: O(n²)

The code contains two nested loops:

• The outer loop iterates through j from 0 to n-1, running n times
• The inner loop iterates through k from j+1 to n-1, running approximately n-j-1 times for each j
• The total iterations across both loops is (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2, which simplifies to O(n²)
• Inside the inner loop, all operations (modulo calculation, dictionary lookup, and addition) are O(1)
• After the inner loop, the dictionary update operation is also O(1)

Therefore, the overall time complexity is O(n²).

Space Complexity: O(n)

The space usage comes from:

• The cnt dictionary (defaultdict) which stores the count of remainders when elements are divided by d
• Since d is a constant and each element's remainder when divided by d can only be in the range [0, d-1], the dictionary can have at most min(n, d) unique keys
• In the worst case where all elements have different remainders or d ≥ n, the dictionary can store up to n entries
• Other variables (ans, n, j, k, x) use constant space O(1)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Remainder Calculation

One of the most common mistakes is incorrectly calculating the required remainder for nums[i].

Pitfall Code:

# WRONG: This fails when (nums[j] + nums[k]) % d == 0
required_remainder = d - (nums[j] + nums[k]) % d

Issue: When (nums[j] + nums[k]) % d == 0, this formula gives required_remainder = d, but we actually need required_remainder = 0 since we're looking for elements with remainder 0.

Solution:

# CORRECT: The outer modulo ensures we get 0 instead of d
required_remainder = (d - (nums[j] + nums[k]) % d) % d

2. Updating Hash Table at Wrong Time

Another critical mistake is updating the hash table at the wrong point in the iteration.

Pitfall Code:

for j in range(n):
    # WRONG: Adding nums[j] to hash table BEFORE checking k values
    remainder_count[nums[j] % d] += 1

    for k in range(j + 1, n):
        required_remainder = (d - (nums[j] + nums[k]) % d) % d
        result += remainder_count[required_remainder]

Issue: This would count invalid triplets where i == j, violating the constraint i < j < k.

Solution:

for j in range(n):
    for k in range(j + 1, n):
        required_remainder = (d - (nums[j] + nums[k]) % d) % d
        result += remainder_count[required_remainder]

    # CORRECT: Add nums[j] AFTER processing all k values
    remainder_count[nums[j] % d] += 1

3. Using Regular Dictionary Instead of DefaultDict

Using a regular dictionary without proper initialization can cause KeyError.

Pitfall Code:

remainder_count = {}  # Regular dictionary
# ...
result += remainder_count[required_remainder]  # KeyError if key doesn't exist

Solution:

# Option 1: Use defaultdict
from collections import defaultdict
remainder_count = defaultdict(int)

# Option 2: Use get() method with default value
remainder_count = {}
result += remainder_count.get(required_remainder, 0)

4. Handling Negative Numbers Incorrectly

If the array contains negative numbers, the modulo operation in Python handles them correctly, but it's important to understand the behavior.

Example: For d = 5 and nums[j] + nums[k] = -3:

• Python's (-3) % 5 returns 2 (not -3)
• The required remainder calculation still works correctly

Best Practice: Always test with negative numbers to ensure your solution handles them properly.