Skip to main content
Talentd

Count Special Triplets - Solution & Explanation

MediumArrayHash TableCounting11 min readAsked at: Meta, Google, Bloomberg
Practice this problem

Problem Statement

You are given an integer array nums.

A special triplet is defined as a triplet of indices (i, j, k) such that:

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

Return the total number of special triplets in the array.

Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [6,3,6]

Output: 1

Explanation:

The only special triplet is (i, j, k) = (0, 1, 2), where:

  • nums[0] = 6, nums[1] = 3, nums[2] = 6
  • nums[0] = nums[1] * 2 = 3 * 2 = 6
  • nums[2] = nums[1] * 2 = 3 * 2 = 6

Example 2:

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

Output: 1

Explanation:

The only special triplet is (i, j, k) = (0, 2, 3), where:

  • nums[0] = 0, nums[2] = 0, nums[3] = 0
  • nums[0] = nums[2] * 2 = 0 * 2 = 0
  • nums[3] = nums[2] * 2 = 0 * 2 = 0

Example 3:

Input: nums = [8,4,2,8,4]

Output: 2

Explanation:

There are exactly two special triplets:

  • (i, j, k) = (0, 1, 3)
    • nums[0] = 8, nums[1] = 4, nums[3] = 8
    • nums[0] = nums[1] * 2 = 4 * 2 = 8
    • nums[3] = nums[1] * 2 = 4 * 2 = 8
  • (i, j, k) = (1, 2, 4)
    • nums[1] = 4, nums[2] = 2, nums[4] = 4
    • nums[1] = nums[2] * 2 = 2 * 2 = 4
    • nums[4] = nums[2] * 2 = 2 * 2 = 4

 

Constraints:

  • 3 <= n == nums.length <= 105
  • 0 <= nums[i] <= 105

Approach Overview

Problem Overview: You need to count triplets of indices (i, j, k) such that i < j < k and the three values satisfy a specific “special” numeric relationship defined in the problem. The challenge is avoiding the obvious cubic scan of all triplets and instead exploiting the fact that the middle index j uniquely determines what values must appear on the left and right.

Approach 1: Brute Force Triplet Enumeration (O(n^3) time, O(1) space)

The direct approach checks every possible triple of indices. Use three nested loops: the outer loop picks i, the second picks j, and the third picks k. For each triple, evaluate the special relation defined by the problem. This guarantees correctness but performs O(n^3) checks, which becomes too slow once the array grows beyond a few thousand elements. The method is mainly useful for verifying logic or constructing small test cases.

Approach 2: Enumerate Middle Number + Hash Table (O(n) time, O(n) space)

The key observation: once the middle index j is fixed, the required values for nums[i] and nums[k] become deterministic based on nums[j] and the special relation. Instead of scanning both sides repeatedly, maintain frequency counts of elements on the left and right using a hash map. As you iterate through the array, treat the current element as the middle. The left map stores counts of values that appear before j, while the right map tracks remaining elements after j.

For each j, compute the value(s) that must appear on the left and right to form a valid triplet with nums[j]. A constant‑time hash lookup gives the number of candidates on each side. Multiply those counts to determine how many triplets use this middle element. Then update the maps as the pointer moves forward. This technique converts repeated scans into O(1) lookups, reducing the total complexity to linear time.

The pattern of fixing a center element and counting compatible values on both sides appears frequently in problems involving arrays, frequency tracking with hash tables, and combinational counting. Once you recognize that the middle value determines the relationship, the optimization becomes straightforward.

Recommended for interviews: Start by explaining the O(n^3) brute force idea to show you understand the triplet constraint i < j < k. Then move to the optimized solution where you enumerate the middle element and use hash maps to count valid partners on each side. Interviewers typically expect this reasoning because it reduces redundant scans and demonstrates familiarity with frequency maps and counting techniques.

Solution

We can enumerate the middle number nums[j], and use two hash tables, left and right, to record the occurrence counts of numbers to the left and right of nums[j], respectively.

First, we add all numbers to right. Then, we traverse each number nums[j] from left to right. During the traversal:

  1. Remove nums[j] from right.
  2. Count the occurrences of the number nums[i] = nums[j] * 2 to the left of nums[j], denoted as left[nums[j] * 2].
  3. Count the occurrences of the number nums[k] = nums[j] * 2 to the right of nums[j], denoted as right[nums[j] * 2].
  4. Multiply left[nums[j] * 2] and right[nums[j] * 2] to get the number of special triplets with nums[j] as the middle number, and add the result to the answer.
  5. Add nums[j] to left.

Finally, return the answer.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Small inputs or verifying correctness during initial reasoning
Enumerate Middle + Hash TableO(n)O(n)General case; optimal interview solution using frequency counting

Video Solution

Count Special Triplets | LeetCode 3583 | Complete Intuition Explained • Sanyam IIT Guwahati • 1,875 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Special Triplets easy or hard?
Count Special Triplets is generally classified as a Medium problem. The difficulty comes from recognizing that fixing the middle element allows you to convert a triple nested search into a counting problem with hash tables. Once that insight is clear, the implementation becomes straightforward.
Count Special Triplets Python/Java solution
Implement the optimized approach by iterating through the array and maintaining two hash maps: one for elements already seen and one for elements remaining. For each middle index, compute the required partner values and use map lookups to count valid combinations. This logic translates directly to Python dictionaries, Java HashMap, C++ unordered_map, and similar structures.
How to solve Count Special Triplets in O(n)?
Iterate through the array and treat each element as the middle index j. Maintain a hash map for values to the left and another for values to the right. For the current middle value, determine which values must appear on both sides to form a valid triplet and multiply their frequencies. Update the maps as you move forward to maintain correct counts.
What is the best approach for Count Special Triplets?
The most efficient approach enumerates the middle index j and uses hash tables to track frequencies of numbers on the left and right of j. For each middle value, compute the required partner values that satisfy the special relation and use constant-time hash lookups to count matches. This reduces the complexity from O(n^3) brute force to O(n) time with O(n) extra space.
Is Count Special Triplets asked at Google/Amazon/Meta?
Problems based on counting triplets with hash maps and index ordering frequently appear in interviews at companies like Google, Amazon, and Meta. Variations typically test array traversal, frequency maps, and recognizing patterns where fixing one element simplifies the search space.
What data structure is used in Count Special Triplets?
The optimized solution relies on a hash table (hash map) to maintain frequency counts of numbers on the left and right sides of the current middle index. Arrays are used for traversal, while the hash table enables constant-time lookups for matching values required to form valid triplets.
What is the time complexity of Count Special Triplets?
The optimal solution runs in O(n) time using a middle enumeration strategy with hash maps for frequency counting. Each element is processed once as the middle, while lookups for matching left and right values take O(1) on average. Space complexity is O(n) for storing frequency counts.

Ready to solve this problem?

Practice Count Special Triplets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays