Leetcode 3583. Count Special Triplets

Let's understand what we're being asked to do. We have an array like nums = [1, 2, 3, 2, 1] and need to count triplets (i, j, k) where i < j < k and both nums[i] and nums[k] equal 2 * nums[j].

Tracing through: For j=1 (where nums[j]=2), we need nums[i]=4 and nums[k]=4. Looking left of index 1, we have no 4s. Looking right, we have no 4s. So this j contributes 0 triplets.

For j=3 (where nums[j]=2), we need nums[i]=4 and nums[k]=4 again. Still no matches.

Important constraint: The array can have up to 10^5 elements, and values can be up to 10^5. This means a brute-force O(n³) approach checking all triplets would be too slow!

Key observation: For each middle index j, we need to count how many times 2*nums[j] appears to the left AND to the right, then multiply these counts.

Edge cases to consider: What if nums[j]=0? (then 2*nums[j]=0). What if the array has fewer than 3 elements? What if no valid triplets exist?

The brute-force approach uses three nested loops to check every possible triplet (i, j, k) where i < j < k. For each triplet, verify if nums[i] == 2 * nums[j] and nums[k] == 2 * nums[j]. If both conditions are true, increment the count. This approach is straightforward but extremely inefficient for large arrays, as it examines all O(n³) possible triplets.

def count_arithmetic_triplets(nums):
    """
    Brute force: Check all triplets (i, j, k) where i < j < k.
    Count triplets where nums[i] == 2 * nums[j] and nums[k] == 2 * nums[j].
    """
    MOD = 10**9 + 7
    n = len(nums)
    count = 0
    
    # Outer loop: iterate through all possible i positions
    for i in range(n):
        # Middle loop: iterate through all possible j positions (j > i)
        for j in range(i + 1, n):
            # Inner loop: iterate through all possible k positions (k > j)
            for k in range(j + 1, n):
                # Check if nums[i] equals 2 * nums[j]
                if nums[i] == 2 * nums[j]:
                    # Check if nums[k] equals 2 * nums[j]
                    if nums[k] == 2 * nums[j]:
                        # Found valid triplet, increment count
                        count = (count + 1) % MOD
    
    return count

For each middle element nums[j], we need to find elements equal to 2*nums[j] on BOTH sides. If there are leftCount such elements on the left and rightCount on the right, they form leftCount * rightCount valid triplets.

This transforms the problem from checking all O(n³) triplets to processing each middle position in O(1) time with preprocessing.

By precomputing frequency maps for elements to the left and right of each position, we avoid the nested loops of checking every possible (i, j, k) combination.

Instead of checking billions of triplets for large arrays, we make a single pass through the array, looking up counts in O(1) time. This reduces complexity from O(n³) to O(n).

Imagine you're standing at position j in the array. You need to count pairs where one element is to your left and one is to your right, both having the same target value 2*nums[j].

If you know there are 3 copies of the target value on your left and 2 copies on your right, you can form 3 * 2 = 6 triplets by pairing any left element with any right element. The key insight is: precompute these counts so you don't have to scan left and right repeatedly for each position.

The optimal approach uses frequency maps to track counts of each value to the left and right of each position. For each index j, compute the target value 2 * nums[j]. Look up how many times this target appears in the left frequency map and the right frequency map. Multiply these counts to get the number of valid triplets with j as the middle index. As we iterate through the array, dynamically update the left and right frequency maps. Sum all contributions modulo 10^9 + 7.

def count_triplets(nums):
    """
    Count triplets (i<j<k) where nums[i] == nums[k] == 2*nums[j].
    Uses frequency maps to track counts left and right of each position.
    """
    MOD = 10**9 + 7
    n = len(nums)
    
    # Initialize frequency maps
    left_freq = {}
    right_freq = {}
    
    # Build right frequency map with all elements
    for num in nums:
        right_freq[num] = right_freq.get(num, 0) + 1
    
    result = 0
    
    # Iterate through each position as middle element
    for j in range(n):
        # Remove current element from right map
        right_freq[nums[j]] -= 1
        if right_freq[nums[j]] == 0:
            del right_freq[nums[j]]
        
        # Calculate target value (2 * nums[j])
        target = 2 * nums[j]
        
        # Count triplets with j as middle
        left_count = left_freq.get(target, 0)
        right_count = right_freq.get(target, 0)
        triplets = (left_count * right_count) % MOD
        result = (result + triplets) % MOD
        
        # Add current element to left map
        left_freq[nums[j]] = left_freq.get(nums[j], 0) + 1
    
    return result

• Frequency map with prefix-suffix decomposition: When counting triplet relationships where the middle element determines the constraint, decompose into left and right frequency maps - for each middle position j, multiply counts of the target value (2*nums[j]) appearing before and after, enabling O(n) instead of O(n³) brute force.
• Dynamic frequency tracking pattern: Maintain a suffix frequency map initialized with all elements, then iterate through the array while moving elements from suffix to prefix map - this single-pass technique elegantly handles "elements to the left" vs "elements to the right" queries without multiple array scans.
• Multiplication principle for independent choices: When selecting elements from disjoint sets (left side and right side of j), the total combinations equals count_left × count_right - this combinatorial insight transforms a nested loop problem into simple arithmetic per position.
• Modular arithmetic accumulation: Apply mod 1e9+7 only during accumulation of the final sum, not during intermediate frequency counting - premature modding can cause incorrect results when you need actual counts for multiplication, and final modding prevents integer overflow.
• Value-as-key optimization: When array values are bounded (up to 1e5) but you need to count occurrences of specific values, use hash maps with values as keys rather than index-based arrays - this handles sparse value distributions efficiently and makes the "find count of 2*nums[j]" lookup O(1).
• Triplet counting reduction technique: For constrained triplet problems (i<j<k with value relationships), identify if the middle element determines both endpoints - if so, iterate over middle positions and use precomputed counts rather than nested loops, a pattern applicable to many "special triplet" problems.