Count Special Quadruplets

EASY

Description

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

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

Approaches

Checkout 2 different approaches to solve Count Special Quadruplets. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The most straightforward way to solve this problem is to check every possible quadruplet of indices (a, b, c, d). We can use four nested loops to generate all combinations of four distinct indices that satisfy the condition a < b < c < d. For each valid combination of indices, we then check if the sum of the values at the first three indices equals the value at the fourth index. If it does, we increment a counter.

Algorithm

Initialize a counter count to 0.
Get the length of the array, n.
Use four nested loops to iterate through all possible combinations of indices a, b, c, and d such that 0 <= a < b < c < d < n.
- The outer loop for a runs from 0 to n-4.
- The second loop for b runs from a+1 to n-3.
- The third loop for c runs from b+1 to n-2.
- The innermost loop for d runs from c+1 to n-1.
Inside the innermost loop, check if the condition nums[a] + nums[b] + nums[c] == nums[d] is met.
If the condition is true, increment the count.
After all loops complete, return the final count.

This approach directly translates the problem statement into code. We systematically generate every unique quadruplet of indices (a, b, c, d) ensuring they are in increasing order. The four nested loops handle this generation. The first loop picks index a, the second picks b greater than a, the third picks c greater than b, and the fourth picks d greater than c. For each such quadruplet, we perform the sum check nums[a] + nums[b] + nums[c] == nums[d]. If they are equal, we've found a special quadruplet and increment our result counter.

class Solution {
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int a = 0; a < n; a++) {
            for (int b = a + 1; b < n; b++) {
                for (int c = b + 1; c < n; c++) {
                    for (int d = c + 1; d < n; d++) {
                        if (nums[a] + nums[b] + nums[c] == nums[d]) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n^4) - There are four nested loops, each iterating up to `n` times. This results in a quartic time complexity. Given `n <= 50`, `50^4 = 6,250,000`, which is acceptable.Space Complexity: O(1) - We only use a few variables to store the loop indices and the count, so the space required is constant.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Highly inefficient due to its O(n^4) time complexity.
Will likely result in a 'Time Limit Exceeded' error for larger constraints, although it passes for this problem given n <= 50.

Code Solutions

Checking out 3 solutions in different languages for Count Special Quadruplets. Click on different languages to view the code.

class Solution { public int countQuadruplets ( int [] nums ) { int ans = 0 , n = nums . length ; for ( int a = 0 ; a < n - 3 ; ++ a ) { for ( int b = a + 1 ; b < n - 2 ; ++ b ) { for ( int c = b + 1 ; c < n - 1 ; ++ c ) { for ( int d = c + 1 ; d < n ; ++ d ) { if ( nums [ a ] + nums [ b ] + nums [ c ] == nums [ d ]) { ++ ans ; } } } } } return ans ; } }

Video Solution

Watch the video walkthrough for Count Special Quadruplets

Patterns:

Enumeration

Data Structures:

ArrayHash Table