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, andnums[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 <= 40001 <= 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.
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)
}
|
