Count Special Quadruplets

Difficulty: Easy | Acceptance: 64.70% | Paid: No Topics: Array, Hash Table, Enumeration

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:

nums[a] + nums[b] + nums[c] == nums[d], and a < b < c < d

• Examples
• Constraints
• Brute Force
• Hash Map - Enumerate b from Right
• Hash Map - Enumerate c from Left

Examples

Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the condition is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets.

Input: nums = [1,1,1,3,5]
Output: 4
Explanation: There are 4 quadruplets that satisfy the condition:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

Constraints

4 <= nums.length <= 50
1 <= nums[i] <= 100

Brute Force

Intuition Check all possible quadruplets using four nested loops, verifying if the sum of the first three equals the fourth.

Steps

• Iterate through all valid index combinations with a < b < c < d
• Check if nums[a] + nums[b] + nums[c] equals nums[d]
• Count all valid quadruplets found

from typing import List

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        for a in range(n - 3):
            for b in range(a + 1, n - 2):
                for c in range(b + 1, n - 1):
                    for d in range(c + 1, n):
                        if nums[a] + nums[b] + nums[c] == nums[d]:
                            count += 1
        return count

Complexity

• Time: O(n⁴)
• Space: O(1)
• Notes: Simple but inefficient for larger arrays. Works within constraints since n ≤ 50.

Hash Map - Enumerate b from Right

Intuition Rewrite the condition as nums[a] + nums[b] == nums[d] - nums[c]. Iterate b from right to left, maintaining a frequency map of differences nums[d] - nums[c] for pairs (c, d) where c > b.

Steps

• Iterate b from n-2 down to 1
• For each b, add all pairs (c=b+1, d>c) to a difference map
• For all a < b, check if nums[a] + nums[b] exists in the map and accumulate counts

from typing import List

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        diff_map = {}
        
        for b in range(n - 2, 0, -1):
            for d in range(b + 2, n):
                c = b + 1
                diff = nums[d] - nums[c]
                diff_map[diff] = diff_map.get(diff, 0) + 1
            
            for a in range(b):
                target = nums[a] + nums[b]
                if target in diff_map:
                    count += diff_map[target]
        
        return count

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Optimal solution using hash map to store differences, reducing from O(n⁴) to O(n²).

Hash Map - Enumerate c from Left

Intuition Rewrite as nums[a] + nums[b] == nums[d] - nums[c]. Iterate c from left to right, maintaining a frequency map of sums nums[a] + nums[b] for pairs (a, b) where b < c.

Steps

• Iterate c from 1 to n-2
• For each c, add all pairs (a, b=c-1) where a < b to a sum map
• For all d > c, check if nums[d] - nums[c] exists in the map and accumulate counts

from typing import List

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        sum_map = {}
        
        for c in range(1, n - 1):
            for a in range(c - 1):
                b = c - 1
                s = nums[a] + nums[b]
                sum_map[s] = sum_map.get(s, 0) + 1
            
            for d in range(c + 1, n):
                target = nums[d] - nums[c]
                if target in sum_map:
                    count += sum_map[target]
        
        return count

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Alternative optimal approach storing sums instead of differences. Same complexity as the previous hash map method.