Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Fix the middle element of a triplet. Both outer values must equal twice that middle value, and their positions must lie on opposite sides. The number of triplets with this middle is therefore the product of the matching occurrence counts to its left and right.

Approach

Initialize an empty left frequency map and a right map containing all input values. Scan each value x as the middle. First remove its current occurrence from the right map so it cannot be selected as the right endpoint. Add left[2 * x] * right[2 * x] to the answer, then insert x into the left map for future iterations.

Reduce the answer modulo 1,000,000,007. Removing before counting and adding afterward enforces strictly increasing indices, including when x = 0 and the target equals the middle value. Each triplet has exactly one middle index, so it is counted once.

class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        left = Counter()
        right = Counter(nums)
        res = 0

        for x in nums:
            right[x] -= 1
            target = x * 2
            res = (res + left[target] * right[target]) % MOD
            left[x] += 1

        return res % MOD

Complexity analysis

Let n = nums.length and u be its number of distinct values. Time: O(n). Auxiliary space: O(u).