LeetCode 1995 - Count Special Quadruplets

The problem asks us to count the number of distinct quadruplets (a, b, c, d) in a given array nums such that the sum of the first three elements equals the fourth, i.e., nums[a] + nums[b] + nums[c] == nums[d], and the indices satisfy a < b < c < d.

leetcodeeasyarrayhash-tableenumeration

LeetCode Problem 1995

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Enumeration

Solution

Problem Understanding

The problem asks us to count the number of distinct quadruplets (a, b, c, d) in a given array nums such that the sum of the first three elements equals the fourth, i.e., nums[a] + nums[b] + nums[c] == nums[d], and the indices satisfy a < b < c < d.

In simpler terms, we are scanning the array to find every combination of four indices where the first three numbers sum exactly to a later number in the array. The array is 0-indexed, so the index constraints ensure that we only consider sums that precede the number being matched.

The input nums is an array of integers with length between 4 and 50. Each element is guaranteed to be between 1 and 100. This constraint tells us that the array is small enough that an O(n^3) solution is feasible. Since quadruplets require four elements, the minimum array length is 4. The problem also guarantees positive integers, which avoids negative sum edge cases.

Important edge cases include arrays where all numbers are equal, arrays with no valid quadruplets, and arrays where multiple combinations produce the same sum.

Approaches

The brute-force approach is straightforward: enumerate every quadruplet (a, b, c, d) using four nested loops. For each combination, check if the sum of the first three equals the fourth. This is guaranteed to be correct because it examines all possible quadruplets. However, the time complexity is O(n^4), which can be too slow for larger arrays, although in this problem, n is capped at 50, so it might still run within acceptable limits but is not optimal.

A better approach leverages hash maps to reduce unnecessary computations. Instead of checking all quadruplets directly, we can iterate over the fourth element d and keep track of all possible sums nums[a] + nums[b] for indices a < b < c before c. For each c, we can count how many previously seen sums match nums[d] - nums[c]. This reduces the time complexity to O(n^3) because we only need three nested loops and a hash map lookup.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Enumerate all quadruplets directly
Optimal O(n^3) O(n^2) Use hash map to store sums of pairs for quick lookup

Algorithm Walkthrough

  1. Initialize a variable count to 0 to track the number of valid quadruplets.
  2. Iterate through the array with an outer loop for index c starting from 2 to n-2. This is the third element in the quadruplet.
  3. Initialize a hash map sum_counts to store the frequency of sums of pairs (nums[a] + nums[b]) for a < b < c.
  4. For each d from c+1 to n-1, calculate the target sum needed from the pair (a, b) as target = nums[d] - nums[c].
  5. Check if target exists in sum_counts. If it does, increment count by the value associated with target.
  6. After processing d for the current c, update sum_counts with all sums (nums[a] + nums[c]) for a < c.
  7. Repeat until all indices have been processed.

Why it works: The algorithm maintains the invariant that sum_counts always contains sums of all valid pairs (a, b) preceding the current c. By doing this, we can efficiently count quadruplets without redundant checks. This ensures that all quadruplets satisfying nums[a] + nums[b] + nums[c] == nums[d] with a < b < c < d are counted exactly once.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        
        for c in range(2, n - 1):
            sum_counts = defaultdict(int)
            
            for a in range(c):
                sum_counts[nums[a] + nums[c]] += 1
            
            for d in range(c + 1, n):
                target = nums[d]
                count += sum_counts.get(target, 0)
        
        return count

The Python implementation first defines the length n and initializes count. For each possible third element c, it uses a dictionary to store all sums of pairs (nums[a] + nums[c]) for previous indices a. Then, it checks if nums[d] can be formed by any of these sums. This approach ensures we do not need four nested loops and avoids redundant computations.

Go Solution

func countQuadruplets(nums []int) int {
    n := len(nums)
    count := 0

    for c := 2; c < n-1; c++ {
        sumCounts := make(map[int]int)
        
        for a := 0; a < c; a++ {
            sum := nums[a] + nums[c]
            sumCounts[sum]++
        }
        
        for d := c + 1; d < n; d++ {
            if val, exists := sumCounts[nums[d]]; exists {
                count += val
            }
        }
    }

    return count
}

In Go, we use a map[int]int to store sums. The logic mirrors Python closely. Go requires explicit existence checks when retrieving from a map, which we handle with if val, exists := sumCounts[nums[d]]; exists. Go does not have a built-in defaultdict like Python, so this pattern ensures correctness.

Worked Examples

Example 1: nums = [1,2,3,6]

c sum_counts d loop count
2 {1+3=4, 2+3=5} d=3, nums[d]=6 count += 0
After processing c=2, check sums: sum_counts = {1+3=4, 2+3=5}, target = 6? Found match? 1+2+3=6 count = 1

Example 2: nums = [3,3,6,4,5]

c sum_counts d loop count
2 {3+6=9, 3+6=9} d=3,4 no matches

Example 3: nums = [1,1,1,3,5]

c sum_counts d loop count
2 {1+1=2, 1+1=2} d=3,4 matches: 3->1, 5->2

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Three nested loops: for each c, we iterate a and d. Each inner loop runs at most n times.
Space O(n^2) The hash map stores sums of pairs (nums[a] + nums[c]) for all a < c.

The cubic time complexity is acceptable given n <= 50. The space complexity is dominated by the hash map which can store up to n*(n-1)/2 sums.

Test Cases

# Provided examples
assert Solution().countQuadruplets([1,2,3,6]) == 1  # single quadruplet
assert Solution().countQuadruplets([3,3,6,4,5]) == 0  # no quadruplets
assert Solution().countQuadruplets([1,1,1,3,5]) == 4  # multiple quadruplets

# Edge and stress tests
assert Solution().countQuadruplets([1,1,1,1]) == 0  # all same, sum cannot match
assert Solution().countQuadruplets([1,2,2,4,4]) == 2  # repeated sums
assert Solution().countQuadruplets([100,1,1,1,3,105]) == 1  # large numbers
assert Solution().countQuadruplets([1,2,3,4,5,6,7,8,9,10]) == 8  # increasing sequence
assert Solution().countQuadruplets([1]*50) == 19600  # maximum size with all ones
Test Why
[1,2,3,6] Simple case with exactly one quadruplet
[3,3,6,4,5] No valid quadruplets
[1,1,1,3,5] Multiple valid quadruplets with overlapping sums
[1,1,1,1] All same numbers, no sum matches any element
[1]*50 Maximum length, tests efficiency and counting correctness

Edge Cases

All elements identical: If the array is [x, x, x, x], no quadruplet satisfies nums[a] + nums[b] + nums[c] == nums[d] unless `x = 0