1995. Count Special Quadruplets

Time: O(n²)

Space: O(n)

Approach

Two-loop with HashMap tracking nums[d]-nums[c] values; count matching a+b+c == d.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Hash Table

Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.

1995.cs

// Approach: Two-loop with HashMap tracking nums[d]-nums[c] values; count matching a+b+c == d.
// Time: O(n²) Space: O(n)

public class Solution
{
    public int CountQuadruplets(int[] nums)
    {
        int n = nums.Length;
        int ans = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();

        // nums[a] + nums[b] + nums[c] == nums[d]
        // => nums[a] + nums[b] == nums[d] - nums[c]
        for (int b = n - 1; b > 0; --b)
        { // `b` also represents `c`.
            for (int a = b - 1; a >= 0; --a)
                ans += count.TryGetValue(nums[a] + nums[b], out int value) ? value : 0;
            for (int d = n - 1; d > b; --d)
                if (count.ContainsKey(nums[d] - nums[b]))
                {
                    count[nums[d] - nums[b]]++;
                }
                else
                {
                    count[nums[d] - nums[b]] = 1;
                } // b := c
        }

        return ans;
    }
}

Was this solution helpful?