Skip to content

2552. Count Increasing Quadruplets 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  long long countQuadruplets(vector<int>& nums) {
    long 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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