Facebook Pixel

2552. Count Increasing Quadruplets

HardBinary Indexed TreeArrayDynamic ProgrammingEnumerationPrefix Sum
Leetcode Link

Problem Description

You are given a 0-indexed integer array nums of size n that contains all numbers from 1 to n. Your task is to count the number of increasing quadruplets in this array.

A quadruplet (i, j, k, l) is considered "increasing" if it satisfies both of these conditions:

  • The indices follow the order: 0 <= i < j < k < l < n
  • The values at these indices follow the specific pattern: nums[i] < nums[k] < nums[j] < nums[l]

Note that this is not a standard increasing sequence. The pattern requires that:

  1. The value at index i is less than the value at index k
  2. The value at index k is less than the value at index j
  3. The value at index j is less than the value at index l

This creates a "132-4" pattern where indices j and k are swapped in the value comparison compared to their positional order.

The solution uses dynamic programming with preprocessing. It fixes the middle two indices j and k, then:

  • Uses array f[j][k] to store how many indices l > k have nums[l] > nums[j]
  • Uses array g[j][k] to store how many indices i < j have nums[i] < nums[k]

The total count of valid quadruplets is the sum of f[j][k] * g[j][k] for all valid pairs of j and k.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing that directly checking all possible quadruplets would require O(n^4) time, which is inefficient. Instead, we can observe that the pattern nums[i] < nums[k] < nums[j] < nums[l] has an interesting structure where the middle two elements j and k are "inverted" in their value relationship compared to their index positions.

This suggests we should fix the middle two indices j and k as our pivot points. Once we fix these two positions where j < k but nums[j] > nums[k], we need to:

  1. Find all valid i values to the left of j where nums[i] < nums[k]
  2. Find all valid l values to the right of k where nums[l] > nums[j]

The number of valid quadruplets for a fixed (j, k) pair equals the product of valid i choices and valid l choices, since each i can be paired with each l independently.

The challenge is computing these counts efficiently. We notice that:

  • When iterating through different k values for a fixed j, we can maintain a running count of how many elements to the right of k are greater than nums[j]
  • Similarly, when iterating through different j values for a fixed k, we can maintain a running count of how many elements to the left of j are less than nums[k]

This leads to the preprocessing approach where we build two 2D arrays:

  • f[j][k]: counts elements after position k that are greater than nums[j]
  • g[j][k]: counts elements before position j that are less than nums[k]

By precomputing these values, we reduce the problem to O(n^2) time complexity, making it much more efficient than the naive approach.

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Implementation

1class Solution:
2    def countQuadruplets(self, nums: List[int]) -> int:
3        n = len(nums)
4      
5        # f[j][k] stores count of elements > nums[j] that come after k
6        # where j < k and nums[j] > nums[k]
7        greater_after = [[0] * n for _ in range(n)]
8      
9        # g[j][k] stores count of elements < nums[k] that come before j
10        # where j < k and nums[j] > nums[k]
11        less_before = [[0] * n for _ in range(n)]
12      
13        # Build greater_after matrix
14        # For each j, count elements greater than nums[j] that appear after position k
15        for j in range(1, n - 2):
16            # Initially count all elements after j that are greater than nums[j]
17            count = sum(nums[l] > nums[j] for l in range(j + 1, n))
18          
19            for k in range(j + 1, n - 1):
20                if nums[j] > nums[k]:
21                    # If nums[j] > nums[k], store the count
22                    greater_after[j][k] = count
23                else:
24                    # If nums[j] <= nums[k], nums[k] was counted but shouldn't be
25                    # Decrement count as we move forward
26                    count -= 1
27      
28        # Build less_before matrix
29        # For each k, count elements less than nums[k] that appear before position j
30        for k in range(2, n - 1):
31            # Initially count all elements before k that are less than nums[k]
32            count = sum(nums[i] < nums[k] for i in range(k))
33          
34            for j in range(k - 1, 0, -1):
35                if nums[j] > nums[k]:
36                    # If nums[j] > nums[k], store the count
37                    less_before[j][k] = count
38                else:
39                    # If nums[j] <= nums[k], nums[j] was counted but shouldn't be
40                    # Decrement count as we move backward
41                    count -= 1
42      
43        # Calculate total quadruplets
44        # For each valid (j, k) pair where nums[j] > nums[k]:
45        # - greater_after[j][k] gives count of valid l positions
46        # - less_before[j][k] gives count of valid i positions
47        # Multiply them to get all valid (i, j, k, l) quadruplets
48        total = sum(
49            greater_after[j][k] * less_before[j][k] 
50            for j in range(1, n - 2) 
51            for k in range(j + 1, n - 1)
52        )
53      
54        return total
55
1class Solution {
2    public long countQuadruplets(int[] nums) {
3        int n = nums.length;
4      
5        // countGreaterOnRight[j][k]: For indices j < k, stores count of elements > nums[j] that appear after k
6        int[][] countGreaterOnRight = new int[n][n];
7      
8        // countLessOnLeft[j][k]: For indices j < k, stores count of elements < nums[k] that appear before j
9        int[][] countLessOnLeft = new int[n][n];
10      
11        // Precompute countGreaterOnRight array
12        // For each j, we count how many elements after each k are greater than nums[j]
13        for (int j = 1; j < n - 2; j++) {
14            // Initially count all elements after j that are greater than nums[j]
15            int greaterCount = 0;
16            for (int idx = j + 1; idx < n; idx++) {
17                if (nums[idx] > nums[j]) {
18                    greaterCount++;
19                }
20            }
21          
22            // For each k after j, store the count if nums[j] > nums[k] (valid j-k pair)
23            for (int k = j + 1; k < n - 1; k++) {
24                if (nums[j] > nums[k]) {
25                    // nums[j] > nums[k], so this is a valid (j, k) pair
26                    countGreaterOnRight[j][k] = greaterCount;
27                } else {
28                    // nums[k] >= nums[j], so we need to exclude nums[k] from our count
29                    greaterCount--;
30                }
31            }
32        }
33      
34        long result = 0;
35      
36        // Compute countLessOnLeft and accumulate the result
37        for (int k = 2; k < n - 1; k++) {
38            // Count all elements before k that are less than nums[k]
39            int lessCount = 0;
40            for (int idx = 0; idx < k; idx++) {
41                if (nums[idx] < nums[k]) {
42                    lessCount++;
43                }
44            }
45          
46            // For each j before k (going backwards), compute valid quadruplets
47            for (int j = k - 1; j > 0; j--) {
48                if (nums[j] > nums[k]) {
49                    // nums[j] > nums[k], so this is a valid (j, k) pair
50                    countLessOnLeft[j][k] = lessCount;
51                  
52                    // Count valid quadruplets: 
53                    // countLessOnLeft[j][k] gives us valid i's (where i < j and nums[i] < nums[k])
54                    // countGreaterOnRight[j][k] gives us valid l's (where k < l and nums[j] < nums[l])
55                    result += (long) countGreaterOnRight[j][k] * countLessOnLeft[j][k];
56                } else {
57                    // nums[j] <= nums[k], so we need to exclude nums[j] from our count
58                    lessCount--;
59                }
60            }
61        }
62      
63        return result;
64    }
65}
66
1const int MAX_SIZE = 4001;
2int countGreaterAfterJ[MAX_SIZE][MAX_SIZE];  // f[j][k]: count of elements > nums[j] after position k
3int countLessBeforeK[MAX_SIZE][MAX_SIZE];    // g[j][k]: count of elements < nums[k] before position j
4
5class Solution {
6public:
7    long long countQuadruplets(vector<int>& nums) {
8        int n = nums.size();
9      
10        // Initialize arrays to zero
11        memset(countGreaterAfterJ, 0, sizeof countGreaterAfterJ);
12        memset(countLessBeforeK, 0, sizeof countLessBeforeK);
13      
14        // Precompute for each valid j position:
15        // For each k > j where nums[j] > nums[k], count how many l > k satisfy nums[l] > nums[j]
16        for (int j = 1; j < n - 2; ++j) {
17            // Count all elements after j that are greater than nums[j]
18            int greaterCount = 0;
19            for (int l = j + 1; l < n; ++l) {
20                if (nums[l] > nums[j]) {
21                    ++greaterCount;
22                }
23            }
24          
25            // For each k position after j
26            for (int k = j + 1; k < n - 1; ++k) {
27                if (nums[j] > nums[k]) {
28                    // Store count of valid l positions (where nums[l] > nums[j] and l > k)
29                    countGreaterAfterJ[j][k] = greaterCount;
30                } else {
31                    // If nums[k] >= nums[j], this k contributes to reducing available l positions
32                    --greaterCount;
33                }
34            }
35        }
36      
37        long long totalQuadruplets = 0;
38      
39        // For each k position, find valid (i, j) pairs and calculate contribution
40        for (int k = 2; k < n - 1; ++k) {
41            // Count all elements before k that are less than nums[k]
42            int lessCount = 0;
43            for (int i = 0; i < k; ++i) {
44                if (nums[i] < nums[k]) {
45                    ++lessCount;
46                }
47            }
48          
49            // For each j position before k (scanning backwards)
50            for (int j = k - 1; j > 0; --j) {
51                if (nums[j] > nums[k]) {
52                    // Store count of valid i positions (where nums[i] < nums[k] and i < j)
53                    countLessBeforeK[j][k] = lessCount;
54                  
55                    // Add contribution: number of valid i's × number of valid l's
56                    // This counts quadruplets (i, j, k, l) where:
57                    // i < j < k < l and nums[i] < nums[k] < nums[j] < nums[l]
58                    totalQuadruplets += 1LL * countGreaterAfterJ[j][k] * countLessBeforeK[j][k];
59                } else {
60                    // If nums[j] <= nums[k], this j contributes to reducing available i positions
61                    --lessCount;
62                }
63            }
64        }
65      
66        return totalQuadruplets;
67    }
68};
69
1const MAX_SIZE = 4001;
2// countGreaterAfterJ[j][k]: count of elements > nums[j] after position k
3const countGreaterAfterJ: number[][] = Array(MAX_SIZE).fill(0).map(() => Array(MAX_SIZE).fill(0));
4// countLessBeforeK[j][k]: count of elements < nums[k] before position j  
5const countLessBeforeK: number[][] = Array(MAX_SIZE).fill(0).map(() => Array(MAX_SIZE).fill(0));
6
7function countQuadruplets(nums: number[]): number {
8    const n = nums.length;
9  
10    // Reset arrays to zero
11    for (let i = 0; i < MAX_SIZE; i++) {
12        for (let j = 0; j < MAX_SIZE; j++) {
13            countGreaterAfterJ[i][j] = 0;
14            countLessBeforeK[i][j] = 0;
15        }
16    }
17  
18    // Precompute for each valid j position:
19    // For each k > j where nums[j] > nums[k], count how many l > k satisfy nums[l] > nums[j]
20    for (let j = 1; j < n - 2; j++) {
21        // Count all elements after j that are greater than nums[j]
22        let greaterCount = 0;
23        for (let l = j + 1; l < n; l++) {
24            if (nums[l] > nums[j]) {
25                greaterCount++;
26            }
27        }
28      
29        // For each k position after j
30        for (let k = j + 1; k < n - 1; k++) {
31            if (nums[j] > nums[k]) {
32                // Store count of valid l positions (where nums[l] > nums[j] and l > k)
33                countGreaterAfterJ[j][k] = greaterCount;
34            } else {
35                // If nums[k] >= nums[j], this k contributes to reducing available l positions
36                greaterCount--;
37            }
38        }
39    }
40  
41    let totalQuadruplets = 0;
42  
43    // For each k position, find valid (i, j) pairs and calculate contribution
44    for (let k = 2; k < n - 1; k++) {
45        // Count all elements before k that are less than nums[k]
46        let lessCount = 0;
47        for (let i = 0; i < k; i++) {
48            if (nums[i] < nums[k]) {
49                lessCount++;
50            }
51        }
52      
53        // For each j position before k (scanning backwards)
54        for (let j = k - 1; j > 0; j--) {
55            if (nums[j] > nums[k]) {
56                // Store count of valid i positions (where nums[i] < nums[k] and i < j)
57                countLessBeforeK[j][k] = lessCount;
58              
59                // Add contribution: number of valid i's × number of valid l's
60                // This counts quadruplets (i, j, k, l) where:
61                // i < j < k < l and nums[i] < nums[k] < nums[j] < nums[l]
62                totalQuadruplets += countGreaterAfterJ[j][k] * countLessBeforeK[j][k];
63            } else {
64                // If nums[j] <= nums[k], this j contributes to reducing available i positions
65                lessCount--;
66            }
67        }
68    }
69  
70    return totalQuadruplets;
71}
72

Solution Approach

The solution uses preprocessing with two 2D arrays to efficiently count the quadruplets. Let's walk through the implementation step by step:

Step 1: Initialize the arrays

  • Create two n × n arrays f and g initialized with zeros
  • f[j][k] will store the count of indices l > k where nums[l] > nums[j]
  • g[j][k] will store the count of indices i < j where nums[i] < nums[k]

Step 2: Build array f For each valid j position (from 1 to n-3):

  • First, count all elements after j that are greater than nums[j]: cnt = sum(nums[l] > nums[j] for l in range(j + 1, n))
  • Then iterate through each k position after j (from j+1 to n-2):
    • If nums[j] > nums[k] (the required condition), set f[j][k] = cnt
    • Otherwise, decrement cnt by 1 (since nums[k] itself was counted but doesn't satisfy the condition anymore as we move k forward)

The key optimization here is maintaining a running count. As k increases, if nums[k] >= nums[j], then nums[k] was previously counted in cnt but shouldn't be counted for positions after k, so we decrement it.

Step 3: Build array g For each valid k position (from 2 to n-2):

  • First, count all elements before k that are less than nums[k]: cnt = sum(nums[i] < nums[k] for i in range(k))
  • Then iterate through each j position before k in reverse (from k-1 down to 1):
    • If nums[j] > nums[k] (the required condition), set g[j][k] = cnt
    • Otherwise, decrement cnt by 1 (since nums[j] itself was counted but doesn't satisfy the condition as we move j backward)

Step 4: Calculate the final answer The total count of quadruplets is:

sum(f[j][k] * g[j][k] for j in range(1, n - 2) for k in range(j + 1, n - 1))

For each valid (j, k) pair where j < k and nums[j] > nums[k], multiply:

  • The number of valid l values (stored in f[j][k])
  • The number of valid i values (stored in g[j][k])

This gives us all possible quadruplets for that specific (j, k) pair.

Time Complexity: O(n²) for preprocessing both arrays and computing the final sum Space Complexity: O(n²) for storing the two 2D arrays

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a concrete example: nums = [4, 1, 3, 2, 5]

We need to find quadruplets (i, j, k, l) where i < j < k < l and nums[i] < nums[k] < nums[j] < nums[l].

Step 1: Initialize arrays

  • Create 5×5 arrays f and g (all zeros initially)

Step 2: Build array f[j][k] (counts of l > k where nums[l] > nums[j])

For j = 1 (nums[1] = 1):

  • Count elements after j=1 that are > 1: positions 2,3,4 have values 3,2,5, all > 1, so cnt = 3
  • For k = 2 (nums[2] = 3): Since nums[1]=1 NOT > nums[2]=3, skip and decrement cnt to 2
  • For k = 3 (nums[3] = 2): Since nums[1]=1 NOT > nums[3]=2, skip and decrement cnt to 1

For j = 2 (nums[2] = 3):

  • Count elements after j=2 that are > 3: only position 4 has value 5 > 3, so cnt = 1
  • For k = 3 (nums[3] = 2): Since nums[2]=3 > nums[3]=2 ✓, set f[2][3] = 1

Step 3: Build array g[j][k] (counts of i < j where nums[i] < nums[k])

For k = 2 (nums[2] = 3):

  • Count elements before k=2 that are < 3: positions 0,1 have values 4,1, only 1 < 3, so cnt = 1
  • For j = 1 (nums[1] = 1): Since nums[1]=1 NOT > nums[2]=3, skip and decrement cnt to 0

For k = 3 (nums[3] = 2):

  • Count elements before k=3 that are < 2: only position 1 has value 1 < 2, so cnt = 1
  • For j = 2 (nums[2] = 3): Since nums[2]=3 > nums[3]=2 ✓, set g[2][3] = 1
  • For j = 1 (nums[1] = 1): Since nums[1]=1 NOT > nums[3]=2, skip

Step 4: Calculate total quadruplets

Sum up f[j][k] * g[j][k] for all valid (j,k) pairs:

  • Only (j=2, k=3) has both f[2][3] = 1 and g[2][3] = 1
  • Result: 1 * 1 = 1

Verification: The quadruplet is (i=1, j=2, k=3, l=4) with values (1, 3, 2, 5).

  • Check: nums[1]=1 < nums[3]=2 < nums[2]=3 < nums[4]=5 ✓

The algorithm correctly finds 1 increasing quadruplet.

Time and Space Complexity

The time complexity is O(n²) and the space complexity is O(n²), where n is the length of the array.

Time Complexity Analysis:

  • The algorithm uses two main preprocessing loops:
    • First loop: For each j from 1 to n-2, we iterate through k from j+1 to n-1. The initial counting sum(nums[l] > nums[j] for l in range(j + 1, n)) takes O(n) time, but this is done once per j. The inner loop runs O(n) times with O(1) operations each. Total for this section: O(n²)
    • Second loop: For each k from 2 to n-1, we iterate through j from k-1 down to 1. Similar to the first loop, the initial counting takes O(n) time once per k, and the inner loop runs O(n) times with O(1) operations. Total for this section: O(n²)
  • The final summation iterates through all valid (j, k) pairs where j ranges from 1 to n-2 and k ranges from j+1 to n-1, which is O(n²) pairs with O(1) work per pair.
  • Overall time complexity: O(n²) + O(n²) + O(n²) = O(n²)

Space Complexity Analysis:

  • Two 2D arrays f and g are created, each of size n × n
  • Total space used: 2 × n² = O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Count Updates When Building the Arrays

A critical pitfall is misunderstanding when to decrement the count while building the f and g arrays. Many developers make the mistake of decrementing the count in the wrong condition.

Incorrect Implementation:

# WRONG: Decrementing when nums[j] > nums[k]
for k in range(j + 1, n - 1):
    if nums[j] > nums[k]:
        greater_after[j][k] = count
        count -= 1  # WRONG: Should not decrement here

Why it's wrong: When nums[j] > nums[k], we want to keep all elements greater than nums[j] in our count. We only decrement when nums[k] >= nums[j] because nums[k] itself was initially counted but won't be available for future k positions.

Correct Implementation:

for k in range(j + 1, n - 1):
    if nums[j] > nums[k]:
        greater_after[j][k] = count
    else:
        # Only decrement when nums[k] >= nums[j]
        count -= 1

2. Off-by-One Errors in Loop Boundaries

The loop boundaries are crucial for this problem. Common mistakes include:

Incorrect Loop Ranges:

# WRONG: Missing valid positions
for j in range(n - 2):  # Should start from 1, not 0
    count = sum(nums[l] > nums[j] for l in range(j + 1, n))
    for k in range(j + 1, n):  # Should end at n-1, not n

Correct Loop Ranges:

# j must be at least index 1 (need room for i before it)
# j must be at most n-3 (need room for k and l after it)
for j in range(1, n - 2):
    count = sum(nums[l] > nums[j] for l in range(j + 1, n))
    # k must be at most n-2 (need room for l after it)
    for k in range(j + 1, n - 1):

3. Confusing the Pattern Requirements

The pattern nums[i] < nums[k] < nums[j] < nums[l] is NOT a standard increasing sequence. It's easy to mistakenly check for nums[i] < nums[j] < nums[k] < nums[l].

Wrong Understanding:

# WRONG: Checking standard increasing order
if nums[i] < nums[j] and nums[j] < nums[k] and nums[k] < nums[l]:
    count += 1

Correct Understanding: The pattern specifically requires:

  • nums[i] < nums[k] (comparing positions i and k)
  • nums[k] < nums[j] (k value is less than j value, despite k > j in position)
  • nums[j] < nums[l] (comparing positions j and l)

4. Inefficient Initial Count Calculation

While the provided solution is correct, a common inefficiency is recalculating the initial count from scratch for every j or k value:

Less Efficient:

for j in range(1, n - 2):
    # Recalculating from scratch every time
    count = sum(nums[l] > nums[j] for l in range(j + 1, n))

More Efficient Alternative:

# Pre-compute suffix counts for all positions
suffix_greater = [0] * n
for j in range(n - 2, -1, -1):
    suffix_greater[j] = sum(1 for l in range(j + 1, n) if nums[l] > nums[j])

5. Memory Optimization Overlooked

The solution uses O(n²) space for two 2D arrays. For very large inputs, this might cause memory issues. Consider that many entries in the arrays remain zero (when nums[j] <= nums[k]).

Space-Optimized Alternative Using Dictionary:

greater_after = {}  # Use sparse representation
less_before = {}

# Only store non-zero values
if nums[j] > nums[k]:
    greater_after[(j, k)] = count
  
# Later when calculating result
total = sum(
    greater_after.get((j, k), 0) * less_before.get((j, k), 0)
    for j in range(1, n - 2)
    for k in range(j + 1, n - 1)
)

This optimization is particularly useful when the array has many positions where nums[j] <= nums[k], resulting in sparse matrices.

Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Prefix Sum

Prefix Sum Given an array of integers arr and a target value find a subarray that sums to the target Return the start and end indices of the subarray Input arr 1 20 3 30 5 4 target 7 Output 1 4 Explanation The subarray 20 3 30 from index 1 inclusive

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More