Count Special Triplets - Video Solutions

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.