2552. Count Increasing Quadruplets LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2552. Count Increasing Quadruplets LeetCode Solution with the best time and space complexity. The solution to Count Increasing Quadruplets problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Increasing Quadruplets solution in C++
Count Increasing Quadruplets solution in Java
Count Increasing Quadruplets solution in Python
Additional Resources

2552. Count Increasing Quadruplets LeetCode Solution image

Problem Statement of Count Increasing Quadruplets

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2552. Count Increasing Quadruplets LeetCode Solution in C++

class Solution {
 public:
  long long countQuadruplets(vector<int>& nums) {
    long ans = 0;
    // dp[j] := the number of triplets (i, j, k) where i < j < k and nums[i] <
    // nums[k] < nums[j]. Keep this information for l to use later.
    vector<int> dp(nums.size());

    // k can be treated as l.
    for (int k = 2; k < nums.size(); ++k)
      // j can be treated as i.
      for (int j = 0, numLessThanK = 0; j < k; ++j)
        if (nums[j] < nums[k]) {
          ++numLessThanK;  // nums[i] < nums[k]
          // nums[j] < nums[l], so we should add dp[j] since we find a new
          // quadruplets for (i, j, k, l).
          ans += dp[j];

        } else if (nums[j] > nums[k]) {
          dp[j] += numLessThanK;
        }

    return ans;
  }
};
/* code provided by PROGIEZ */

2552. Count Increasing Quadruplets LeetCode Solution in Java

class Solution {
  public long countQuadruplets(int[] nums) {
    long ans = 0;
    // dp[j] := the number of triplets (i, j, k) where i < j < k and nums[i] < nums[k] <
    // nums[j]. Keep this information for l to use later.
    int[] dp = new int[nums.size()];

    // k can be treated as l.
    for (int k = 2; k < nums.length; ++k)
      // j can be treated as i.
      for (int j = 0, numLessThanK = 0; j < k; ++j)
        if (nums[j] < nums[k]) {
          ++numLessThanK; // nums[i] < nums[k]
          // nums[j] < nums[l], so we should add dp[j] since we find a new
          // quadruplets for (i, j, k, l).
          ans += dp[j];
        } else if (nums[j] > nums[k]) {
          dp[j] += numLessThanK;
        }

    return ans;
  }
}
// code provided by PROGIEZ

2552. Count Increasing Quadruplets LeetCode Solution in Python

class Solution:
  def countQuadruplets(self, nums: list[int]) -> int:
    ans = 0
    # dp[j] := the number of triplets (i, j, k) where i < j < k and nums[i] < nums[k] <
    # nums[j]. Keep this information for l to use later.
    dp = [0] * len(nums)

    # k can be treated as l.
    for k in range(2, len(nums)):
      numLessThanK = 0
      # j can be treated as i.
      for j in range(k):
        if nums[j] < nums[k]:
          numLessThanK += 1  # nums[i] < nums[k]
          # nums[j] < nums[l], so we should add dp[j] since we find a new
          # quadruplets for (i, j, k, l).
          ans += dp[j]
        elif nums[j] > nums[k]:
          dp[j] += numLessThanK

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents