This problem was recently asked in Google SDE-3 Interview -

✅ Problem Statement
Given a sorted array a of size N, find the number of quadruplets (i, j, k, l) such that:

i < j < k < l

a[i] + a[j] > k1

a[k] + a[l] > k2

Video Solution -

Constraints:

Elements can be positive or negative

|a[i]|, |k1|, |k2| ≤ 10^8

🔍 Example

Input:
a = [1, 1, 1, 1, 2, 2]
k1 = 1
k2 = 3

Output:
6

Valid quadruplets:
(1,2,5,6), (2,3,5,6), (3,4,5,6), (1,4,5,6), (1,3,5,6), (2,4,5,6)
🚫 Brute Force Approach
Idea:
Try all possible quadruples (i, j, k, l).

Code:
Brute Force (C++)

Time: O(N^4)
Space: O(1)
✅ Step 1: Easy Subproblem – Count Pairs with Sum > K
Problem:
Given a sorted array a, count pairs (i, j) such that i < j and a[i] + a[j] > k.

Optimized Approach: Two Pointers
text
Copy
Edit

• i = 1, j = N
• if a[i] + a[j] > k → all (i, i+1, ..., j-1, j) with this j are valid
• Count += (j - i)
• Move j--, else i++
  🔗 Code (C++)
  ✅ Time: O(N)
  ✅ Space: O(1)

✅ Step 2: Main Problem (Quadruplets)
Idea:
Fix j and count valid (i, j) and (k, l) pairs:

text
Copy
Edit
for each j = 2 to N-2:
count all i < j such that a[i] + a[j] > k1
count all k > j such that a[k] + a[l] > k2 (use 2-pointers)

✅ Time: O(N^2)
✅ Space: O(1)

🚀 Step 3: Log Optimization – Binary Search
Idea:
For fixed j, count valid i < j such that a[i] > k1 - a[j] via binary search.

For (k, l), precompute valid pairs using a suffix array s[k] and suffix[k].

Time: O(N log N)
Space: O(N)
⚡ Final Optimization – Linear Time
Preprocess:
p[j]: count of all valid pairs (i, j) with i < j and a[i] + a[j] > k1 using two pointers

s[k]: count of valid (k, l) using 2-pointers in reverse

Use these in final pass to count all valid (i, j, k, l)

Time: O(N)
Space: O(N)
📌 Key Takeaways:
Start from brute force and break problem into smaller optimized subproblems

Two-pointers and binary search are super effective in sorted arrays

Smart precomputations (prefix/suffix arrays) can bring down time complexity