1995. Count Special Quadruplets

Approach 1: $O(n^4)$

• Time: $O(n^4)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  int countQuadruplets(std::vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;

    for (int a = 0; a < n; ++a)
      for (int b = a + 1; b < n; ++b)
        for (int c = b + 1; c < n; ++c)
          for (int d = c + 1; d < n; ++d)
            if (nums[a] + nums[b] + nums[c] == nums[d])
              ++ans;

    return ans;
  }
};

class Solution {
  public int countQuadruplets(int[] nums) {
    final int n = nums.length;
    int ans = 0;

    for (int a = 0; a < n; ++a)
      for (int b = a + 1; b < n; ++b)
        for (int c = b + 1; c < n; ++c)
          for (int d = c + 1; d < n; ++d)
            if (nums[a] + nums[b] + nums[c] == nums[d])
              ++ans;

    return ans;
  }
}

class Solution:
  def countQuadruplets(self, nums: list[int]) -> int:
    n = len(nums)
    return sum(nums[a] + nums[b] + nums[c] == nums[d]
               for a in range(n)
               for b in range(a + 1, n)
               for c in range(b + 1, n)
               for d in range(c + 1, n))

Approach 2: $O(n^3)$

• Time: $O(n^3)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int countQuadruplets(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    unordered_map<int, int> count;

    for (int c = n - 1; c > 1; --c) {  // `c` also represents `d`.
      for (int b = c - 1; b > 0; --b)
        for (int a = b - 1; a >= 0; --a)
          if (const auto it = count.find(nums[a] + nums[b] + nums[c]);
              it != count.cend())
            ans += it->second;
      ++count[nums[c]];  // c := d
    }

    return ans;
  }
};

class Solution {
  public int countQuadruplets(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (int c = n - 1; c > 1; --c) { // `c` also represents `d`.
      for (int b = c - 1; b > 0; --b)
        for (int a = b - 1; a >= 0; --a)
          ans += count.getOrDefault(nums[a] + nums[b] + nums[c], 0);
      count.merge(nums[c], 1, Integer::sum); // c := d
    }

    return ans;
  }
}

class Solution:
  def countQuadruplets(self, nums: list[int]) -> int:
    n = len(nums)
    ans = 0
    count = collections.Counter()

    for c in range(n - 1, 1, -1):  # `c` also represents `d`.
      for b in range(c - 1, 0, -1):
        for a in range(b - 1, -1, -1):
          ans += count[nums[a] + nums[b] + nums[c]]
      count[nums[c]] += 1  # c := d

    return ans

Approach 3: $O(n^2)$

• Time: $O(n^2)$
• Space: $O(n^2)$

C++JavaPython

class Solution {
 public:
  int countQuadruplets(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    unordered_map<int, int> count;

    //    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)
        if (const auto it = count.find(nums[a] + nums[b]); it != count.cend())
          ans += it->second;
      for (int d = n - 1; d > b; --d)
        ++count[nums[d] - nums[b]];  // b := c
    }

    return ans;
  }
};

class Solution {
  public int countQuadruplets(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    //    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.getOrDefault(nums[a] + nums[b], 0);
      for (int d = n - 1; d > b; --d)
        count.merge(nums[d] - nums[b], 1, Integer::sum); // b := c
    }

    return ans;
  }
}

class Solution:
  def countQuadruplets(self, nums: list[int]) -> int:
    n = len(nums)
    ans = 0
    count = collections.Counter()

    #    nums[a] + nums[b] + nums[c] == nums[d]
    # => nums[a] + nums[b] == nums[d] - nums[c]
    for b in range(n - 1, 0, -1):  # `b` also represents `c`.
      for a in range(b - 1, -1, -1):
        ans += count[nums[a] + nums[b]]
      for d in range(n - 1, b, -1):
        count[nums[d] - nums[b]] += 1  # b := c

    return ans