Count Increasing Quadruplets

Hard

#2332Time: 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.1 company

Patterns

Dynamic Programming Enumeration Prefix Sum

Data structures

Array Binary Indexed Tree

Companies

SAP

Prompt

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

3 approaches with complexity analysis and trade-offs.

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].

Algorithm

Initialize a counter count to 0.
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.
Inside the innermost loop, check if the condition nums[i] < nums[k] < nums[j] < nums[l] is satisfied.
If the condition is true, increment the count.
After all loops complete, return the final count.

Walkthrough

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.

1class Solution {2    public long countIncreasingQuadruplets(int[] nums) {3        int n = nums.length;4        long count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                for (int k = j + 1; k < n; k++) {8                    for (int l = k + 1; l < n; l++) {9                        if (nums[i] < nums[k] && nums[k] < nums[j] && nums[j] < nums[l]) {10                            count++;11                        }12                    }13                }14            }15        }16        return count;17    }18}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Initialize count = 0.
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.
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].
To do this efficiently, we iterate with a third loop for k from n-2 down to j+1.
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.
After all loops complete, return count.

Walkthrough

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).

1class Solution {2    public long countIncreasingQuadruplets(int[] nums) {3        int n = nums.length;4        long count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                int greater_l_count = 0;8                for (int k = n - 1; k > j; k--) {9                    if (nums[j] < nums[k]) {10                        greater_l_count++;11                    }12                    if (nums[i] < nums[k] && nums[k] < nums[j]) {13                        count += greater_l_count;14                    }15                }16            }17        }18        return count;19    }20}

Note: The provided code snippet iterates k from n-1 down to j+1 and updates the count of ls inside the loop. This is a slightly different but equivalent implementation of the O(n^3) logic.

Complexity

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.

Trade-offs

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).

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.

Algorithm

The main idea is to iterate through the index j and, for each j, count the number of valid (i, k, l) triplets.

The total count for a fixed j is the sum over k of (count of valid i's) * (count of valid l's).

1Sum 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]) ]

Initialize total_count = 0.
Loop j from 1 to n-2.
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.
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.
Loop k from n-1 down to j+1.

1If `nums[k] > nums[j]`, it means this element could be a valid `nums[l]` for some quadruplet. We increment `greater_after_count`.

1If `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`.

After the loops complete, return total_count.

Walkthrough

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:

Counting i's: For a given k, we need the number of indices i < j where nums[i] < nums[k].
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).

1class Solution {2    public long countIncreasingQuadruplets(int[] nums) {3        int n = nums.length;4        long totalCount = 0;5 6        for (int j = 1; j < n - 2; j++) {7            // less_before[v] = count of i < j where nums[i] < v8            int[] less_before = new int[n + 1];9            for (int i = 0; i < j; i++) {10                if (nums[i] < nums[j]) { // Optimization: only need to count those < nums[j]11                    less_before[nums[i]]++;12                }13            }14            for (int v = 1; v <= n; v++) {15                less_before[v] += less_before[v - 1];16            }17 18            int greater_after_count = 0;19            for (int k = n - 1; k > j; k--) {20                if (nums[k] < nums[j]) {21                    // Count of i's where i < j and nums[i] < nums[k]22                    int less_count = less_before[nums[k] - 1];23                    totalCount += (long) less_count * greater_after_count;24                }25                if (nums[k] > nums[j]) {26                    greater_after_count++;27                }28            }29        }30 31        return totalCount;32    }33}

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].

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  long countQuadruplets(int[] nums) {4    int n = nums.length;5    int[][] f = new int[n][n];6    int[][] g = new int[n][n];7    for (int j = 1; j < n - 2; ++j) {8      int cnt = 0;9      for (int l = j + 1; l < n; ++l) {10        if (nums[l] > nums[j]) {11          ++cnt;12        }13      }14      for (int k = j + 1; k < n - 1; ++k) {15        if (nums[j] > nums[k]) {16          f[j][k] = cnt;17        } else {18          --cnt;19        }20      }21    }22    long ans = 0;23    for (int k = 2; k < n - 1; ++k) {24      int cnt = 0;25      for (int i = 0; i < k; ++i) {26        if (nums[i] < nums[k]) {27          ++cnt;28        }29      }30      for (int j = k - 1; j > 0; --j) {31        if (nums[j] > nums[k]) {32          g[j][k] = cnt;33          ans += (long)f[j][k] * g[j][k];34        } else {35          --cnt;36        }37      }38    }39    return ans;40  }41}

1const 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 ; } };

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  long countQuadruplets(int[] nums) {4    int n = nums.length;5    int[][] f = new int[n][n];6    int[][] g = new int[n][n];7    for (int j = 1; j < n - 2; ++j) {8      int cnt = 0;9      for (int l = j + 1; l < n; ++l) {10        if (nums[l] > nums[j]) {11          ++cnt;12        }13      }14      for (int k = j + 1; k < n - 1; ++k) {15        if (nums[j] > nums[k]) {16          f[j][k] = cnt;17        } else {18          --cnt;19        }20      }21    }22    long ans = 0;23    for (int k = 2; k < n - 1; ++k) {24      int cnt = 0;25      for (int i = 0; i < k; ++i) {26        if (nums[i] < nums[k]) {27          ++cnt;28        }29      }30      for (int j = k - 1; j > 0; --j) {31        if (nums[j] > nums[k]) {32          g[j][k] = cnt;33          ans += (long)f[j][k] * g[j][k];34        } else {35          --cnt;36        }37      }38    }39    return ans;40  }41}

1const 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 ; } };

1class Solution:2    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))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.