Solution Explanation for LeetCode 1995: Count Special Quadruplets

This problem asks us to find the number of distinct quadruplets (a, b, c, d) in a given array nums such that nums[a] + nums[b] + nums[c] == nums[d] and a < b < c < d.

Approach 1: Brute Force

The most straightforward approach is to iterate through all possible quadruplets and check if they satisfy the condition. This is a brute force approach with four nested loops.

Time Complexity: O(n4), where n is the length of the input array. This is because we have four nested loops, each iterating up to n times in the worst case.

Space Complexity: O(1). We only use a constant amount of extra space.

Code (Python):

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 ans

The code in other languages (Java, C++, Go) follows the same logic, just with different syntax.

Approach 2: Optimized with Hash Table (Counter)

We can optimize the brute force approach by using a hash table (or a Counter in Python) to store the counts of possible values of nums[d]. Instead of checking every d in the innermost loop, we directly check the count of nums[a] + nums[b] + nums[c] in the hash table.

Time Complexity: O(n3). We have three nested loops, and the hash table lookups are O(1) on average.

Space Complexity: O(n) in the worst case, to store the counts in the hash table. The maximum value of nums[a] + nums[b] + nums[c] is bounded, so the space is effectively O(1).

Code (Python):

from collections import Counter
 
class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        counter = Counter()
        for c in range(n - 2, 1, -1):
            counter[nums[c + 1]] += 1
            for a in range(c - 1):
                for b in range(a + 1, c):
                    ans += counter[nums[a] + nums[b] + nums[c]]
        return ans

Approach 3: Further Optimization

This approach further refines the previous one by pre-calculating differences between nums[d] and nums[c], storing counts of these differences in a Counter.

Time Complexity: O(n2) - We have two nested loops and hash table lookups.

Space Complexity: O(n) in the worst case, although the space used is effectively O(1) as the range of values is limited.

Code (Python):

from collections import Counter
 
class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        counter = Counter()
        for b in range(n - 3, 0, -1):
            c = b + 1
            for d in range(c + 1, n):
                counter[nums[d] - nums[c]] += 1
            for a in range(b):
                ans += counter[nums[a] + nums[b]]
        return ans

The Java, C++, and Go implementations for approaches 2 and 3 follow similar logic, using arrays or hash maps to achieve the same time and space complexity improvements. The core idea remains the same: reduce the number of nested loops by leveraging hash tables to count frequencies efficiently. Approach 3 provides the best asymptotic time complexity.