2552

2552. Count Increasing Quadruplets (Hard)

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.

Companies: TikTok, SAP

Related Topics:
Array, Dynamic Programming, Binary Indexed Tree, Enumeration, Prefix Sum

Similar Questions:

• Increasing Triplet Subsequence (Medium)
• Count Special Quadruplets (Easy)
• Count Good Triplets in an Array (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/count-increasing-quadruplets
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/count-increasing-quadruplets/solutions/3111697
class Solution {
public:
    long long countQuadruplets(vector<int>& A) {
        long long N = A.size(), ans = 0;
        vector<long long> cnt(N); // cnt[i] is the number of all 132 triplets with A[i] as the middle number
        for (int j = 0; j < N; ++j) {
            long long prevSmall = 0; // the number of values smaller than A[j]
            for (int i = 0; i < j; ++i) {
                if (A[i] < A[j]) {
                    prevSmall++;
                    ans += cnt[i];
                } else if (A[i] > A[j]) cnt[i] += prevSmall;
            }
        }
        return ans;
    }
};