Skip to content

2552. Count Increasing Quadruplets

Difficulty Topics

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.

Solution

count-increasing-quadruplets.py
class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        N = len(nums)
        left = [[0] * (N + 1)] # 0...i, < j
        right = [[0] * (N + 1)] # i+1...N, > j

        for i in range(1, N):
            curr = left[-1][:]

            for j in range(nums[i - 1] + 1, N + 1):
                curr[j] += 1

            left.append(curr)

        for i in range(N - 2, -1, -1):
            curr = right[-1][:]

            for j in range(nums[i + 1]):
                curr[j] += 1

            right.append(curr)

        right.reverse()

        res = 0

        for j in range(N):
            for k in range(j + 1, N):
                if nums[k] < nums[j]:
                    res += left[j][nums[k]] * right[k][nums[j]]

        return res