Count Increasing Quadruplets

Hard
1633.

Count Increasing Quadruplets

Count Increasing Quadruplets is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon interviews.

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, and
  • nums[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 <= 400
  • 1 <= nums[i] <= nums.length
  • all values are distinct (nums is a permutation)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countQuadruplets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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, and
  • nums[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 <= 400
  • 1 <= nums[i] <= nums.length
  • all values are distinct (nums is a permutation)

Hints for Count Increasing Quadruplets

  1. Hint 1

    Fix the middle pair (j, k) with j < k and nums[j] > nums[k]. The quadruplets through it number (indices i < j with nums[i] < nums[k]) × (indices l > k with nums[l] > nums[j]).

  2. Hint 2

    Those counts can be precomputed in prefix tables in O(n^2) — or folded into a single pass.

  3. Hint 3

    Single pass: scan l from left to right; for each earlier j, keep cnt[j] = number of pairs (i, k) with i < j < k < l, nums[i] < nums[k] < nums[j]. When nums[j] < nums[l], add cnt[j] to the answer; otherwise l can serve as a new k for j, adding the number of earlier indices with values below nums[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

  1. Keep cnt[j] = number of pairs (i, k) seen so far with i < j < k and nums[i] < nums[k] < nums[j].
  2. For each l from left to right, set smaller = 0 and scan j from 0 to l - 1:
  3. If nums[j] < nums[l]: every pair counted in cnt[j] combines with l (since nums[l] > nums[j]), so add cnt[j] to the answer, and increment smaller (one more index before l with a smaller value).
  4. Otherwise (nums[j] > nums[l]): l can be the k of a new pair for j, with any of the smaller indices before j as i — add smaller to cnt[j].
  5. 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 < l in value order — a 1-3-2-4 shape — not a plain increasing run.
  • In the original problem the count needs 64 bits; here n <= 400 keeps it inside 32 bits, but the O(n^4) brute force is far too slow either way.
  • Update cnt[j] with smaller as of index j — counting indices after j would break i < 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 ans

Java

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