Count Special Quadruplets — LeetCode 1995 Python Solution

The problem

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], and a < b < c < d

This statement is abridged. Read the full problem on LeetCode.

Example

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.

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1995. Count Special Quadruplets is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems