Count Increasing Quadruplets — Problem & Solution
Count Increasing Quadruplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Increasing Quadruplets is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Prefix Sum, Enumeration, Binary Indexed Tree
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of length n that is a permutation of 1..n. A quadruplet of indices (i, j, k, l) is increasing when:
0 <= i < j < k < l < n, andnums[i] < nums[k] < nums[j] < nums[l].
Note the middle two are swapped: the value at k sits between the values at i and j. Return the number of increasing quadruplets.
CodeKairo note: n is at most 400 here (the original allows 4000), so the count — at most C(400, 4) — always fits in a 32-bit integer.
Example 1
Input: nums = [1,3,2,4,5]
Output: 2
Explanation: (0,1,2,3): 1 < 2 < 3 < 4, and (0,1,2,4): 1 < 2 < 3 < 5.
Example 2
Input: nums = [1,2,3,4]
Output: 0
Explanation: The only quadruplet has nums[k] = 3 > nums[j] = 2.
Example 3
Input: nums = [2,4,3,1,5]
Output: 1
Explanation: Only (0,1,2,4): 2 < 3 < 4 < 5.
Constraints
4 <= nums.length <= 4001 <= nums[i] <= nums.lengthall values are distinct (nums is a permutation)
Hints for Count Increasing Quadruplets
Hint 1
Fix the middle pair
(j, k)withj < kandnums[j] > nums[k]. The quadruplets through it number (indicesi < jwithnums[i] < nums[k]) × (indicesl > kwithnums[l] > nums[j]).Hint 2
Those counts can be precomputed in prefix tables in
O(n^2)— or folded into a single pass.Hint 3
Single pass: scan
lfrom left to right; for each earlierj, keepcnt[j]= number of pairs(i, k)withi < j < k < l,nums[i] < nums[k] < nums[j]. Whennums[j] < nums[l], addcnt[j]to the answer; otherwiselcan serve as a newkforj, adding the number of earlier indices with values belownums[l].
How to solve Count Increasing Quadruplets
Count by the middle pair. Sweeping the last index l and keeping, for every j, how many valid (i, k) pairs already sit around it gives an O(n^2) count without extra tables.
Approach
- Keep
cnt[j]= number of pairs(i, k)seen so far withi < j < kandnums[i] < nums[k] < nums[j]. - For each
lfrom left to right, setsmaller = 0and scanjfrom0tol - 1: - If
nums[j] < nums[l]: every pair counted incnt[j]combines withl(sincenums[l] > nums[j]), so addcnt[j]to the answer, and incrementsmaller(one more index beforelwith a smaller value). - Otherwise (
nums[j] > nums[l]):lcan be thekof a new pair forj, with any of thesmallerindices beforejasi— addsmallertocnt[j]. - Return the answer.
Why it works
When j is visited in the inner loop for a given l, smaller counts the indices i < j with nums[i] < nums[l], which is exactly the number of ways to pick i when l plays the role of k. And when nums[l] > nums[j], all pairs (i, k) recorded for j have k < l, so each forms a quadruplet with l. Every quadruplet is counted exactly once, at its l.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
- The pattern is
i < k < j < lin value order — a 1-3-2-4 shape — not a plain increasing run. - In the original problem the count needs 64 bits; here
n <= 400keeps it inside 32 bits, but theO(n^4)brute force is far too slow either way. - Update
cnt[j]withsmalleras of indexj— counting indices afterjwould breaki < j.
Reference solution
Python
from typing import List
def countQuadruplets(nums: List[int]) -> int:
n = len(nums)
cnt = [0] * n
ans = 0
for l in range(n):
smaller = 0
vl = nums[l]
for j in range(l):
if nums[j] < vl:
smaller += 1
ans += cnt[j]
else:
cnt[j] += smaller
return ansJava
public static int countQuadruplets(int[] nums) {
int n = nums.length;
int[] cnt = new int[n];
int ans = 0;
for (int l = 0; l < n; l++) {
int smaller = 0;
for (int j = 0; j < l; j++) {
if (nums[j] < nums[l]) { smaller++; ans += cnt[j]; }
else cnt[j] += smaller;
}
}
return ans;
}C++
int countQuadruplets(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(n, 0);
int ans = 0;
for (int l = 0; l < n; l++) {
int smaller = 0;
for (int j = 0; j < l; j++) {
if (nums[j] < nums[l]) { smaller++; ans += cnt[j]; }
else cnt[j] += smaller;
}
}
return ans;
}JavaScript
var countQuadruplets = function(nums) {
var n = nums.length, cnt = new Array(n).fill(0), ans = 0;
for (var l = 0; l < n; l++) {
var smaller = 0;
for (var j = 0; j < l; j++) {
if (nums[j] < nums[l]) { smaller++; ans += cnt[j]; }
else cnt[j] += smaller;
}
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming