2552. Count Increasing Quadruplets

Description

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.

Solutions

Solution 1: Enumeration + Preprocessing

We can enumerate \(j\) and \(k\) in the quadruplet, then the problem is transformed into, for the current \(j\) and \(k\):

• Count how many \(l\) satisfy \(l > k\) and \(nums[l] > nums[j]\);
• Count how many \(i\) satisfy \(i < j\) and \(nums[i] < nums[k]\).

We can use two two-dimensional arrays \(f\) and \(g\) to record these two pieces of information. Where \(f[j][k]\) represents how many \(l\) satisfy \(l > k\) and \(nums[l] > nums[j]\), and \(g[j][k]\) represents how many \(i\) satisfy \(i < j\) and \(nums[i] < nums[k]\).

Therefore, the answer is the sum of all \(f[j][k] \times g[j][k]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Where \(n\) is the length of the array.

Python3JavaC++Go

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

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

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

func countQuadruplets(nums []int) int64 {
    n := len(nums)
    f := make([][]int, n)
    g := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
        g[i] = make([]int, n)
    }
    for j := 1; j < n-2; j++ {
        cnt := 0
        for l := j + 1; l < n; l++ {
            if nums[l] > nums[j] {
                cnt++
            }
        }
        for k := j + 1; k < n-1; k++ {
            if nums[j] > nums[k] {
                f[j][k] = cnt
            } else {
                cnt--
            }
        }
    }
    ans := 0
    for k := 2; k < n-1; k++ {
        cnt := 0
        for i := 0; i < k; i++ {
            if nums[i] < nums[k] {
                cnt++
            }
        }
        for j := k - 1; j > 0; j-- {
            if nums[j] > nums[k] {
                g[j][k] = cnt
                ans += f[j][k] * g[j][k]
            } else {
                cnt--
            }
        }
    }
    return int64(ans)
}

Comments