LeetCode 3583 - Count Special Triplets

LeetCode Problem 3583

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

This problem asks us to count the number of special triplets in an integer array nums. A special triplet (i, j, k) must satisfy three conditions: the indices are strictly increasing 0 <= i < j < k < n, nums[i] is exactly double nums[j], and nums[k] is also exactly double nums[j]. In other words, nums[j] acts as a "pivot" value, with both nums[i] before it and nums[k] after it being exactly double its value.

The input is a list of integers, and the output is a single integer representing the total number of such triplets, modulo $10^9 + 7$. The constraints indicate that the array length can be up to $10^5$ and values can also be up to $10^5$, meaning a naive cubic solution would be far too slow. Important edge cases include arrays with zeros (since 0 * 2 = 0) and arrays with repeated elements.

Approaches

The brute-force approach is straightforward: iterate over all triplets (i, j, k) with three nested loops. For each triplet, check if nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2. This guarantees correctness because it explicitly examines all possibilities. However, its time complexity is $O(n^3)$, which is infeasible for n = 10^5.

The optimal approach relies on counting occurrences efficiently using hash maps. For each potential pivot nums[j], we want to know how many nums[i] to the left satisfy nums[i] == nums[j] * 2 and how many nums[k] to the right satisfy nums[k] == nums[j] * 2. We can maintain a prefix map that counts how many times each number has appeared so far and a suffix map that counts occurrences to the right. Then, for each j, the number of special triplets with nums[j] as the pivot is prefix_count[nums[j] * 2] * suffix_count[nums[j] * 2]. This reduces the algorithm to a linear pass with constant-time map operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Checks all triplets explicitly, too slow for large n
Optimal	O(n)	O(n)	Uses prefix and suffix counts with hash maps to compute contributions efficiently

Algorithm Walkthrough

1. Initialize a hash map suffix_count to store the frequency of each number in the array. This represents how many times each number occurs to the right of the current pivot index j.

2. Initialize an empty hash map prefix_count to store counts of numbers to the left of j.

3. Initialize a variable result to zero, which will accumulate the total number of special triplets.

4. Iterate over the array with index j. For each nums[j]:

5. Decrease suffix_count[nums[j]] by 1 because nums[j] is now the pivot, not part of the right segment.

6. Calculate the number of valid left elements as prefix_count[nums[j] * 2] and the number of valid right elements as suffix_count[nums[j] * 2].

7. Increment result by the product of these two counts. This counts all triplets (i, j, k) with the current pivot j.

8. Increase prefix_count[nums[j]] by 1 to include the current pivot in the left counts for future iterations.

9. Return result % (10^9 + 7) to handle large outputs.

Why it works: The algorithm correctly counts all triplets without missing or double-counting because each element acts exactly once as the pivot j, and we accurately maintain counts of potential i and k candidates on either side. Map lookups are constant time, ensuring efficiency.

Python Solution

from typing import List
from collections import Counter

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

The Python implementation uses Counter for both prefix_count and suffix_count to keep track of occurrences efficiently. For each pivot, we decrement the suffix count to exclude the pivot itself, then multiply left and right counts to get the contribution to the result. Finally, the pivot is added to the prefix for future iterations.

Go Solution

func specialTriplets(nums []int) int {
    const MOD = 1_000_000_007
    suffixCount := make(map[int]int)
    prefixCount := make(map[int]int)
    result := 0

    for _, num := range nums {
        suffixCount[num]++
    }

    for _, num := range nums {
        suffixCount[num]--
        left := prefixCount[num*2]
        right := suffixCount[num*2]
        result = (result + left*right) % MOD
        prefixCount[num]++
    }

    return result
}

In Go, maps are used instead of Counter. The logic is identical: maintain counts of numbers on the left and right, compute the contribution of each pivot, and update the result modulo $10^9 + 7$. Go handles integer overflow naturally for values below 2^63 - 1.

Worked Examples

Example: nums = [6, 3, 6]

j	num	prefix_count	suffix_count	left	right	result
0	6	{}	{6:2,3:1}	0	0	0
1	3	{6:1}	{6:1,3:1}	1	1	1
2	6	{6:1,3:1}	{6:0,3:1}	0	0	1

Total result = 1

Example: nums = [0,1,0,0]

j	num	prefix_count	suffix_count	left	right	result
0	0	{}	{0:3,1:1}	0	2	0
1	1	{0:1}	{0:3,1:0}	0	0	0
2	0	{0:1,1:1}	{0:2,1:0}	0	2	0
3	0	{0:2,1:1}	{0:1,1:0}	0	1	1

Total result = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over the array, with O(1) map operations for each element
Space	O(n)	Two hash maps storing counts of numbers in the array

The linear complexity is sufficient for the upper bound of n = 10^5. Each map can hold at most n unique numbers, matching the space analysis.

Test Cases

# Provided examples
assert Solution().specialTriplets([6,3,6]) == 1  # single triplet
assert Solution().specialTriplets([0,1,0,0]) == 1  # zeros handling
assert Solution().specialTriplets([8,4,2,8,4]) == 2  # multiple triplets

# Edge cases
assert Solution().specialTriplets([1,2,4]) == 0  # no valid triplet
assert Solution().specialTriplets([0,0,0,0]) == 4  # all zeros, multiple triplets
assert Solution().specialTriplets([2,4,8,16,32]) == 0  # no pivot has double on both sides
assert Solution().specialTriplets([1]*100) == 0  # repeated same number, cannot satisfy double condition

Test	Why
[6,3,6]	Single valid triplet
[0,1,0,0]	Zero values test edge case
[8,4,2,8,4]	Multiple triplets
[1,2,4]	No triplets possible
[0,0,0,0]	Multiple triplets with zeros
[2,4,8,16,32]	Sequential doubles without pivot match
[1]*100	Repeated numbers, no valid doubling

Edge Cases

All zeros: Arrays of zeros like `[0,0,0,0]