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, and
  • nums[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
Count Increasing Quadruplets: Find Crossing PatternsInput: [1,3,2,4,5] → Find quadruplets (i,j,k,l) where nums[i] < nums[k] < nums[j] < nums[l]13245i=0j=1k=2l=3l=4Pattern: 1 < 2 < 3 < 4 (Valid ✓)Pattern: 1 < 2 < 3 < 5 (Valid ✓)Output: 2 valid quadruplets foundKey: Values cross - middle elements are out of position order
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
Asked in
Google 15 Facebook 12 Amazon 8
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen
Algorithm Visualization
Pinch to zoom • Tap outside to close
Test Cases
0 passed
0 failed
3 pending

Select Compiler

Choose a programming language

Compiler list would appear here...