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].

Examples

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 <= 4000
• 1 <= nums[i] <= nums.length
• All the integers of nums are unique. nums is a permutation.

Solution

Method 1 – Prefix/Suffix Counting (Enumeration)

Intuition

For each possible j and k (with j < k), count how many i < j have nums[i] < nums[k] and how many l > k have nums[j] < nums[l]. The answer is the sum over all (j, k) of the product of these two counts.

Approach

1. For each k from 1 to n-2:
   • For each j from 0 to k-1:
     • If nums[j] < nums[k], increment a prefix count.
   • For each l from k+1 to n-1:
     • If nums[j] < nums[l], increment a suffix count.
   • For each (j, k), multiply the prefix and suffix counts and add to the answer.
2. Return the total answer.

Code

C++

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int k = 1; k < n - 2; ++k) {
            for (int j = 0; j < k; ++j) {
                if (nums[j] < nums[k]) {
                    int left = 0, right = 0;
                    for (int i = 0; i < j; ++i) if (nums[i] < nums[k]) left++;
                    for (int l = k + 1; l < n; ++l) if (nums[j] < nums[l]) right++;
                    ans += left * right;
                }
            }
        }
        return ans;
    }
};

Go

func countQuadruplets(nums []int) int {
    n, ans := len(nums), 0
    for k := 1; k < n-2; k++ {
        for j := 0; j < k; j++ {
            if nums[j] < nums[k] {
                left, right := 0, 0
                for i := 0; i < j; i++ {
                    if nums[i] < nums[k] { left++ }
                }
                for l := k+1; l < n; l++ {
                    if nums[j] < nums[l] { right++ }
                }
                ans += left * right
            }
        }
    }
    return ans
}

Java

class Solution {
    public int countQuadruplets(int[] nums) {
        int n = nums.length, ans = 0;
        for (int k = 1; k < n - 2; ++k) {
            for (int j = 0; j < k; ++j) {
                if (nums[j] < nums[k]) {
                    int left = 0, right = 0;
                    for (int i = 0; i < j; ++i) if (nums[i] < nums[k]) left++;
                    for (int l = k + 1; l < n; ++l) if (nums[j] < nums[l]) right++;
                    ans += left * right;
                }
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countQuadruplets(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        for (k in 1 until n-2) {
            for (j in 0 until k) {
                if (nums[j] < nums[k]) {
                    var left = 0
                    var right = 0
                    for (i in 0 until j) if (nums[i] < nums[k]) left++
                    for (l in k+1 until n) if (nums[j] < nums[l]) right++
                    ans += left * right
                }
            }
        }
        return ans
    }
}

Python

class Solution:
    def countQuadruplets(self, nums: list[int]) -> int:
        n, ans = len(nums), 0
        for k in range(1, n-2):
            for j in range(0, k):
                if nums[j] < nums[k]:
                    left = sum(1 for i in range(j) if nums[i] < nums[k])
                    right = sum(1 for l in range(k+1, n) if nums[j] < nums[l])
                    ans += left * right
        return ans

Rust

impl Solution {
    pub fn count_quadruplets(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for k in 1..n-2 {
            for j in 0..k {
                if nums[j] < nums[k] {
                    let left = (0..j).filter(|&i| nums[i] < nums[k]).count();
                    let right = (k+1..n).filter(|&l| nums[j] < nums[l]).count();
                    ans += left * right;
                }
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    countQuadruplets(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        for (let k = 1; k < n-2; k++) {
            for (let j = 0; j < k; j++) {
                if (nums[j] < nums[k]) {
                    let left = 0, right = 0;
                    for (let i = 0; i < j; i++) if (nums[i] < nums[k]) left++;
                    for (let l = k+1; l < n; l++) if (nums[j] < nums[l]) right++;
                    ans += left * right;
                }
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^3), as we enumerate all (i, j, k, l) in a nested way.
• 🧺 Space complexity: O(1), only a constant amount of space is used.