# Count Increasing Quadruplets
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-increasing-quadruplets)
Canonical: https://scaleengineer.com/dsa/problems/count-increasing-quadruplets
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Binary Indexed Tree
**Companies:** [SAP](https://scaleengineer.com/companies/sap)
---
## Problem
Given a **0-indexed** integer array `nums` of size `n` containing all numbers from `1` to `n`, return _the number of increasing quadruplets_.

A quadruplet `(i, j, k, l)` is increasing if:

* `0 <= i < j < k < l < n`, and
* `nums[i] < nums[k] < nums[j] < nums[l]`.

**Example 1:**

**Input:** nums = [1,3,2,4,5]
**Output:** 2
**Explanation:** 
- When i = 0, j = 1, k = 2, and l = 3, nums[i] < nums[k] < nums[j] < nums[l].
- When i = 0, j = 1, k = 2, and l = 4, nums[i] < nums[k] < nums[j] < nums[l]. 
There are no other quadruplets, so we return 2.

**Example 2:**

**Input:** nums = [1,2,3,4]
**Output:** 0
**Explanation:** There exists only one quadruplet with i = 0, j = 1, k = 2, l = 3, but since nums[j] < nums[k], we return 0.

**Constraints:**

* `4 <= nums.length <= 4000`
* `1 <= nums[i] <= nums.length`
* All the integers of `nums` are **unique**. `nums` is a permutation.

# Approaches
## Brute Force Enumeration
The most straightforward approach is to check every possible quadruplet of indices `(i, j, k, l)`. We can use four nested loops to generate all combinations of four distinct indices in increasing order. For each combination, we then verify if the values at these indices, `nums[i]`, `nums[j]`, `nums[k]`, and `nums[l]`, satisfy the required condition: `nums[i] < nums[k] < nums[j] < nums[l]`.
**Time:** O(n^4) - Four nested loops iterate through all possible combinations of four indices, where `n` is the length of the array. This leads to a quartic time complexity. · **Space:** O(1) - We only use a few variables to store indices and the count, requiring constant extra space.
**Pros:** Simple to understand and implement.; Correctness is easy to verify.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
This method systematically explores the entire search space. It iterates through every possible set of four indices `i, j, k, l` that maintain the order `i < j < k < l`. For each valid set of indices, it performs a simple comparison to see if the corresponding array values meet the specified increasing quadruplet condition. If they do, a counter is incremented. While this approach is guaranteed to be correct, its computational cost is very high due to the four levels of nested loops, making it impractical for larger input sizes.

```java
class Solution {
    public long countIncreasingQuadruplets(int[] nums) {
        int n = nums.length;
        long count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        if (nums[i] < nums[k] && nums[k] < nums[j] && nums[j] < nums[l]) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use four nested loops to iterate through all possible combinations of indices `(i, j, k, l)` such that `0 <= i < j < k < l < n`.
   - The first loop for `i` runs from `0` to `n-4`.
   - The second loop for `j` runs from `i+1` to `n-3`.
   - The third loop for `k` runs from `j+1` to `n-2`.
   - The fourth loop for `l` runs from `k+1` to `n-1`.
3. Inside the innermost loop, check if the condition `nums[i] < nums[k] < nums[j] < nums[l]` is satisfied.
4. If the condition is true, increment the `count`.
5. After all loops complete, return the final `count`.

## Optimized Counting with Three Loops
We can improve upon the brute-force approach by reducing the number of nested loops from four to three. The idea is to fix the first two indices, `i` and `j`, and then efficiently count the number of valid pairs `(k, l)` that can complete the quadruplet. Instead of a naive nested loop for `k` and `l`, we can use a single backward pass for `k` while maintaining a count of valid `l`'s.
**Time:** O(n^3) - Three nested loops are used. The outer two loops iterate through `i` and `j`, and the inner loop iterates through `k`. This results in a cubic time complexity. · **Space:** O(1) - Only a few variables are needed for loops and counts.
**Pros:** A significant improvement over the O(n^4) brute-force approach.; Uses constant extra space.
**Cons:** Still too slow to pass the time limits for the given constraints (`n` up to 4000).
### Explanation
For each pair of indices `(i, j)`, we need to find the number of pairs `(k, l)` such that `j < k < l` and `nums[i] < nums[k] < nums[j] < nums[l]`. We can iterate `k` from `j+1` to `n-1` and for each `k`, count the valid `l`'s. This would still be O(n^4). 

To optimize, we can iterate `k` backwards from `n-2` down to `j+1`. As we iterate, we can maintain a count of how many numbers greater than `nums[j]` we have seen so far in the range `(k, n)`. Let's call this `greater_l_count`. When we are at index `k`, if `nums[i] < nums[k] < nums[j]`, we know that there are `greater_l_count` possible values for `l` that will satisfy the condition. We add this count to our total. This reduces one level of looping, bringing the complexity down to O(n^3).

```java
class Solution {
    public long countIncreasingQuadruplets(int[] nums) {
        int n = nums.length;
        long count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int greater_l_count = 0;
                for (int k = n - 1; k > j; k--) {
                    if (nums[j] < nums[k]) {
                        greater_l_count++;
                    }
                    if (nums[i] < nums[k] && nums[k] < nums[j]) {
                        count += greater_l_count;
                    }
                }
            }
        }
        return count;
    }
}
```
Note: The provided code snippet iterates `k` from `n-1` down to `j+1` and updates the count of `l`s inside the loop. This is a slightly different but equivalent implementation of the O(n^3) logic.
### Algorithm
1. Initialize `count = 0`.
2. Iterate through all possible pairs of indices `(i, j)` with `i < j`.
   - Loop `i` from `0` to `n-4`.
   - Loop `j` from `i+1` to `n-3`.
3. For each pair `(i, j)`, we need to count pairs `(k, l)` such that `j < k < l` and `nums[i] < nums[k] < nums[j] < nums[l]`.
4. To do this efficiently, we iterate with a third loop for `k` from `n-2` down to `j+1`.
5. Inside the `k` loop, we maintain a running count, `greater_l_count`, of indices `l > k` where `nums[l] > nums[j]`.
   - In each step of the `k` loop (from `n-2` down to `j+1`), we first update `greater_l_count` by checking `nums[k+1]`. If `nums[k+1] > nums[j]`, we increment `greater_l_count`.
   - Then, we check if the current `k` satisfies `nums[i] < nums[k] < nums[j]`.
   - If it does, it means we have found a valid `(i, j, k)` triplet, and any of the `l`'s counted in `greater_l_count` will form a valid quadruplet. So, we add `greater_l_count` to the total `count`.
6. After all loops complete, return `count`.

## Dynamic Programming with Space Optimization
The most efficient approach reduces the time complexity to O(n^2) by using dynamic programming or precomputation. The central idea is to fix the index `j` and then efficiently count the contributions of all possible `i`, `k`, and `l` indices that form a valid quadruplet with `j`.
**Time:** O(n^2) - The outer loop runs `n` times for `j`. Inside, computing the `less_before` array takes O(n), and the inner loop for `k` also takes O(n). The total complexity is O(n * (n + n)) = O(n^2). · **Space:** O(n) - For each `j`, we create a `less_before` array of size `n+1`, which is reused in each iteration of the outer loop.
**Pros:** Efficient enough to pass the time limits for the given constraints.; Demonstrates a good use of dynamic programming and precomputation to optimize a counting problem.
**Cons:** More complex to reason about and implement correctly.; Requires extra space proportional to `n`.
### Explanation
We iterate through each possible index `j` from `1` to `n-2`. For each `j`, our goal is to find the number of triplets `(i, k, l)` satisfying `i < j < k < l` and `nums[i] < nums[k] < nums[j] < nums[l]`.

For a fixed `j`, we can separate the problem into two independent counting subproblems:
1.  Counting `i`'s: For a given `k`, we need the number of indices `i < j` where `nums[i] < nums[k]`.
2.  Counting `l`'s: For a given `k`, we need the number of indices `l > k` where `nums[l] > nums[j]`.

To do this efficiently in O(n) time for each `j`, we can precompute the counts for the `i`'s. We create a prefix sum array, `less_before`, where `less_before[v]` stores the count of numbers less than `v` in `nums[0...j-1]`. This takes O(n) time and O(n) space for each `j`.

Then, we iterate `k` from `n-1` down to `j+1`. We maintain a running count `greater_after_count` of numbers seen so far (i.e., at indices greater than `k`) that are larger than `nums[j]`. When we encounter a `k` such that `nums[k] < nums[j]`, we can find the number of valid `i`'s in O(1) from our `less_before` array (`less_before[nums[k]]`) and multiply it by the current `greater_after_count` to get the number of new quadruplets found for this `(j, k)` pair.

This process is repeated for all `j`, leading to an overall time complexity of O(n^2).

```java
class Solution {
    public long countIncreasingQuadruplets(int[] nums) {
        int n = nums.length;
        long totalCount = 0;

        for (int j = 1; j < n - 2; j++) {
            // less_before[v] = count of i < j where nums[i] < v
            int[] less_before = new int[n + 1];
            for (int i = 0; i < j; i++) {
                if (nums[i] < nums[j]) { // Optimization: only need to count those < nums[j]
                    less_before[nums[i]]++;
                }
            }
            for (int v = 1; v <= n; v++) {
                less_before[v] += less_before[v - 1];
            }

            int greater_after_count = 0;
            for (int k = n - 1; k > j; k--) {
                if (nums[k] < nums[j]) {
                    // Count of i's where i < j and nums[i] < nums[k]
                    int less_count = less_before[nums[k] - 1];
                    totalCount += (long) less_count * greater_after_count;
                }
                if (nums[k] > nums[j]) {
                    greater_after_count++;
                }
            }
        }

        return totalCount;
    }
}
```
*Note: The code snippet contains a small optimization. When building `less_before`, we only care about `nums[i] < nums[j]`. Also, when querying `less_before`, we need values strictly less than `nums[k]`, so we query `less_before[nums[k]-1]`.*
### Algorithm
1. The main idea is to iterate through the index `j` and, for each `j`, count the number of valid `(i, k, l)` triplets.
2. The total count for a fixed `j` is the sum over `k` of `(count of valid i's) * (count of valid l's)`.
   `Sum for j = Σ (for k where j < k < n and nums[k] < nums[j]) [ (count of i < j where nums[i] < nums[k]) * (count of l > k where nums[l] > nums[j]) ]`
3. Initialize `total_count = 0`.
4. Loop `j` from `1` to `n-2`.
5.   For each `j`, pre-calculate an array `less_before` of size `n+1`. `less_before[v]` will store the number of indices `i < j` such that `nums[i] < v`. This can be computed in O(n) time.
6.   Initialize `greater_after_count = 0`. This variable will keep track of the number of elements `nums[l]` with `l > k` that are greater than `nums[j]` as we iterate `k` backwards.
7.   Loop `k` from `n-1` down to `j+1`.
8.     If `nums[k] > nums[j]`, it means this element could be a valid `nums[l]` for some quadruplet. We increment `greater_after_count`.
9.     If `nums[k] < nums[j]`, this `k` is a potential middle index. The number of valid `i`'s is `less_before[nums[k]]`, and the number of valid `l`'s is the current `greater_after_count`. We add their product, `less_before[nums[k]] * greater_after_count`, to `total_count`.
10. After the loops complete, return `total_count`.

# Solutions
### Java

```java
class Solution {
public
  long countQuadruplets(int[] nums) {
    int n = nums.length;
    int[][] f = new int[n][n];
    int[][] g = new int[n][n];
    for (int j = 1; j < n - 2; ++j) {
      int cnt = 0;
      for (int l = j + 1; l < n; ++l) {
        if (nums[l] > nums[j]) {
          ++cnt;
        }
      }
      for (int k = j + 1; k < n - 1; ++k) {
        if (nums[j] > nums[k]) {
          f[j][k] = cnt;
        } else {
          --cnt;
        }
      }
    }
    long ans = 0;
    for (int k = 2; k < n - 1; ++k) {
      int cnt = 0;
      for (int i = 0; i < k; ++i) {
        if (nums[i] < nums[k]) {
          ++cnt;
        }
      }
      for (int j = k - 1; j > 0; --j) {
        if (nums[j] > nums[k]) {
          g[j][k] = cnt;
          ans += (long)f[j][k] * g[j][k];
        } else {
          --cnt;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
const int N = 4001 ; int f [ N ][ N ]; int g [ N ][ N ]; class Solution { public: long long countQuadruplets ( vector < int >& nums ) { int n = nums . size (); memset ( f , 0 , sizeof f ); memset ( g , 0 , sizeof g ); for ( int j = 1 ; j < n - 2 ; ++ j ) { int cnt = 0 ; for ( int l = j + 1 ; l < n ; ++ l ) { if ( nums [ l ] > nums [ j ]) { ++ cnt ; } } for ( int k = j + 1 ; k < n - 1 ; ++ k ) { if ( nums [ j ] > nums [ k ]) { f [ j ][ k ] = cnt ; } else { -- cnt ; } } } long long ans = 0 ; for ( int k = 2 ; k < n - 1 ; ++ k ) { int cnt = 0 ; for ( int i = 0 ; i < k ; ++ i ) { if ( nums [ i ] < nums [ k ]) { ++ cnt ; } } for ( int j = k - 1 ; j > 0 ; -- j ) { if ( nums [ j ] > nums [ k ]) { g [ j ][ k ] = cnt ; ans += 1ll * f [ j ][ k ] * g [ j ][ k ]; } else { -- cnt ; } } } return ans ; } };
```

### Python

```python
class Solution:
    def countQuadruplets(self, nums: List[int]) -> int: n = len(nums) f = [[0] * n for _ in range(n)] g = [[0] * n for _ in range(n)] for j in range(1, n - 2): cnt = sum(nums[l] > nums[j] for l in range(j + 1, n)) for k in range(j + 1, n - 1): if nums[j] > nums[k]: f[j][k] = cnt else: cnt -= 1 for k in range(2, n - 1): cnt = sum(nums[i] < nums[k] for i in range(k)) for j in range(k - 1, 0, - 1): if nums[j] > nums[k]: g[j][k] = cnt else: cnt -= 1 return sum(f[j][k] * g[j][k] for j in range(1, n - 2) for k in range(j + 1, n - 1))

```