Count Special Quadruplets: From Brute Force to Hash Map

LeetCode Count Special Quadruplets (problem 1995, easy) asks you to count the number of tuples (a, b, c, d) where a < b < c < d and nums[a] + nums[b] + nums[c] == nums[d]. At first glance it looks like you need four nested loops, but a clever rearrangement of the equation lets you solve it in O(n^2) with a hash map.

Why this problem matters

This is a classic example of reducing algorithmic complexity through algebraic manipulation. The brute force approach uses four nested loops and runs in O(n^4). By rearranging the equation from nums[a] + nums[b] + nums[c] = nums[d] to nums[a] + nums[b] = nums[d] - nums[c], you transform a four-variable search into a two-variable lookup problem. It is the same complement-lookup idea from Two Sum, applied to a 4-sum variant. Once you see this trick, you can apply it to many similar multi-sum problems.

Brute force approach

The most direct solution checks every valid combination of four indices. You loop through all (a, b, c, d) where a < b < c < d and test whether the sum condition holds.

def count_quadruplets(nums):
    n = len(nums)
    count = 0
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                for d in range(c + 1, n):
                    if nums[a] + nums[b] + nums[c] == nums[d]:
                        count += 1
    return count

This works perfectly for small arrays but becomes painfully slow as n grows. Four nested loops give you O(n^4) time, which is around 100 million operations for n = 100. You can do much better.

The hash map optimization

The key insight is rearranging the equation. Instead of nums[a] + nums[b] + nums[c] = nums[d], write it as:

nums[a] + nums[b] = nums[d] - nums[c]

Now the left side depends on two indices (a, b) and the right side depends on two indices (c, d). You can use a hash map to connect them.

The algorithm works by iterating c from right to left (from index n - 2 down to 2). For each value of c, you first add all nums[d] - nums[c] pairs where d > c into a count map. Then you loop through all pairs (a, b) where a < b < c and check whether nums[a] + nums[b] appears in the map. If it does, you add the stored count to your result.

Why iterate c from right to left? Because as c moves left, the set of valid d values (those to the right of c) grows. You accumulate differences in the map as you go, and each new position of c inherits all previously stored differences plus the new ones from the current c.

def count_quadruplets(nums):
    n = len(nums)
    count = 0
    diff_count = {}
    for c in range(n - 2, 1, -1):
        d = c + 1
        while d < n:
            diff = nums[d] - nums[c]
            diff_count[diff] = diff_count.get(diff, 0) + 1
            d += 1
        for a in range(c):
            for b in range(a + 1, c):
                pair_sum = nums[a] + nums[b]
                if pair_sum in diff_count:
                    count += diff_count[pair_sum]
    return count

Wait, that still looks like it might be O(n^3). Let me clarify. The inner loop over d for each c adds all new differences, and the double loop over (a, b) checks pair sums. But the d loop across all iterations of c does redundant work. Here is the tighter version that avoids recomputation:

def count_quadruplets(nums):
    n = len(nums)
    count = 0
    diff_count = {}
    for c in range(n - 2, 1, -1):
        for d in range(c + 1, n):
            diff = nums[d] - nums[c]
            diff_count[diff] = diff_count.get(diff, 0) + 1
        for a in range(c):
            for b in range(a + 1, c):
                pair_sum = nums[a] + nums[b]
                if pair_sum in diff_count:
                    count += diff_count[pair_sum]
    return count

The total work for the (a, b) pairs across all values of c is O(n^2) because each pair is checked at most once for the smallest valid c. The map insertions are also bounded. The overall time complexity is O(n^2).

Step-by-step walkthrough

Let's trace through nums = [1, 2, 3, 6] using the hash map approach. The equation becomes nums[a] + nums[b] = nums[d] - nums[c].

The map acts as a running tally of all nums[d] - nums[c] differences seen so far. Each time you fix a new c and scan the (a, b) pairs, you are checking: "Does any pair sum match a difference I have already recorded?" This is the complement-lookup pattern applied at a higher level.

Complexity analysis

Time: The brute force checks all four-index combinations. The hash map approach reduces this to O(n^2) by precomputing differences and looking up pair sums.

Space: The hash map stores up to O(n^2) distinct difference values in the worst case, one for each (c, d) pair.

The building blocks

Two building blocks make this optimization possible:

Hash map for complement lookup. You have seen this in Two Sum: compute what you need, check the map, store what you have. Here the "complement" is nums[d] - nums[c], and the "query" is nums[a] + nums[b]. Same idea, different equation.

Equation rearrangement. When a problem involves three or more variables summing to a target, try splitting the equation into two halves. A + B + C = D becomes A + B = D - C. Each half depends on fewer variables, which means fewer nested loops. This technique appears in problems like 4Sum II and other multi-sum variants.

Edge cases

• Array of length 4. The smallest valid input. There is exactly one possible tuple (0, 1, 2, 3). Check whether nums[0] + nums[1] + nums[2] == nums[3].
• No valid quadruplets. If no four indices satisfy the condition, return 0. The algorithm handles this naturally since the map lookup will never find a match.
• All same elements. For an array like [0, 0, 0, 0], every valid tuple is a special quadruplet because 0 + 0 + 0 = 0. With n elements, the count is C(n, 4), the number of ways to choose 4 indices.
• Duplicate values with different indices. The problem counts tuples of indices, not tuples of values. Two tuples with the same values but different indices count separately. The hash map approach handles this correctly because it counts occurrences rather than just checking existence.

From understanding to recall

The equation rearrangement trick is the kind of insight that feels obvious in hindsight but is easy to miss under pressure. You see nums[a] + nums[b] + nums[c] = nums[d] and your instinct is to nest four loops. The mental shift to "split this into two sides and use a map" requires practice.

Try solving this problem from scratch without looking at the solution. Then come back to it in a few days. If you can reproduce the rearrangement and the right-to-left iteration order from memory, the pattern is yours. If you get stuck, that tells you exactly which piece needs more repetition.

Related posts

• Two Sum - The foundational complement-lookup pattern that this problem extends
• 4Sum - A related four-element problem using sorting and two pointers instead of hash maps
• 3Sum Closest - Another multi-sum problem showing how to reduce nested loops