Skip to content

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

Thinking

Count quadruples \(i<j<k<l\) with \(nums[i]<nums[k]<nums[j]<nums[l]\). A four-fold loop fails at \(n\le 4000\), and naive side counts for each \((j,k)\) can still be cubic.

Fix \(j\) and sweep \(k\) rightward while decrementing the number of later values \(>nums[j]\), storing \(f[j][k]\). Symmetrically sweep \(j\) left of each \(k\) for \(g[j][k]\). Multiply the two only when \(nums[j]>nums[k]\). The whole pass is \(O(n^2)\).

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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