Count Increasing Quadruplets
HardPrompt
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
numsare unique.numsis a permutation.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible quadruplet of indices (i, j, k, l). We can use four nested loops to generate all combinations of four distinct indices in increasing order. For each combination, we then verify if the values at these indices, nums[i], nums[j], nums[k], and nums[l], satisfy the required condition: nums[i] < nums[k] < nums[j] < nums[l].
Algorithm
- Initialize a counter
countto 0. - Use four nested loops to iterate through all possible combinations of indices
(i, j, k, l)such that0 <= i < j < k < l < n.- The first loop for
iruns from0ton-4. - The second loop for
jruns fromi+1ton-3. - The third loop for
kruns fromj+1ton-2. - The fourth loop for
lruns fromk+1ton-1.
- The first loop for
- Inside the innermost loop, check if the condition
nums[i] < nums[k] < nums[j] < nums[l]is satisfied. - If the condition is true, increment the
count. - After all loops complete, return the final
count.
Walkthrough
This method systematically explores the entire search space. It iterates through every possible set of four indices i, j, k, l that maintain the order i < j < k < l. For each valid set of indices, it performs a simple comparison to see if the corresponding array values meet the specified increasing quadruplet condition. If they do, a counter is incremented. While this approach is guaranteed to be correct, its computational cost is very high due to the four levels of nested loops, making it impractical for larger input sizes.
class Solution { public long countIncreasingQuadruplets(int[] nums) { int n = nums.length; long count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { for (int l = k + 1; l < n; l++) { if (nums[i] < nums[k] && nums[k] < nums[j] && nums[j] < nums[l]) { count++; } } } } } return count; }}Complexity
Time
O(n^4) - Four nested loops iterate through all possible combinations of four indices, where `n` is the length of the array. This leads to a quartic time complexity.
Space
O(1) - We only use a few variables to store indices and the count, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement.
Correctness is easy to verify.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.