LeetCode 2552 - Count Increasing Quadruplets

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Binary Indexed Tree, Enumeration, Prefix Sum

Solution

Problem Understanding

The problem asks us to count the number of increasing quadruplets (i, j, k, l) in a 0-indexed array nums of size n, where nums is a permutation of the integers from 1 to n. A quadruplet is considered increasing if it satisfies both the index order 0 <= i < j < k < l < n and the value condition nums[i] < nums[k] < nums[j] < nums[l].

In other words, we are looking for four distinct indices such that the first element is smaller than the third, the third is smaller than the second, and the second is smaller than the fourth. The input is guaranteed to be a permutation, so each number appears exactly once, which eliminates repeated values as a concern. The output is simply an integer representing the count of quadruplets satisfying these conditions.

The constraints are important: the length of nums can be up to 4000, so a naive solution that examines all quadruplets directly (O(n^4)) will not be feasible. Edge cases to consider include small arrays of size 4, strictly increasing or decreasing arrays, and arrays where no quadruplet satisfies the condition.

Approaches

The brute-force approach is straightforward. We could use four nested loops over indices i, j, k, l and check if each quadruplet satisfies nums[i] < nums[k] < nums[j] < nums[l]. This method is guaranteed to be correct because it checks every possible quadruplet, but its complexity is O(n^4), which is too slow for n = 4000.

The key insight for a more efficient solution is to enumerate the middle pair (j, k) and count how many valid i and l exist for each. Instead of looping through all four indices, we can preprocess counts:

For each j, track how many i exist before j where nums[i] < nums[k].
For each k (with k > j), track how many l exist after k where nums[l] > nums[j].

This transforms the problem into a series of counts, reducing the complexity to O(n^2) by using prefix sums or binary indexed trees (Fenwick Trees) for fast counting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1)	Check all quadruplets directly; correct but too slow
Optimal	O(n^2)	O(n)	Enumerate `(j, k)` pairs and count valid `i` and `l` using prefix sums

Algorithm Walkthrough

Initialize a variable result to store the number of quadruplets.
Create an array prefix to store, for each position k, the number of elements to its left that are smaller than nums[k].
Iterate over k from index 1 to n-2. For each k, iterate j from k+1 to n-1. For each (j, k) pair:
Count the number of i indices before k where nums[i] < nums[k] using the prefix array.
Count the number of l indices after j where nums[l] > nums[j] using a similar suffix approach.
Multiply the counts of valid i and l and add to result.
Return result.

Why it works: By counting valid i and l for each middle pair (j, k), we consider all possible quadruplets that satisfy the value condition without iterating all combinations. The prefix/suffix counts ensure the index order and value conditions are respected.

Python Solution

from typing import List

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        
        for j in range(1, n - 2):
            for k in range(j + 1, n - 1):
                count_i = sum(1 for i in range(j) if nums[i] < nums[k])
                count_l = sum(1 for l in range(k + 1, n) if nums[l] > nums[j])
                result += count_i * count_l
                
        return result

The Python implementation iterates over all valid (j, k) pairs, counts i indices before k and l indices after j that satisfy the value constraints, and accumulates the result. This uses O(n^2) time and O(1) extra space.

Go Solution

func countQuadruplets(nums []int) int64 {
    n := len(nums)
    var result int64 = 0

    for j := 1; j < n-2; j++ {
        for k := j + 1; k < n-1; k++ {
            countI := 0
            for i := 0; i < j; i++ {
                if nums[i] < nums[k] {
                    countI++
                }
            }
            countL := 0
            for l := k + 1; l < n; l++ {
                if nums[l] > nums[j] {
                    countL++
                }
            }
            result += int64(countI * countL)
        }
    }

    return result
}

In Go, we handle large counts with int64 to avoid overflow. The logic mirrors the Python version, with nested loops for (j, k) and counting valid i and l.

Worked Examples

Example 1: nums = [1,3,2,4,5]

Iterate (j, k):

j = 1, k = 2: nums[k]=2
Valid i before j with nums[i] < nums[k]: [1] → 1
Valid l after k with nums[l] > nums[j]: [4,5] → 2
Add 1*2 = 2 to result
Other (j,k) pairs yield 0 valid quadruplets

Result = 2

Example 2: nums = [1,2,3,4]

Only one possible (j,k) pair (1,2): nums[k]=3
Valid i before j with nums[i] < nums[k]: [1] → 1
Valid l after k with nums[l] > nums[j]: [4] → 1
Check nums[i] < nums[k] < nums[j] < nums[l]: 1 < 3 < 2 < 4 fails
No valid quadruplets

Result = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Nested loops over `(j,k)` pairs, counting `i` and `l` each O(n) in worst case, simplified to O(n^2)
Space	O(1)	No extra data structures beyond counters

We avoid O(n^4) brute-force by only enumerating middle pairs (j,k) and counting valid endpoints efficiently.

Test Cases

# Provided examples
assert Solution().countQuadruplets([1,3,2,4,5]) == 2  # Example 1
assert Solution().countQuadruplets([1,2,3,4]) == 0     # Example 2

# Edge cases
assert Solution().countQuadruplets([4,3,2,1]) == 0     # strictly decreasing
assert Solution().countQuadruplets([1,2,3,5,4]) == 1  # single valid quadruplet
assert Solution().countQuadruplets([1,4,2,5,3]) == 2  # multiple scattered quadruplets

# Boundary values
assert Solution().countQuadruplets([1,2,3,4]) == 0     # smallest n=4 with no valid quadruplet
assert Solution().countQuadruplets([1,3,2,4]) == 1    # n=4 with 1 valid quadruplet

Test	Why
`[1,3,2,4,5]`	Valid quadruplets counted correctly
`[1,2,3,4]`	No quadruplets satisfy `nums[i] < nums[k] < nums[j] < nums[l]`
`[4,3,2,1]`	Descending array should yield 0
`[1,2,3,5,4]`	Single quadruplet scenario
`[1,4,2,5,3]`	Multiple quadruplets with scattered order

Edge Cases

Strictly decreasing array: This case could trip up naive implementations that assume any increasing subsequence exists. The correct handling ensures counts are zero, which our counting method naturally does.
Array of size exactly 4: Minimal array size is a boundary. There is only one possible quadruplet. The algorithm handles it correctly by the nested loop bounds.
**Large array with