Scale Engineer

Count Special Triplets

Med
#3190Time: O(N^3) - Three nested loops iterate through the array, where N is the length of `nums`. This results in a cubic time complexity.Space: O(1) - Constant extra space is used.
Patterns
Counting
Data structures
ArrayHash Table

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to use three nested loops to check every possible triplet of indices (i, j, k) that satisfy i < j < k. For each triplet, we verify if it meets the special triplet conditions. This method is easy to conceptualize but computationally very expensive.

Algorithm

  • Initialize a counter count to 0.
  • Use three nested loops to iterate through all possible triplets of indices (i, j, k) such that 0 <= i < j < k < n.
  • Inside the innermost loop, check if the conditions nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2 are met.
  • If the conditions are true, increment the count.
  • After iterating through all triplets, return count modulo 10^9 + 7.

Walkthrough

This method iterates through all combinations of three distinct indices i, j, and k from the array. The loops are structured to ensure that i < j < k, which is a requirement for the triplet. For each valid combination of indices, it performs a check to see if nums[i] and nums[k] are both equal to nums[j] * 2. A counter is maintained to keep track of how many such triplets are found.

class Solution {    public int countSpecialTriplets(int[] nums) {        int n = nums.length;        long count = 0;        int MOD = 1_000_000_007;         for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                for (int k = j + 1; k < n; k++) {                    // Use long for multiplication to prevent potential overflow, though not strictly necessary with given constraints.                    if ((long)nums[i] == (long)nums[j] * 2 && (long)nums[k] == (long)nums[j] * 2) {                        count++;                    }                }            }        }        return (int)(count % MOD);    }}

Complexity

Time

O(N^3) - Three nested loops iterate through the array, where N is the length of `nums`. This results in a cubic time complexity.

Space

O(1) - Constant extra space is used.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space.

Cons

  • Extremely inefficient and will lead to a 'Time Limit Exceeded' error for the given constraints.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem