Count Special Quadruplets
EasyPrompt
Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:
nums[a] + nums[b] + nums[c] == nums[d], anda < b < c < d
Example 1:
Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.Example 2:
Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].Example 3:
Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5
Constraints:
4 <= nums.length <= 501 <= nums[i] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward way to solve this problem is to check every possible quadruplet of indices (a, b, c, d). We can use four nested loops to generate all combinations of four distinct indices that satisfy the condition a < b < c < d. For each valid combination of indices, we then check if the sum of the values at the first three indices equals the value at the fourth index. If it does, we increment a counter.
Algorithm
- Initialize a counter
countto 0. - Get the length of the array,
n. - Use four nested loops to iterate through all possible combinations of indices
a,b,c, anddsuch that0 <= a < b < c < d < n.- The outer loop for
aruns from0ton-4. - The second loop for
bruns froma+1ton-3. - The third loop for
cruns fromb+1ton-2. - The innermost loop for
druns fromc+1ton-1.
- The outer loop for
- Inside the innermost loop, check if the condition
nums[a] + nums[b] + nums[c] == nums[d]is met. - If the condition is true, increment the
count. - After all loops complete, return the final
count.
Walkthrough
This approach directly translates the problem statement into code. We systematically generate every unique quadruplet of indices (a, b, c, d) ensuring they are in increasing order. The four nested loops handle this generation. The first loop picks index a, the second picks b greater than a, the third picks c greater than b, and the fourth picks d greater than c. For each such quadruplet, we perform the sum check nums[a] + nums[b] + nums[c] == nums[d]. If they are equal, we've found a special quadruplet and increment our result counter.
class Solution { public int countQuadruplets(int[] nums) { int n = nums.length; int count = 0; for (int a = 0; a < n; a++) { for (int b = a + 1; b < n; b++) { for (int c = b + 1; c < n; c++) { for (int d = c + 1; d < n; d++) { if (nums[a] + nums[b] + nums[c] == nums[d]) { count++; } } } } } return count; }}Complexity
Time
O(n^4) - There are four nested loops, each iterating up to `n` times. This results in a quartic time complexity. Given `n <= 50`, `50^4 = 6,250,000`, which is acceptable.
Space
O(1) - We only use a few variables to store the loop indices and the count, so the space required is constant.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient due to its O(n^4) time complexity.
Will likely result in a 'Time Limit Exceeded' error for larger constraints, although it passes for this problem given
n <= 50.
We can improve upon the brute-force approach by reducing the time complexity from O(n^4) to O(n^3). The key is to avoid the innermost loop that searches for d. Instead of a linear search, we can use a frequency map to check for the existence of nums[d] in O(1) time. By iterating through the indices a, b, and c, we calculate the target sum S = nums[a] + nums[b] + nums[c]. Then, we check how many times the value S appears in the array at an index d greater than c.
Algorithm
- The core idea is to rearrange the equation to
nums[d] = nums[a] + nums[b] + nums[c]and optimize the search ford. - We can iterate through the third index,
c, fromn-2down to2. - For each
c, we need to find pairs(a, b)witha < b < cand an indexdwithd > cthat satisfy the equation. - To do this efficiently, we maintain a frequency map (an array, since
nums[i]values are small) that stores the counts ofnums[d]for alld > c. - The algorithm proceeds as follows:
- Initialize
count = 0. - Initialize a frequency array
freqof size 101 (since1 <= nums[i] <= 100) to all zeros. - Loop
cfromn-2down to2.- In each iteration, first update the
freqarray by incrementing the count fornums[c+1]. This ensuresfreqalways stores the frequencies of elements with indices greater than the currentc. - Then, use two nested loops to iterate through all pairs
(a, b)such thata < b < c. - For each pair, calculate
sum = nums[a] + nums[b] + nums[c]. - If
sumis within the valid range (i.e.,<= 100), addfreq[sum]to the totalcount. Thisfreq[sum]represents the number of validd's we found for the current triplet(a, b, c).
- In each iteration, first update the
- Initialize
- After the loops complete, return
count.
Walkthrough
To implement this efficiently, we can iterate the index c backwards from n-2 down to 2. We maintain a frequency map (an array freq is sufficient due to the small range of nums[i]) that, for a given c, stores the frequency of each number nums[k] for all k > c.
As we decrement c in our main loop, we can update this frequency map incrementally. For example, when moving from c to c-1, the element nums[c] now becomes a potential nums[d] for future triplets, so we add it to our frequency map.
For each fixed c, we iterate through all possible pairs of a and b (where a < b < c). We calculate their sum with nums[c] and look up this sum in our frequency map. The value from the map tells us how many valid d's exist for this specific triplet (a, b, c), which we add to our total count.
class Solution { public int countQuadruplets(int[] nums) { int n = nums.length; int count = 0; // freq[v] will store the count of v in nums[k] where k > c int[] freq = new int[101]; // Max value of nums[i] is 100 // Let the indices be a < b < c < d // We will iterate c from n-2 down to 2 for (int c = n - 2; c >= 2; c--) { // For the current c, we update the frequency map to include the element // at index c+1, which can now act as a 'd' for smaller 'c's. freq[nums[c + 1]]++; // Now, for this fixed c, find pairs (a, b) where a < b < c for (int a = 0; a < c; a++) { for (int b = a + 1; b < c; b++) { int sum = nums[a] + nums[b] + nums[c]; if (sum <= 100) { // freq[sum] gives the number of d's such that d > c and nums[d] == sum count += freq[sum]; } } } } return count; }}Complexity
Time
O(n^3) - We have three nested loops. The outer loop for `c` runs about `n` times. The two inner loops for `a` and `b` together run O(c^2) times, which is O(n^2) in the worst case. This gives a total time complexity of O(n^3).
Space
O(M) - Where `M` is the maximum possible value of `nums[i]`. Since the constraints state `nums[i] <= 100`, the space complexity is O(101), which is constant.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Passes well within time limits for the given constraints.
Uses constant extra space due to the small range of values in
nums.
Cons
The logic is more complex than the brute-force approach.
Solutions
Solution
class Solution { public int countQuadruplets ( int [] nums ) { int ans = 0 , n = nums . length ; for ( int a = 0 ; a < n - 3 ; ++ a ) { for ( int b = a + 1 ; b < n - 2 ; ++ b ) { for ( int c = b + 1 ; c < n - 1 ; ++ c ) { for ( int d = c + 1 ; d < n ; ++ d ) { if ( nums [ a ] + nums [ b ] + nums [ c ] == nums [ d ]) { ++ ans ; } } } } } return ans ; } }class Solution {public: int countQuadruplets(vector<int> &nums) { int ans = 0, n = nums.size(); for (int a = 0; a < n - 3; ++a) for (int b = a + 1; b < n - 2; ++b) for (int c = b + 1; c < n - 1; ++c) for (int d = c + 1; d < n; ++d) if (nums[a] + nums[b] + nums[c] == nums[d]) ++ans; return ans; }};class Solution: def countQuadruplets(self, nums: List[int]) -> int: ans, n = 0, len(nums) for a in range(n - 3): for b in range(a + 1, n - 2): for c in range(b + 1, n - 1): for d in range(c + 1, n): if nums[a] + nums[b] + nums[c] == nums[d]: ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.