# Count Special Quadruplets
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-special-quadruplets)
Canonical: https://scaleengineer.com/dsa/problems/count-special-quadruplets
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
---
## Problem
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
## 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.
**Time:** 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:** O(1) - We only use a few variables to store the loop indices and the count, so the space required is constant.
**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`.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Get the length of the array, `n`.
3. 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`.
4. Inside the innermost loop, check if the condition `nums[a] + nums[b] + nums[c] == nums[d]` is met.
5. If the condition is true, increment the `count`.
6. After all loops complete, return the final `count`.

## Using a Frequency Map
We can improve upon the brute-force approach by reducing the time complexity from O(n^4) to O(n^3). The key is to avoid the innermost loop that searches for `d`. Instead of a linear search, we can use a frequency map to check for the existence of `nums[d]` in O(1) time. By iterating through the indices `a`, `b`, and `c`, we calculate the target sum `S = nums[a] + nums[b] + nums[c]`. Then, we check how many times the value `S` appears in the array at an index `d` greater than `c`.
**Time:** O(n^3) - We have three nested loops. The outer loop for `c` runs about `n` times. The two inner loops for `a` and `b` together run O(c^2) times, which is O(n^2) in the worst case. This gives a total time complexity of O(n^3). · **Space:** O(M) - Where `M` is the maximum possible value of `nums[i]`. Since the constraints state `nums[i] <= 100`, the space complexity is O(101), which is constant.
**Pros:** Significantly more efficient than the brute-force approach.; Passes well within time limits for the given constraints.; Uses constant extra space due to the small range of values in `nums`.
**Cons:** The logic is more complex than the brute-force approach.
### Explanation
To implement this efficiently, we can iterate the index `c` backwards from `n-2` down to `2`. We maintain a frequency map (an array `freq` is sufficient due to the small range of `nums[i]`) that, for a given `c`, stores the frequency of each number `nums[k]` for all `k > c`. 

As we decrement `c` in our main loop, we can update this frequency map incrementally. For example, when moving from `c` to `c-1`, the element `nums[c]` now becomes a potential `nums[d]` for future triplets, so we add it to our frequency map. 

For each fixed `c`, we iterate through all possible pairs of `a` and `b` (where `a < b < c`). We calculate their sum with `nums[c]` and look up this sum in our frequency map. The value from the map tells us how many valid `d`'s exist for this specific triplet `(a, b, c)`, which we add to our total count.

```java
class Solution {
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int count = 0;
        // freq[v] will store the count of v in nums[k] where k > c
        int[] freq = new int[101]; // Max value of nums[i] is 100

        // Let the indices be a < b < c < d
        // We will iterate c from n-2 down to 2
        for (int c = n - 2; c >= 2; c--) {
            // For the current c, we update the frequency map to include the element
            // at index c+1, which can now act as a 'd' for smaller 'c's.
            freq[nums[c + 1]]++;

            // Now, for this fixed c, find pairs (a, b) where a < b < c
            for (int a = 0; a < c; a++) {
                for (int b = a + 1; b < c; b++) {
                    int sum = nums[a] + nums[b] + nums[c];
                    if (sum <= 100) {
                        // freq[sum] gives the number of d's such that d > c and nums[d] == sum
                        count += freq[sum];
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. The core idea is to rearrange the equation to `nums[d] = nums[a] + nums[b] + nums[c]` and optimize the search for `d`.
2. We can iterate through the third index, `c`, from `n-2` down to `2`.
3. For each `c`, we need to find pairs `(a, b)` with `a < b < c` and an index `d` with `d > c` that satisfy the equation.
4. To do this efficiently, we maintain a frequency map (an array, since `nums[i]` values are small) that stores the counts of `nums[d]` for all `d > c`.
5. The algorithm proceeds as follows:
   - Initialize `count = 0`.
   - Initialize a frequency array `freq` of size 101 (since `1 <= nums[i] <= 100`) to all zeros.
   - Loop `c` from `n-2` down to `2`.
     - In each iteration, first update the `freq` array by incrementing the count for `nums[c+1]`. This ensures `freq` always stores the frequencies of elements with indices greater than the current `c`.
     - Then, use two nested loops to iterate through all pairs `(a, b)` such that `a < b < c`.
     - For each pair, calculate `sum = nums[a] + nums[b] + nums[c]`.
     - If `sum` is within the valid range (i.e., `<= 100`), add `freq[sum]` to the total `count`. This `freq[sum]` represents the number of valid `d`'s we found for the current triplet `(a, b, c)`.
6. After the loops complete, return `count`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution {
public:
  int countQuadruplets(vector<int> &nums) {
    int ans = 0, n = nums.size();
    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;
  }
};

```

### Python

```python
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

```