Count Special Triplets - Practice Coding Problems

Count Special Triplets - Problem

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 10^9 + 7.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Two valid triplets: (0,1,2) where nums[0]=2, nums[1]=4, nums[2]=8 (2=4*2 is false, invalid). Actually valid triplets are (1,2,4) and (1,3,4) where middle elements 4 have 8's on both sides.

Example 2 — No Valid Triplets

$ Input: nums = [1,2,3,4,5]

› Output: 0

💡 Note: No valid triplets exist since no element equals another element times 2 in the required positions.

Example 3 — Multiple Matches

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

› Output: 4

💡 Note: Multiple triplets where middle element 2 has 4's (2*2=4) on both sides, creating several valid combinations.

Constraints

3 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,4,8,4,8] with indices 0,1,2,3,4

Process

Find triplets (i,j,k) where nums[i]=nums[k]=nums[j]*2

Output

Count of valid special triplets

Key Takeaway

🎯 Key Insight: Fix the middle element and count valid pairs on left and right sides

Asked in

G Google 15 A Amazon 12 M Microsoft 8

The key insight is to fix the middle element and count valid left and right elements. For each position j, count how many elements equal nums[j]*2 on the left and right, then multiply these counts. Best approach is the optimized O(n²) solution. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Triple Loop	O(n³)	O(1)	Check all possible triplets (i,j,k) with three nested loops
Optimized with Frequency Count	O(n²)	O(1)	For each middle element j, count valid left and right elements using frequency maps

Brute Force Triple Loop — Algorithm Steps

Step 1: Use three nested loops for indices i, j, k where i < j < k
Step 2: Check if nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2
Step 3: Count valid triplets and return result modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Triple Nested Loops

Generate all combinations i < j < k

Condition Check

Verify nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2

Count Valid

Increment counter for each valid triplet

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    const int MOD = 1000000007;
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] == nums[j] * 2 && nums[k] == nums[j] * 2) {
                    count++;
                }
            }
        }
    }
    
    return count % MOD;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops iterate through all possible triplet combinations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for counting

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Triple Loop — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler