Count Increasing Quadruplets - Leetcode Solution

Problem Statement:

Given an array of integers nums, return the number of quadruplets (a, b, c, d) such that:

nums[a] < nums[b] < nums[c] < nums[d]

Example:

Input: nums = [1,2,3,4] Output: 1 Explanation: The only quadruplet that satisfies the condition is (0, 1, 2, 3)

Solution:

The given problem can be solved using nested loops in Time complexity of O(n^4). But such an approach is pretty inefficient as the input size of the array can be as large as 5000.

We can solve this using an optimized approach in O(n^2) time complexity.

The optimized solution involves using pre-processing to count all pairs and quadruplets that satisfy the condition. The main idea is to fix the two indices (i, j) in the array and then count the number of increasing pairs of elements that have indices greater than j. This can be done using a simple loop.

Algorithm:

1. Initialize a variable count to zero, which will count all the valid quadruplets.
2. For each pair of indices (i, j), where 0 ≤ i < j < n, count the number of increasing pairs of elements greater than j.
3. The count for this step can be achieved by using a variable k initialized to j+1 and checking if nums[i] < nums[j] < nums[k] and nums[k] < nums[l], where l > k.
4. If the condition is true we increment our count by (n-l).
5. Return the count of valid quadruplets.

Code:

class Solution { public: int countQuadruplets(vector<int>& nums) { int n = nums.size(); int count = 0; for (int i = 0; i < n-3; i++) { for (int j = i+1; j < n-2; j++) { int k = j + 1, l = n - 1; while (k < l) { if (nums[i] < nums[j] && nums[j] < nums[k] && nums[k] < nums[l]) { count += (n-l); k++; } else { l--; } } } } return count; } };

Time Complexity: O(n^2), Space Complexity: O(1)

Explanation:

In the above code, we maintain two loops to check each pair of indices and keep a count of the number of valid quadruplets. For each pair of indices, we set k to j+1, l to n-1, and start a while loop until k becomes greater than or equal to l.

We check the condition if nums[i] < nums[j] < nums[k] < nums[l], where k is the index of the third number in our quadruplet. If this condition is true, we add (n-l) to the count and increment k (count the number of valid quadruplets). If the condition is false, we decrement l. We continue to do this until k becomes greater than or equal to l.

Finally, we return the count of all valid quadruplets in the input array nums.

1