Problem Description

You are given an integer array arr and an integer target. Your task is to find the number of triplets (i, j, k) where the indices satisfy i < j < k and the sum arr[i] + arr[j] + arr[k] equals the target.

Since the count of such triplets can be very large, you need to return the result modulo 10^9 + 7.

The solution uses a counting approach with enumeration. It maintains a counter cnt to track the frequency of each element in the array. For each middle element arr[j], it first decrements the count of that element, then looks at all elements before position j as potential first elements arr[i]. For each pair (arr[i], arr[j]), it calculates what the third element c should be (c = target - arr[i] - arr[j]) and adds the count of c in the remaining elements to the answer. This ensures we only count valid triplets where i < j < k.

Intuition

The key insight is that we need to count triplets with a specific ordering constraint i < j < k. A naive approach would check all possible triplets, but that would be O(n³) which is too slow.

Instead, we can fix the middle element and think about the problem differently. If we fix the middle element arr[j], we need to find pairs where one element comes before j and one comes after j that sum up to target - arr[j].

The clever part is using a frequency counter. We start with a counter containing all elements. As we iterate through the array and fix each element as the middle element arr[j], we first remove it from the counter (decrement its count). This ensures that when we look for the third element, we're only considering elements that come after position j.

For each element arr[i] that comes before j, we know exactly what the third element needs to be: c = target - arr[i] - arr[j]. The counter tells us how many such elements exist after position j. By adding cnt[c] to our answer, we're counting all valid triplets with arr[i] as the first element, arr[j] as the middle element, and any occurrence of c after j as the third element.

This approach reduces the complexity to O(n²) because for each of the n middle positions, we check all previous elements, and the counter lookup is O(1).

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation uses a counting and enumeration strategy with the following steps:

1. Initialize the counter: Create a Counter object cnt that stores the frequency of each element in the array arr. Since the problem constraints limit values to the range [0, 100], we could also use an array of size 101.

2. Set up the modulo value: Define mod = 10^9 + 7 for the final result calculation.

3. Enumerate the middle element: Iterate through the array with index j and value b = arr[j]. This element will serve as the middle element of our triplet.

4. Update the counter: Before looking for matching pairs, decrement cnt[b] by 1. This crucial step ensures that when we search for the third element, we only count elements that appear after position j.

5. Enumerate the first element: For each middle element arr[j], iterate through all elements before it (arr[:j]). Each of these elements a = arr[i] can potentially be the first element of a valid triplet.

6. Calculate the required third element: For each pair (a, b), calculate what the third element must be: c = target - a - b.

7. Count valid triplets: Add cnt[c] to the answer. This represents the number of times value c appears after position j, giving us all valid triplets with first element a, middle element b, and third element c.

8. Apply modulo operation: After each addition, apply the modulo operation ans = (ans + cnt[c]) % mod to prevent integer overflow.

9. Return the result: After processing all possible middle elements and their corresponding pairs, return the final answer.

The time complexity is O(n²) where n is the length of the array, as we have nested loops iterating through the array. The space complexity is O(1) if we consider the counter size as constant (since values are limited to range [0, 100]), or O(n) if we consider the general case.

Example Walkthrough

Let's walk through a concrete example with arr = [1, 1, 2, 2, 3] and target = 6.

Initial Setup:

• Create counter: cnt = {1: 2, 2: 2, 3: 1}
• Initialize ans = 0

Iteration 1: j=0, arr[j]=1 (first middle element)

• Decrement counter: cnt = {1: 1, 2: 2, 3: 1}
• No elements before j=0, so no pairs to check
• Move to next iteration

Iteration 2: j=1, arr[j]=1 (second middle element)

• Decrement counter: cnt = {1: 0, 2: 2, 3: 1}
• Check element before j=1: arr[0]=1
  • Calculate needed third element: c = 6 - 1 - 1 = 4
  • Check counter: cnt[4] = 0
  • Add to answer: ans = 0 + 0 = 0

Iteration 3: j=2, arr[j]=2 (third middle element)

• Decrement counter: cnt = {1: 0, 2: 1, 3: 1}
• Check elements before j=2:
  • For arr[0]=1: c = 6 - 1 - 2 = 3, cnt[3] = 1, ans = 0 + 1 = 1
  • For arr[1]=1: c = 6 - 1 - 2 = 3, cnt[3] = 1, ans = 1 + 1 = 2

Iteration 4: j=3, arr[j]=2 (fourth middle element)

• Decrement counter: cnt = {1: 0, 2: 0, 3: 1}
• Check elements before j=3:
  • For arr[0]=1: c = 6 - 1 - 2 = 3, cnt[3] = 1, ans = 2 + 1 = 3
  • For arr[1]=1: c = 6 - 1 - 2 = 3, cnt[3] = 1, ans = 3 + 1 = 4
  • For arr[2]=2: c = 6 - 2 - 2 = 2, cnt[2] = 0, ans = 4 + 0 = 4

Iteration 5: j=4, arr[j]=3 (fifth middle element)

• Decrement counter: cnt = {1: 0, 2: 0, 3: 0}
• Check elements before j=4:
  • For arr[0]=1: c = 6 - 1 - 3 = 2, cnt[2] = 0, ans = 4 + 0 = 4
  • For arr[1]=1: c = 6 - 1 - 3 = 2, cnt[2] = 0, ans = 4 + 0 = 4
  • For arr[2]=2: c = 6 - 2 - 3 = 1, cnt[1] = 0, ans = 4 + 0 = 4
  • For arr[3]=2: c = 6 - 2 - 3 = 1, cnt[1] = 0, ans = 4 + 0 = 4

Final Result: The function returns 4.

The valid triplets found are:

• (0, 2, 4): arr[0]=1, arr[2]=2, arr[4]=3 → 1+2+3=6
• (1, 2, 4): arr[1]=1, arr[2]=2, arr[4]=3 → 1+2+3=6
• (0, 3, 4): arr[0]=1, arr[3]=2, arr[4]=3 → 1+2+3=6
• (1, 3, 4): arr[1]=1, arr[3]=2, arr[4]=3 → 1+2+3=6

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the length of the array arr. This is because:

• The outer loop iterates through each element in arr, running n times
• For each iteration j, the inner loop iterates through all elements before index j, which ranges from 0 to n-1 elements
• The total number of operations is 0 + 1 + 2 + ... + (n-1) = n(n-1)/2, which simplifies to O(n²)
• The Counter lookup cnt[c] and Counter update cnt[b] -= 1 operations are both O(1) on average

The space complexity is O(n) or alternatively O(C), where C is the range of possible values in the array. This is because:

• The Counter cnt stores at most n unique elements from the array, requiring O(n) space
• Since the problem constraints limit element values to a range (typically 0 to 100 in this problem), the Counter can also be bounded by O(C) where C = 100
• The space complexity can be expressed as O(min(n, C)), which in this specific problem context with C = 100 is effectively O(C)

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

Common Pitfalls

1. Not Properly Managing the Counter State

One of the most critical pitfalls in this solution is forgetting to decrement the counter for the middle element. If you don't decrement frequency_map[middle_val], you might count invalid triplets where the same element position is used multiple times.

Incorrect approach:

for middle_idx, middle_val in enumerate(arr):
    # WRONG: Not decrementing the counter
    for left_val in arr[:middle_idx]:
        required_third = target - left_val - middle_val
        triplet_count += frequency_map[required_third]

Why it fails: This would count cases where the middle element itself could be counted as the third element, violating the i < j < k constraint.

2. Integer Overflow Issues

Without applying the modulo operation during accumulation, the result can overflow for large inputs.

Incorrect approach:

# Accumulate without modulo
triplet_count += frequency_map[required_third]
# Apply modulo only at the end
return triplet_count % MOD

Correct approach:

# Apply modulo during each addition
triplet_count = (triplet_count + frequency_map[required_third]) % MOD

3. Incorrect Index Ordering

A common mistake is not maintaining the strict ordering i < j < k. Some might try to use combinations or permutations without considering the index constraints.

Incorrect approach:

# Using combinations without considering actual indices
from itertools import combinations
count = 0
for triplet in combinations(arr, 3):
    if sum(triplet) == target:
        count += 1

Why it fails: This counts unique value combinations, not index-based triplets. For example, [1,1,2] with target 4 should count the triplet twice (indices 0,1,2 and indices 0,2,1 are different), but combinations would only count it once.

4. Not Handling Negative Values in Required Third Element

If the calculated required_third is negative or out of the valid range, accessing frequency_map[required_third] still works with Counter (returns 0), but with an array-based approach, it could cause issues.

Potential issue with array-based counting:

# If using array instead of Counter
frequency_array = [0] * 101
# ...
required_third = target - left_val - middle_val
# This could be negative or > 100
triplet_count += frequency_array[required_third]  # IndexError!

Solution:

# Add bounds checking for array approach
if 0 <= required_third <= 100:
    triplet_count += frequency_array[required_third]

5. Reconstructing Counter Instead of Decrementing

Some might try to create a new counter for remaining elements instead of decrementing, which is inefficient.

Inefficient approach:

for middle_idx, middle_val in enumerate(arr):
    # Creating new counter each time - O(n) operation
    remaining_counter = Counter(arr[middle_idx + 1:])
    for left_val in arr[:middle_idx]:
        required_third = target - left_val - middle_val
        triplet_count += remaining_counter[required_third]

Why the original approach is better: Decrementing and maintaining a single counter is more efficient (O(1) per update) than creating new counters (O(n) per iteration).