Problem Statement in English

You’re given a 0-indexed array nums of integers. A triplet (i, j, k) is called special if the following conditions are satisfied:

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

Return the total number of special triplets in nums. Since the answer may be very large, return it modulo $10^9 + 7$.

Approach

To solve the problem of counting special triplets in the array, we can use a combination of prefix and suffix counts. The idea is to keep track of how many times each number has appeared before and after the current index while iterating through the array.

Further, using a little bit of combinatorics, we can determine how many valid triplets can be formed with the current element as the middle element of the triplet.

Solution in Python


class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        l = len(nums)
        MOD = 10**9 + 7

        c = defaultdict(int)
        prefix = [0] * l
        suffix = [0] * l
        res = 0

        for i, num in enumerate(nums):
            prefix[i] = c[num * 2]
            c[num] += 1

        c = defaultdict(int)
        
        for i in reversed(range(l)):
            num = nums[i]
            suffix[i] = c[num * 2]
            c[num] += 1

        for i in range(len(nums)):
            res += (prefix[i] * suffix[i]) % MOD

        return res % MOD

Complexity

  • Time: $O(n)$
    Since we iterate over the array once to build prefix and suffix counts, and once more to calculate the result.

  • Space: $O(n)$
    We use additional space for the prefix and suffix arrays, as well as the dictionaries to count occurrences.

And we are done.