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.
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 ; } }Video 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.