Problem Description

You are given an integer array nums.

A special triplet is defined as a triplet of indices (i, j, k) such that:

• 0 <= i < j < k < n, where n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

Return the total number of special triplets in the array.

Since the answer may be large, return it modulo 10^9 + 7.

Intuition

The task is to count triplets (i, j, k) where nums[i] and nums[k] are both exactly double nums[j], with the indices in order (i < j < k). Instead of checking all possible triplets, which would be slow for large arrays, notice that for each possible "middle" element nums[j], we only care about how many times nums[j] * 2 appears both before and after index j.

If we can quickly count those occurrences, then for each j, the total number of triplets with j as the middle is just the product of those two counts. This can be done efficiently by keeping track of counts to the left and right of j as we iterate through the array. Using hash tables (or Counters) to store these counts lets us compute the answer in one pass, updating our counts as we go.

Solution Approach

The solution uses an efficient way to count the valid triplets by focusing on each possible "middle" index j and using hash tables to keep track of occurrences:

1. Use two hash tables, left and right, where:
   • left[x] tracks how many times number x has appeared before the current index.
   • right[x] tracks how many times number x will appear after the current index.
2. Initially, count all occurrences of each number in nums and store them in right. The left hash table starts empty.
3. Iterate over the array from left to right using index j as the "middle" of the triplet:
   • For each nums[j], decrement its count in right since it's now being considered.
   • To form a valid triplet (i, j, k), need:
     • i < j where nums[i] == nums[j] * 2 (count in left[nums[j] * 2])
     • k > j where nums[k] == nums[j] * 2 (count in right[nums[j] * 2])
   • Multiply the counts for left[nums[j] * 2] and right[nums[j] * 2] to get all ways to choose i and k for given j, and add to the answer.
   • After processing, increment the count of nums[j] in left.
4. Since the result can be large, keep the answer modulo 10^9 + 7.

Here is the code that implements this logic:

from collections import Counter

class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        left = Counter()
        right = Counter(nums)
        ans = 0
        mod = 10**9 + 7
        for x in nums:
            right[x] -= 1
            ans = (ans + left[x * 2] * right[x * 2] % mod) % mod
            left[x] += 1
        return ans

• The algorithm runs in linear time, iterating through nums once and using constant work per position with hash table lookups and updates. This makes it very efficient for large arrays.

Example Walkthrough

Let's illustrate the solution with a small array: nums = [4, 2, 4, 8, 2]

We want to count the number of special triplets (i, j, k) such that:

• 0 <= i < j < k < 5
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

Step-by-step

1. Initialization

• left = Counter()          (Initially empty)
• right = Counter({4: 2, 2: 2, 8: 1})  (Counts of all elements)
• ans = 0

2. Iterate through each j (the middle index):

j = 0, nums[0] = 4

• Decrement right[4] → right[4] = 1
• Count of nums[j]*2 in left = left[8] = 0
• Count of nums[j]*2 in right = right[8] = 1
• Triplets for this j: 0 * 1 = 0 (add to ans)
• Increment left[4] → left[4] = 1

j = 1, nums[1] = 2

• Decrement right[2] → right[2] = 1
• nums[j]*2 = 4
• left[4] = 1, right[4] = 1
• Triplets: 1 * 1 = 1 (add to ans, now ans = 1)
• Increment left[2] → left[2] = 1

j = 2, nums[2] = 4

• Decrement right[4] → right[4] = 0
• nums[j]*2 = 8
• left[8] = 0, right[8] = 1
• Triplets: 0 * 1 = 0
• Increment left[4] → left[4] = 2

j = 3, nums[3] = 8

• Decrement right[8] → right[8] = 0
• nums[j]*2 = 16
• left[16] = 0, right[16] = 0
• Triplets: 0 * 0 = 0
• Increment left[8] → left[8] = 1

j = 4, nums[4] = 2

• Decrement right[2] → right[2] = 0
• nums[j]*2 = 4
• left[4]=2, right[4]=0
• Triplets: 2 * 0 = 0
• Increment left[2] → left[2] = 2

Final count

The total number of special triplets in [4, 2, 4, 8, 2] is 1.

This process efficiently counts triplets by only tracking how many valid i (before j) and k (after j) can pair up with each choice of j, avoiding slow triple-nested loops.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.