Count Special Triplets

Medium
1832.

Count Special Triplets

Count Special Triplets is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

You are given an integer array nums.

A special triplet is a triple of indices (i, j, k) with 0 <= i < j < k < n such that nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2.

Return the number of special triplets. Since it can be very large, return it modulo 10^9 + 7.

Example 1

Input
nums = [4,2,4,2,4]
Output
4
Explanation
With the `2` at index 1: one `4` before it and two after (2 triplets). With the `2` at index 3: two `4`s before and one after (2 more).

Example 2

Input
nums = [0,0,0,0]
Output
4
Explanation
`0 * 2 = 0`: middle index 1 gives `1 * 2`, middle index 2 gives `2 * 1`.

Example 3

Input
nums = [1,2,3]
Output
0

Constraints

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var specialTriplets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Special Triplets — Solution in Python, Java & C++

Count Special Triplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Special Triplets is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums.

A special triplet is a triple of indices (i, j, k) with 0 <= i < j < k < n such that nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2.

Return the number of special triplets. Since it can be very large, return it modulo 10^9 + 7.

Example 1

Input: nums = [4,2,4,2,4]
Output: 4
Explanation: With the `2` at index 1: one `4` before it and two after (2 triplets). With the `2` at index 3: two `4`s before and one after (2 more).

Example 2

Input: nums = [0,0,0,0]
Output: 4
Explanation: `0 * 2 = 0`: middle index 1 gives `1 * 2`, middle index 2 gives `2 * 1`.

Example 3

Input: nums = [1,2,3]
Output: 0

Constraints

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

Hints for Count Special Triplets

  1. Hint 1

    Fix the middle index j. The outer indices are independent: any i < j holding 2 * nums[j] pairs with any k > j holding the same value.

  2. Hint 2

    So the middle contributes left[2 * nums[j]] * right[2 * nums[j]], where left counts values before j and right counts values after it.

  3. Hint 3

    Start with right = counts of the whole array; while sweeping j left to right, remove nums[j] from right before using it and add it to left afterwards. The product can exceed 32 bits — use 64-bit arithmetic before taking the modulus.

How to solve Count Special Triplets

Count by the middle element. For a fixed j, the number of valid outer pairs is the product of how many times 2 * nums[j] appears to the left and to the right, and both counts can be maintained in one sweep.

Approach

  1. Build right, the frequency of every value in nums, and an empty left.
  2. For each j from left to right: decrement right[nums[j]] (so right covers indices after j).
  3. Let t = 2 * nums[j]; add left[t] * right[t] to the answer, modulo 10^9 + 7.
  4. Increment left[nums[j]].

Why it works

Every special triplet has exactly one middle index, and for that j the pair (i, k) is any choice of an index before j and an index after j that both hold t. The number of such choices is left[t] * right[t], and the sweep keeps left and right equal to the counts strictly before and strictly after j.

Complexity

  • Time — O(n)
  • Space — O(V) for the counts

Pitfalls

  • Zeros satisfy 0 == 0 * 2: the middle itself must not be counted on either side, which is why right is decremented before the lookup and left incremented after.
  • left[t] * right[t] can reach about 2.5 * 10^9, which overflows a 32-bit integer.
  • 2 * nums[j] can exceed the largest value present — guard the lookup.

Reference solution

Python

from typing import List

def specialTriplets(nums: List[int]) -> int:
    MOD = 10**9 + 7
    right = {}
    for v in nums:
        right[v] = right.get(v, 0) + 1
    left = {}
    ans = 0
    for v in nums:
        right[v] -= 1
        t = v * 2
        ans = (ans + left.get(t, 0) * right.get(t, 0)) % MOD
        left[v] = left.get(v, 0) + 1
    return ans

Java

public static int specialTriplets(int[] nums) {
    final long MOD = 1_000_000_007L;
    int mx = 0;
    for (int v : nums) mx = Math.max(mx, v);
    int[] left = new int[mx + 1], right = new int[mx + 1];
    for (int v : nums) right[v]++;
    long ans = 0;
    for (int v : nums) {
        right[v]--;
        int t = v * 2;
        if (t <= mx) ans = (ans + (long) left[t] * right[t]) % MOD;
        left[v]++;
    }
    return (int) ans;
}

C++

int specialTriplets(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    int mx = 0;
    for (int v : nums) mx = max(mx, v);
    vector<int> left(mx + 1, 0), right(mx + 1, 0);
    for (int v : nums) right[v]++;
    long long ans = 0;
    for (int v : nums) {
        right[v]--;
        int t = v * 2;
        if (t <= mx) ans = (ans + (long long)left[t] * right[t]) % MOD;
        left[v]++;
    }
    return (int)ans;
}

JavaScript

var specialTriplets = function(nums) {
    var MOD = 1000000007;
    var right = new Map(), left = new Map();
    for (var i = 0; i < nums.length; i++) right.set(nums[i], (right.get(nums[i]) || 0) + 1);
    var ans = 0;
    for (var j = 0; j < nums.length; j++) {
        var v = nums[j];
        right.set(v, right.get(v) - 1);
        var t = v * 2;
        // Both counts are at most 1e5, so the product stays below 2^53.
        ans = (ans + ((left.get(t) || 0) * (right.get(t) || 0)) % MOD) % MOD;
        left.set(v, (left.get(v) || 0) + 1);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets