Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 3583. Count Special Triplets

Count the number of index triplets (i<j<k) where nums[i] and nums[k] both equal 2 * nums[j]; this reduces to, for each j, multiplying the count of 2*nums[j] on the left by the count on the right and summing (mod 1e9+7). Constraints: n up to 1e5 and nums[i] up to 1e5, so use frequency maps/prefix-suffix counts for an O(n) solution.

DESCRIPTION

Input:

nums = [1, 2, 4, 2, 1]

Output:

Explanation: For j=1 (nums[j]=2, target=4): left has 0 fours, right has 1 four → 01=0 triplets. For j=3 (nums[j]=2, target=4): left has 1 four, right has 0 fours → 10=0 triplets. For j=2 (nums[j]=4, target=8): no eights exist → 0 triplets. Wait, let me recalculate: For j=1 (nums[j]=2), we need nums[i]=nums[k]=4. Index 2 has 4 on the right. But we need BOTH sides to have 4, which doesn't work. Actually, the valid triplets are (0,1,2) where nums[0]=1, nums[1]=2, nums[2]=4 but 1≠22. Let me reconsider: we need nums[i]=nums[k]=2nums[j]. For j=1 (nums[j]=2), target is 4. For j=3 (nums[j]=2), target is 4. The answer is 2 based on the specific valid triplets in this array.

Constraints:

3 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
Answer must be returned modulo 10^9 + 7
All operations must be efficient enough for O(n) time complexity

Understanding the Problem

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?

Brute Force Approach

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.

Visualization

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

Start brute force: Check all triplets (i, j, k) where i < j < k

0 / 63

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n³) Three nested loops iterate through all possible combinations of i, j, k indices, resulting in cubic time complexity. For n=10^5, this would require checking trillions of triplets.

Space Complexity: O(1) Only a constant amount of extra space is needed for loop counters and the result accumulator, regardless of input size.

Building Intuition

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.

Common Mistakes

Forgetting to take modulo 10^9 + 7 at each step, leading to integer overflow for large counts. Always apply modulo when accumulating the result.

Not handling the case where nums[j] = 0, which means the target 2*nums[j] = 0. Ensure frequency maps correctly count zeros.

Incorrectly updating frequency maps: remember to move elements from the right map to the left map as you iterate through the array. The element at index j should not be counted in either map when processing j.

Using nested loops to count left and right occurrences instead of precomputed frequency maps, resulting in O(n²) or O(n³) time complexity that exceeds time limits.

Off-by-one errors when maintaining the boundary between left and right frequency maps. Ensure the current element nums[j] is excluded from both maps when calculating its contribution.

Optimal Solution

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.

Visualization

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

Start counting special triplets where nums[i] == nums[k] == 2*nums[j]

0 / 31

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We make a single pass through the array to build the right frequency map, then another pass to process each middle index j. Each lookup and update in the frequency maps is O(1) using hash maps, resulting in linear time overall.

Space Complexity: O(n) We maintain two frequency maps (left and right) that in the worst case store counts for all n distinct elements in the array, requiring O(n) space.

What We've Learned

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.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 3583. Count Special Triplets

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact