Count Special Quadruplets — Solution in Python, Java & C++
Count Special Quadruplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Special Quadruplets is an easy coding problem on arrays, hash table and enumeration, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the number of index quadruplets (a, b, c, d) with a < b < c < d such that nums[a] + nums[b] + nums[c] == nums[d].
Quadruplets are counted by their indices, so equal values at different positions count separately.
Example 1
Input: nums = [2,3,5,10]
Output: 1
Explanation: 2 + 3 + 5 == 10.
Example 2
Input: nums = [5,5,5,5]
Output: 0
Example 3
Input: nums = [2,2,2,6,10]
Output: 4
Explanation: (0,1,2,3) gives 6, and (0,1,3,4), (0,2,3,4), (1,2,3,4) each give 2 + 2 + 6 == 10.
Constraints
4 <= nums.length <= 501 <= nums[i] <= 100
Hints for Count Special Quadruplets
Hint 1
With
n <= 50four nested loops already pass, but you can do much better.Hint 2
Rewrite the equation as
nums[a] + nums[b] == nums[d] - nums[c].Hint 3
Fix
band move it from right to left; keep a count of every differencenums[d] - nums[c]withb < c < d, and look upnums[a] + nums[b]for eacha < b.
How to solve Count Special Quadruplets
Split the equation into a left pair and a right pair: nums[a] + nums[b] == nums[d] - nums[c]. With b as the pivot, all right pairs have c > b, so they can be counted incrementally as b moves left.
Approach
- Keep
cnt[v], the number of pairsc < dwithc > bandnums[d] - nums[c] == v(only positivevcan ever match). - For
bfromn - 3down to 1: first add the pairs that usec = b + 1— everyd > b + 1contributesnums[d] - nums[b + 1]. - Then, for every
a < b, addcnt[nums[a] + nums[b]]to the answer. - Return the answer.
Why it works
When b is processed, cnt holds exactly the pairs (c, d) with b < c < d: the pairs with c = b + 1 were just added, and those with larger c were added in earlier iterations. Each valid quadruplet is counted once — at its own b, for its own a, through its own (c, d) pair.
Complexity
- Time —
O(n^2) - Space —
O(V) with V = 200
Pitfalls
- Differences can be negative; since
nums[a] + nums[b] >= 2, only positive differences need storing. - Add the new
c = b + 1pairs before counting for thisb, not after. - Count index quadruplets, not distinct value combinations.
Reference solution
Python
from typing import List
def countQuadruplets(nums: List[int]) -> int:
n = len(nums)
cnt = [0] * 201
ans = 0
for b in range(n - 3, 0, -1):
c = b + 1
for d in range(c + 1, n):
diff = nums[d] - nums[c]
if diff > 0:
cnt[diff] += 1
for a in range(b):
ans += cnt[nums[a] + nums[b]]
return ansJava
public static int countQuadruplets(int[] nums) {
int n = nums.length, ans = 0;
int[] cnt = new int[201];
for (int b = n - 3; b >= 1; b--) {
int c = b + 1;
for (int d = c + 1; d < n; d++) {
int diff = nums[d] - nums[c];
if (diff > 0) cnt[diff]++;
}
for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b]];
}
return ans;
}C++
int countQuadruplets(vector<int>& nums) {
int n = nums.size(), ans = 0;
vector<int> cnt(201, 0);
for (int b = n - 3; b >= 1; b--) {
int c = b + 1;
for (int d = c + 1; d < n; d++) {
int diff = nums[d] - nums[c];
if (diff > 0) cnt[diff]++;
}
for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b]];
}
return ans;
}JavaScript
var countQuadruplets = function(nums) {
var n = nums.length, ans = 0;
var cnt = new Array(201).fill(0);
for (var b = n - 3; b >= 1; b--) {
var c = b + 1;
for (var d = c + 1; d < n; d++) {
var diff = nums[d] - nums[c];
if (diff > 0) cnt[diff]++;
}
for (var a = 0; a < b; a++) ans += cnt[nums[a] + nums[b]];
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets