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.