#1995

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Special Quadruplets

Count Special Quadruplets requires scanning arrays and using hash lookups to efficiently find quadruplets matching sum conditions.

array hash table enumeration

Problem Statement

Given a 0-indexed integer array nums, count all distinct quadruplets (a, b, c, d) where a < b < c < d and nums[a] + nums[b] + nums[c] == nums[d]. Return the total count of such quadruplets.

For example, given nums = [1,2,3,6], there is exactly one quadruplet (0,1,2,3) because 1 + 2 + 3 equals 6. For nums = [3,3,6,4,5], no quadruplets satisfy the condition. Ensure your solution efficiently handles small arrays up to length 50 using array scanning plus hash lookup.

Examples

Example 1

Input: nums = [1,2,3,6]

Output: 1

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

There are no such quadruplets in [3,3,6,4,5].

Example 3

Input: nums = [1,1,1,3,5]

Output: 4

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 <= 50
1 <= nums[i] <= 100

Solution Approach

Brute Force Triple Loop

Use three nested loops to pick indices a, b, c, and check for each d > c if nums[a] + nums[b] + nums[c] equals nums[d]. This works but has O(n^4) time complexity, which is acceptable only for very small arrays.

Optimized Hash Map Lookup

Iterate through c and d from the end, storing nums[d] - nums[c] in a hash map. Then, scan a and b to check if nums[a] + nums[b] exists in the map. This reduces redundant checks and exploits the pattern of array scanning plus hash lookup.

Early Sum Pruning

Because all numbers are positive and array length is small, skip combinations where the partial sum exceeds possible nums[d]. This reduces unnecessary hash lookups and nested iterations without affecting correctness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n^3) with hash optimization to O(n^4) for pure brute force. Space complexity is O(n) for hash map storage. Small array size allows these approaches to run efficiently.

What Interviewers Usually Probe

Expect questions on handling duplicate numbers in quadruplets.
They may probe if you can reduce four nested loops using a hash table.
Look for awareness of early pruning opportunities to speed up array scans.

Common Pitfalls or Variants

Common pitfalls

Counting quadruplets incorrectly when indices are not strictly increasing.
Failing to use hash lookup and iterating unnecessarily over d multiple times.
Overlooking array length constraints and optimizing prematurely for larger n.

Follow-up variants

Count quadruplets where nums[a] * nums[b] * nums[c] equals nums[d].
Find quadruplets with any sum equal to a target value instead of the fourth element.
Return indices of quadruplets instead of just counting them.

FAQ

What is the main pattern used in Count Special Quadruplets?

The primary pattern is array scanning plus hash lookup to efficiently find sums of triplets matching a later element.

Can the array contain duplicates and still produce valid quadruplets?

Yes, duplicates are allowed, but quadruplet indices must be strictly increasing, so repeated numbers can form different valid quadruplets.

Is brute force acceptable for this problem?

Brute force with four nested loops works for very small arrays, but hash map optimization is recommended to avoid O(n^4) time.

How do I handle the constraint 4 <= nums.length <= 50?

Use the small array size to your advantage: optimized triple loops with hash lookup are fast enough within these bounds.

Can we use early pruning in Count Special Quadruplets?

Yes, skip combinations where the sum of the first three numbers exceeds any possible nums[d], reducing unnecessary iterations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        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]:
                            ans += 1
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        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]:
                            ans += 1
        return ans

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        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]:
                            ans += 1
        return ans

Continue Practicing

#2025 maximum number of ways to partition an array #2094 finding 3 digit even numbers #2122 recover the original array