Count Increasing Quadruplets - Video Solutions

Problem Overview: Given an array nums, count the number of index quadruplets (i, j, k, l) such that i < j < k < l and nums[i] < nums[k] < nums[j] < nums[l]. The challenge is enforcing both index ordering and value ordering efficiently without checking every possible combination.

Approach 1: Brute Force with Early Pruning (O(n^4) time, O(1) space)

Enumerate all quadruplets using four nested loops over indices i, j, k, and l. For each combination, check the ordering constraint directly. Small optimizations prune cases early, such as skipping when nums[i] >= nums[k] or nums[j] >= nums[l]. The algorithm is straightforward but scales poorly because the search space grows as n^4. Useful mainly for understanding the problem or validating optimized solutions.

Approach 2: Nested Loop with Counting (O(n^3) time, O(1) space)

Fix two middle indices and reduce the remaining search to counting valid values. Iterate j and k, ensuring j < k. For each pair where nums[k] < nums[j], scan the left side for indices i where nums[i] < nums[k] and scan the right side for indices l where nums[l] > nums[j]. Multiply the counts to get the number of quadruplets using this (j,k) pair. This eliminates one loop but still requires scanning ranges repeatedly.

Approach 3: Improved Counting with Preprocessing (O(n^2) time, O(n^2) space)

Precompute helpful counts to avoid rescanning the array. For each index pair, track how many elements to the right are greater than a given value and how many to the left are smaller. When iterating over (j, k) pairs with j < k and nums[k] < nums[j], combine these precomputed values to determine how many valid i and l indices exist. This converts repeated scans into constant‑time lookups, reducing the overall complexity to O(n^2). The approach relies heavily on careful counting and is closely related to techniques used in dynamic programming and prefix sum style preprocessing.

Approach 4: Optimized Approach with Preprocessing / Fenwick Tree (O(n^2) time, O(n log n) updates)

A more scalable variant uses frequency structures such as a Fenwick Tree (Binary Indexed Tree). While iterating through the array, maintain counts of values already seen and values remaining. For each potential (j, k) pair, query the structure to count elements smaller than nums[k] on the left and larger than nums[j] on the right. Fenwick Trees support prefix queries and updates in O(log n), making the counting step efficient. This technique is common in advanced array counting problems and when using a Binary Indexed Tree.

Recommended for interviews: Start by describing the brute force enumeration to demonstrate understanding of the constraints. Interviewers usually expect the optimized counting approach with preprocessing or Fenwick Tree, which reduces the problem to O(n^2) time. The key insight is fixing the middle pair (j, k) and counting valid elements on both sides instead of explicitly enumerating all four indices.