Count Increasing Quadruplets - Problem
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]
Notice the specific ordering pattern: element at position k comes between elements at positions i and j in value, creating a unique increasing subsequence pattern.
Input & Output
Example 1 — Basic Case
$
Input:
nums = [1,3,2,4,5]
›
Output:
2
💡 Note:
Two valid quadruplets: (0,1,2,3) where 1<2<3<4, and (0,1,2,4) where 1<2<3<5. Both follow the pattern nums[i]
Example 2 — No Valid Quadruplets
$
Input:
nums = [4,3,2,1]
›
Output:
0
💡 Note:
Array is decreasing, so no quadruplet can satisfy the increasing condition nums[i] < nums[k] < nums[j] < nums[l].
Example 3 — Complex Pattern
$
Input:
nums = [4,1,5,2,6,3]
›
Output:
3
💡 Note:
Valid quadruplets: (1,2,3,4) gives 1<2<5<6, (1,2,5,4) gives 1<3<5<6, and (1,4,5,2) gives 1<3<6
Constraints
- 4 ≤ nums.length ≤ 4000
- 1 ≤ nums[i] ≤ nums.length
- All values in nums are unique
- nums contains all integers from 1 to n
Visualization
Tap to expand
Understanding the Visualization
1
Input Array
Array with values 1 to n in some permutation
2
Find Pattern
Locate indices i<j<k<l with crossing value pattern
3
Count Valid
Return total count of valid quadruplets
Key Takeaway
🎯 Key Insight: The pattern requires a "crossing" where the middle values nums[k] and nums[j] are out of position order
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code
Test Cases
0 passed
0 failed
3 pending