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], anda < b < c < d
Example 1:
Input: nums = [1,2,3,6] Output: 1 Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.
Example 2:
Input: nums = [3,3,6,4,5] Output: 0 Explanation: There are no such quadruplets in [3,3,6,4,5].
Example 3:
Input: nums = [1,1,1,3,5] Output: 4 Explanation: The 4 quadruplets that satisfy the requirement are: - (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 <= 501 <= nums[i] <= 100Problem Overview: Given an integer array nums, count the number of quadruplets (a, b, c, d) such that a < b < c < d and nums[a] + nums[b] + nums[c] == nums[d]. The task is essentially finding ordered index combinations where the sum of three earlier elements equals a later element.
Approach 1: Naive Brute Force Enumeration (O(n4) time, O(1) space)
The most direct solution enumerates every possible quadruplet using four nested loops. The loops enforce the index constraint a < b < c < d. For each combination, compute nums[a] + nums[b] + nums[c] and compare it with nums[d]. If they match, increment the count. This approach is easy to implement and useful for understanding the structure of the problem, but the O(n4) runtime grows quickly as the array size increases. It mainly serves as a baseline enumeration technique for problems involving ordered index tuples in arrays.
Approach 2: Optimized Hash Map Approach (O(n2) time, O(n) space)
The key observation is that the equation nums[a] + nums[b] + nums[c] = nums[d] can be rearranged to nums[a] + nums[b] = nums[d] - nums[c]. Instead of checking all quadruplets, store differences (nums[d] - nums[c]) in a hash map while scanning from the right side of the array. Then iterate pairs (a, b) on the left and check whether their sum appears in the map. Each lookup is O(1) on average, turning the nested search into roughly O(n2). The map tracks how many valid (c, d) combinations produce a specific difference. This technique leverages constant‑time lookups from a hash table and reduces redundant enumeration.
This optimization works because the index ordering constraint allows the array to be split into two regions: pairs on the left and pairs on the right. By converting the equality condition into a difference lookup, you avoid repeatedly recomputing the same combinations. This is a common pattern in problems involving sums, pair matching, and enumeration with constraints.
Recommended for interviews: Start by explaining the brute force idea to demonstrate you understand the ordering constraint and the equation structure. Then derive the hash map optimization by rearranging the equation into a pair‑sum vs difference lookup. Interviewers usually expect the optimized O(n2) approach because it shows you can reduce multi‑loop enumeration using hashing.
This approach involves iterating through all combinations of four distinct indices (a, b, c, d) and checking if they satisfy the condition nums[a] + nums[b] + nums[c] == nums[d]. Loop every possible index to find all such quadruplets and count them.
This C implementation leverages four nested loops to check every combination of indices (a, b, c, d) for the condition nums[a] + nums[b] + nums[c] == nums[d]. For each valid quadruplet, it increments the count.
Time Complexity: O(n^4) where n is the length of the array.
Space Complexity: O(1) as only a constant amount of space is used.
The optimization focuses on reducing the number of loops by reversing the sum checking process. By using hash maps, you can precompute partial sums and efficiently check for matches.
This C solution uses a hash table to store possible values of nums[d] - nums[c] as keys and counts them. We iterate from the back of the array to avoid redundant loops.
Time Complexity: O(n^3).
Space Complexity: O(n), due to the use of hash map storage.
| Approach | Complexity |
|---|---|
| Naive Brute Force Approach | Time Complexity: O(n^4) where n is the length of the array. |
| Optimized Hash Map Approach | Time Complexity: O(n^3). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Brute Force Enumeration | O(n^4) | O(1) | Best for understanding the constraint a < b < c < d or when input size is very small. |
| Hash Map Optimization | O(n^2) | O(n) | Preferred solution in interviews and large inputs; reduces nested loops using constant‑time hash lookups. |
1995. Count Special Quadruplets (Leetcode Easy) • Programming Live with Larry • 1,962 views views
Watch 9 more video solutions →Practice Count Special Quadruplets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor