Count Special Quadruplets

Easy
1112.

Count Special Quadruplets

Count Special Quadruplets is an easy coding problem on arrays, hash table and enumeration, asked in Amazon and Google interviews.

Return the number of index quadruplets (a, b, c, d) with a < b < c < d such that nums[a] + nums[b] + nums[c] == nums[d].

Quadruplets are counted by their indices, so equal values at different positions count separately.

Example 1

Input
nums = [2,3,5,10]
Output
1
Explanation
2 + 3 + 5 == 10.

Example 2

Input
nums = [5,5,5,5]
Output
0

Example 3

Input
nums = [2,2,2,6,10]
Output
4
Explanation
(0,1,2,3) gives 6, and (0,1,3,4), (0,2,3,4), (1,2,3,4) each give 2 + 2 + 6 == 10.

Constraints

  • 4 <= nums.length <= 50
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countQuadruplets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Special Quadruplets — Solution in Python, Java & C++

Count Special Quadruplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Special Quadruplets is an easy coding problem on arrays, hash table and enumeration, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Enumeration
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the number of index quadruplets (a, b, c, d) with a < b < c < d such that nums[a] + nums[b] + nums[c] == nums[d].

Quadruplets are counted by their indices, so equal values at different positions count separately.

Example 1

Input: nums = [2,3,5,10]
Output: 1
Explanation: 2 + 3 + 5 == 10.

Example 2

Input: nums = [5,5,5,5]
Output: 0

Example 3

Input: nums = [2,2,2,6,10]
Output: 4
Explanation: (0,1,2,3) gives 6, and (0,1,3,4), (0,2,3,4), (1,2,3,4) each give 2 + 2 + 6 == 10.

Constraints

  • 4 <= nums.length <= 50
  • 1 <= nums[i] <= 100

Hints for Count Special Quadruplets

  1. Hint 1

    With n <= 50 four nested loops already pass, but you can do much better.

  2. Hint 2

    Rewrite the equation as nums[a] + nums[b] == nums[d] - nums[c].

  3. Hint 3

    Fix b and move it from right to left; keep a count of every difference nums[d] - nums[c] with b < c < d, and look up nums[a] + nums[b] for each a < b.

How to solve Count Special Quadruplets

Split the equation into a left pair and a right pair: nums[a] + nums[b] == nums[d] - nums[c]. With b as the pivot, all right pairs have c > b, so they can be counted incrementally as b moves left.

Approach

  1. Keep cnt[v], the number of pairs c < d with c > b and nums[d] - nums[c] == v (only positive v can ever match).
  2. For b from n - 3 down to 1: first add the pairs that use c = b + 1 — every d > b + 1 contributes nums[d] - nums[b + 1].
  3. Then, for every a < b, add cnt[nums[a] + nums[b]] to the answer.
  4. Return the answer.

Why it works

When b is processed, cnt holds exactly the pairs (c, d) with b < c < d: the pairs with c = b + 1 were just added, and those with larger c were added in earlier iterations. Each valid quadruplet is counted once — at its own b, for its own a, through its own (c, d) pair.

Complexity

  • Time — O(n^2)
  • Space — O(V) with V = 200

Pitfalls

  • Differences can be negative; since nums[a] + nums[b] >= 2, only positive differences need storing.
  • Add the new c = b + 1 pairs before counting for this b, not after.
  • Count index quadruplets, not distinct value combinations.

Reference solution

Python

from typing import List

def countQuadruplets(nums: List[int]) -> int:
    n = len(nums)
    cnt = [0] * 201
    ans = 0
    for b in range(n - 3, 0, -1):
        c = b + 1
        for d in range(c + 1, n):
            diff = nums[d] - nums[c]
            if diff > 0:
                cnt[diff] += 1
        for a in range(b):
            ans += cnt[nums[a] + nums[b]]
    return ans

Java

public static int countQuadruplets(int[] nums) {
    int n = nums.length, ans = 0;
    int[] cnt = new int[201];
    for (int b = n - 3; b >= 1; b--) {
        int c = b + 1;
        for (int d = c + 1; d < n; d++) {
            int diff = nums[d] - nums[c];
            if (diff > 0) cnt[diff]++;
        }
        for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b]];
    }
    return ans;
}

C++

int countQuadruplets(vector<int>& nums) {
    int n = nums.size(), ans = 0;
    vector<int> cnt(201, 0);
    for (int b = n - 3; b >= 1; b--) {
        int c = b + 1;
        for (int d = c + 1; d < n; d++) {
            int diff = nums[d] - nums[c];
            if (diff > 0) cnt[diff]++;
        }
        for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b]];
    }
    return ans;
}

JavaScript

var countQuadruplets = function(nums) {
    var n = nums.length, ans = 0;
    var cnt = new Array(201).fill(0);
    for (var b = n - 3; b >= 1; b--) {
        var c = b + 1;
        for (var d = c + 1; d < n; d++) {
            var diff = nums[d] - nums[c];
            if (diff > 0) cnt[diff]++;
        }
        for (var a = 0; a < b; a++) ans += cnt[nums[a] + nums[b]];
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets