2552. Count Increasing Quadruplets

Description

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

 

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.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const countQuadruplets = function (nums) {
  const n = nums.length;
  const dp = Array.from({ length: n }, () => 0);
  let result = 0;

  for (let k = 2; k < n; k++) {
    let lessThanK = 0;

    for (let j = 0; j < k; j++) {
      if (nums[j] < nums[k]) {
        lessThanK += 1;
        result += dp[j];
      } else {
        dp[j] += lessThanK;
      }
    }
  }

  return result;
};