LeetCode 3583 - Count Special Triplets

We are given an integer array nums of length n. We must count the number of index triplets (i, j, k) such that 0 <= i < j < k < n and the middle element nums[j] acts as a generator for both ends through the relation nums[i] = 2 nums[j] and nums[k] = 2 nums[j].

leetcodemediumarrayhash-tablecounting

LeetCode Problem 3583

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

Solution

Problem Understanding

We are given an integer array nums of length n. We must count the number of index triplets (i, j, k) such that 0 <= i < j < k < n and the middle element nums[j] acts as a generator for both ends through the relation nums[i] = 2 * nums[j] and nums[k] = 2 * nums[j].

Equivalently, for each choice of middle index j, we are looking for pairs of indices i < j and k > j such that both nums[i] and nums[k] equal the same value x = 2 * nums[j]. Each valid pair of occurrences of x on the left and right of j contributes one valid triplet.

The output is the total number of such triplets modulo 10^9 + 7.

The constraints 3 <= n <= 10^5 and 0 <= nums[i] <= 10^5 imply that an O(n^2) or worse solution is not feasible. We must precompute or maintain frequency information efficiently.

Edge cases include arrays with many zeros, since 2 * 0 = 0, which makes matching highly repetitive, and arrays where valid values occur densely on both sides of many positions.

Approaches

A brute-force solution directly enumerates all triples (i, j, k) with i < j < k and checks whether both equality conditions hold. This is correct because it directly follows the definition, but it is computationally infeasible since it examines all O(n^3) combinations.

The key insight is that for a fixed middle index j, the condition depends only on counting occurrences of a single value x = 2 * nums[j] on the left side and right side. If we can maintain prefix and suffix frequencies, we can compute contributions for each j in constant time.

We maintain two hash maps: left counts occurrences of values before j, and right counts occurrences after j. Initially, right contains frequencies of the entire array. As we move j from left to right, we decrement right[nums[j]] and increment left[nums[j]], ensuring correct partitioning.

For each j, we compute x = 2 * nums[j], and the number of valid pairs is left[x] * right[x].

Complexity Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Enumerate all triples explicitly
Optimal O(n) O(n) Maintain prefix and suffix frequency maps

Algorithm Walkthrough

We proceed by maintaining frequency counts of elements on both sides of the current index j.

  1. First, construct a frequency map right that counts occurrences of every value in nums. This represents all elements available to the right of the current index before processing begins.
  2. Initialize an empty map left, which will represent elements strictly to the left of j as we iterate.
  3. Iterate j from 0 to n - 1. At each step, we conceptually move nums[j] from the right side into the middle position, so we decrement right[nums[j]] before processing j.
  4. For the current index j, compute target = 2 * nums[j]. This is the value that must appear at both ends of the triplet.
  5. The number of valid choices for i is left[target], since any occurrence of target before j is valid. The number of valid choices for k is right[target], since any occurrence of target after j is valid.
  6. The contribution of index j is therefore left[target] * right[target], and we add this to the global answer.
  7. After processing index j, we update left[nums[j]] += 1 to reflect that this element is now part of the left side for future iterations.
  8. Continue until all indices are processed, taking all results modulo 10^9 + 7.

Why it works

At each index j, the arrays left and right form a correct partition of all indices i < j < k. Since multiplication of counts enumerates all independent choices of valid i and k, every valid triplet is counted exactly once when processing its middle index j.

Python Solution

from typing import List
from collections import defaultdict

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

        right = defaultdict(int)
        for x in nums:
            right[x] += 1

        left = defaultdict(int)
        ans = 0

        for j in range(n):
            x = nums[j]
            right[x] -= 1

            target = 2 * x

            if target in left and target in right:
                ans += left[target] * right[target]
                ans %= MOD

            left[x] += 1

        return ans % MOD

Explanation of Python Implementation

We initialize right as the full frequency map. During iteration, we first remove the current element from right to ensure it is not counted in the suffix. We then compute target = 2 * nums[j] and multiply prefix and suffix counts from left and right. Finally, we move nums[j] into left. The modulo is applied incrementally to avoid overflow.

Go Solution

func specialTriplets(nums []int) int {
    const MOD int64 = 1000000007

    right := make(map[int]int64)
    left := make(map[int]int64)

    for _, v := range nums {
        right[v]++
    }

    var ans int64 = 0

    for j := 0; j < len(nums); j++ {
        x := nums[j]

        right[x]--

        target := 2 * x

        if left[target] > 0 && right[target] > 0 {
            ans = (ans + left[target]*right[target]) % MOD
        }

        left[x]++

        if right[x] == 0 {
            delete(right, x)
        }
    }

    return int(ans % MOD)
}

Go-Specific Notes

Go requires explicit use of int64 to safely handle intermediate multiplication and modulo arithmetic. Maps default to zero values, which simplifies frequency handling. We optionally delete zero-count entries from right for cleanliness, though it is not strictly necessary for correctness.

Worked Examples

Example 1: nums = [6,3,6]

We initialize right = {6:1, 3:1, 6:1} which merges into {6:2, 3:1}, and left = {}.

At j = 0, nums[j] = 6, so target = 12. No occurrences exist in left or right, contribution is 0.

After update: left = {6:1}, right = {6:1, 3:1}.

At j = 1, nums[j] = 3, so target = 6. Now left[6] = 1, right[6] = 1, so contribution is 1.

After update: left = {6:1, 3:1}, right = {6:0}.

At j = 2, nums[j] = 6, target = 12. No contribution.

Final answer is 1.

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

We track only relevant transitions.

At j = 2, nums[j] = 0, so target = 0.

Before processing, left contains one 0 at index 0, and right contains one 0 at index 3.

Thus contribution is 1 * 1 = 1.

All other indices produce zero contribution because nums[j] != 0 or insufficient matching values.

Final answer is 1.

Example 3: nums = [8,4,2,8,4]

We examine only indices producing valid targets.

At j = 1, nums[j] = 4, target = 8.

Left has one 8, right has one 8, so contribution is 1.

At j = 2, nums[j] = 2, target = 4.

Left has one 4, right has one 4, so contribution is 1.

Total is 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is processed once with O(1) hash operations
Space O(n) Two hash maps store frequency counts of values

The algorithm performs constant-time updates per element. The dominant cost is maintaining frequency maps over the array’s value range.

Test Cases

assert Solution().specialTriplets([6, 3, 6]) == 1  # basic example
assert Solution().specialTriplets([0, 1, 0, 0]) == 1  # zero-heavy case
assert Solution().specialTriplets([8, 4, 2, 8, 4]) == 2  # multiple valid j
assert Solution().specialTriplets([1, 2, 3]) == 0  # no valid triplets
assert Solution().specialTriplets([2, 1, 2, 1, 2]) == 4  # repeated pattern
assert Solution().specialTriplets([0, 0, 0]) == 1  # all zeros
assert Solution().specialTriplets([10]) == 0  # minimal invalid length handled implicitly
Test Why
[6,3,6] verifies basic single triplet
[0,1,0,0] checks zero doubling property
[8,4,2,8,4] multiple valid middle indices
[1,2,3] no valid structure exists
[2,1,2,1,2] dense repeated values
[0,0,0] all elements equal edge case
[10] degenerate small input robustness

Edge Cases

One important edge case is when all elements are zero. Since 2 * 0 = 0, every index can potentially form triplets with any pair of other zeros. This creates a combinatorial explosion that the frequency-based approach correctly handles without special casing, since counts naturally multiply.

Another edge case arises when values are large but sparse. In such cases, target = 2 * nums[j] may exceed typical value ranges seen elsewhere in the array. The hash map safely returns zero for missing keys, ensuring correctness without explicit bounds checks.

A final edge case involves arrays with repeated values clustered on one side of the pivot. The correctness depends critically on maintaining strict separation between left and right at each j. The incremental update of maps before and after processing each index guarantees that no invalid index ordering is counted.