LeetCode Solutions Blog

Count Increasing Quadruplets

Number: 2682

Difficulty: Hard

Paid? No

Problem Description

Given an array nums which is a permutation of the numbers from 1 to n, count the number of quadruplets (i, j, k, l) with 0 <= i < j < k < l < n satisfying: nums[i] < nums[k] < nums[j] < nums[l].

Key Insights

The quadruplet condition is not completely monotonic – notice that while indices are in increasing order, the value relationships are interleaved.
We can fix the middle pair (j, k) with j < k and, provided nums[k] < nums[j], the valid i choices come from indices less than j with nums[i] < nums[k] and the valid l choices come from indices greater than k with nums[l] > nums[j].
Counting valid i and l efficiently can be achieved using Binary Indexed Trees (Fenwick Trees) for prefix/suffix counting.
With BITs we can in O(log n) time query the number of elements in a range that satisfy a condition. Iterating over the middle two indices leads to an O(n² log n) solution.

Space and Time Complexity

Time Complexity: O(n² log n), where n is the length of nums. Space Complexity: O(n) for the BIT structures.

Solution

We reframe the problem by fixing indices j and k (with j < k) under the condition that nums[k] < nums[j]. For each such pair, we need: (1) the number of indices i (with i < j) for which nums[i] < nums[k], and (2) the number of indices l (with l > k) for which nums[l] > nums[j]. We pre-process and maintain these counts using two Binary Indexed Trees (BITs). • BIT1 is used for the prefix (indices < j) and is keyed by values (since nums are in 1..n). • BIT2 is used for the suffix (indices > j); for a fixed j, we initially add every index l (from j+1 to n–1) with nums[l] > nums[j] into BIT2. As we iterate k from j+1 onward, we remove the contribution of index k (if it was added) so that BIT2 can answer how many valid l exist with index greater than the current k. We then update our answer by multiplying the count obtained from BIT1 (for i’s) and BIT2 (for l’s) for every valid pair (j, k), and finally update BIT1 by adding nums[j] before moving to the next j.

Code Solutions

# Python solution with detailed comments

# Binary Indexed Tree implementation
class BIT:
    def __init__(self, size):
        # BIT is 1-indexed array of given size+1
        self.size = size
        self.tree = [0] * (size + 1)
        
    # add value 'delta' at index 'idx' (1-indexed)
    def update(self, idx, delta):
        while idx <= self.size:
            self.tree[idx] += delta
            idx += idx & -idx

    # query prefix sum up to and including idx (1-indexed)
    def query(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    # query range sum [l, r] (1-indexed)
    def query_range(self, l, r):
        return self.query(r) - self.query(l - 1)

def countQuadruplets(nums):
    n = len(nums)
    res = 0
    # BIT1: for counting valid indices i, keyed by value (values go from 1 to n)
    bit1 = BIT(n)
    
    # Loop j from 1 to n-3 (because we need room for at least one i before j and k,l after)
    for j in range(1, n - 2):
        # BIT2: for counting valid indices l, but we build it over indices with condition nums[l] > nums[j]
        # Here we use a BIT for indices, but we only need to count positions. 
        # We create an array of length n. BIT2 is a BIT keyed by index (1-indexed; map index l to l+1).
        bit2 = BIT(n)
        # For each possible l > j, if nums[l] > nums[j], add a count at position (l + 1) in BIT2.
        for l in range(j + 1, n):
            if nums[l] > nums[j]:
                bit2.update(l + 1, 1)
                
        # For k from j+1 to n-2 (we need at least one valid l after k)
        for k in range(j + 1, n - 1):
            # For current k, if the condition nums[k] < nums[j] holds, then:
            if nums[k] < nums[j]:
                # count valid i: among indices [0, j-1] with value less than nums[k]
                count_i = bit1.query(nums[k] - 1)
                # count valid l: among indices > k, stored in BIT2, query from k+2 to n.
                # Because BIT2 is 1-indexed and stores for index l as (l+1), we query indices greater than k+1
                count_l = bit2.query_range(k + 2, n)
                res += count_i * count_l
            # In BIT2, if current index k was counted (i.e. if nums[k] > nums[j]), remove it.
            if nums[k] > nums[j]:
                bit2.update(k + 1, -1)
        # After finishing with j, add nums[j]'s contribution in BIT1 for future i counts.
        bit1.update(nums[j], 1)
    return res

# Example test cases:
print(countQuadruplets([1,3,2,4,5]))  # Expected output: 2
print(countQuadruplets([1,2,3,4]))      # Expected output: 0