Count increasing quadruplets

Array Dynamic Programming Binary Indexed Tree Enumeration Prefix Sum

34.5% acceptance

Feb 25, 2026

401

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_quadruplets(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut ans = 0i64;
    // count_less[v] = # of indices seen so far (i < j) with nums[i] < v
    let mut count_less = vec![0i64; n + 2];
    for j in 0..n {
      // right_count[k] = # of l > k with nums[l] > nums[j]
      let mut right_count = vec![0i64; n];
      for k in (j + 1..n).rev() {
        right_count[k] = if k + 1 < n {
          right_count[k + 1] + if nums[k + 1] > nums[j] { 1 } else { 0 }
        } else {
          0
        };
      }
      // For each k > j where nums[k] < nums[j], count valid (i, j, k, l) quadruplets
      for k in j + 1..n {
        if nums[k] < nums[j] {
          ans += count_less[nums[k] as usize] * right_count[k];
        }
      }
      // Add nums[j] to count_less: increment count_less[v] for all v > nums[j]
      for v in (nums[j] as usize + 1)..=n {
        count_less[v] += 1;
      }
    }
    ans
  }
}