LeetCode 2552. Count Increasing Quadruplets Solution in Java, C++, Python & Go | Explanation + Code

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] × g[j][k].

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

PythonJavaC++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) )(code-box)

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; } }(code-box)

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; } };(code-box)

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) }(code-box)