Problem Description

You are given an integer array nums that is 0-indexed (meaning the first element is at index 0). Your task is to count how many distinct quadruplets of indices (a, b, c, d) exist in the array that satisfy both of the following conditions:

1. The sum of three elements equals the fourth element: nums[a] + nums[b] + nums[c] == nums[d]
2. The indices are in strictly increasing order: a < b < c < d

A quadruplet consists of four different positions in the array. You need to find all valid combinations where the values at the first three positions add up to equal the value at the fourth position, while maintaining the strict ordering of indices.

For example, if nums = [1, 2, 3, 6], then the quadruplet (0, 1, 2, 3) would be valid because:

• nums[0] + nums[1] + nums[2] = 1 + 2 + 3 = 6 = nums[3]
• The indices satisfy 0 < 1 < 2 < 3

The solution uses a brute force approach with four nested loops to check every possible combination of four indices. For each valid combination where the indices are in increasing order, it checks if the sum condition is met. If both conditions are satisfied, the counter is incremented. The time complexity is O(n^4) where n is the length of the array.

Intuition

When we need to find all valid quadruplets with specific conditions, the most straightforward approach is to examine every possible combination of four indices. Since we're looking for groups of four elements where three sum to equal the fourth, and the indices must be in strict ascending order, we can think of this as a selection problem.

The key insight is that with the constraint a < b < c < d, we're essentially choosing 4 positions from the array in order. This naturally leads to using nested loops where each inner loop starts from the position after the previous loop's current index. This ensures we never revisit the same combination and automatically maintains the ordering requirement.

For each combination of four indices, we simply check if nums[a] + nums[b] + nums[c] == nums[d]. The equation has a fixed structure - we always sum the first three values and compare to the fourth. This makes the checking condition straightforward.

While we could optimize this problem using techniques like hash maps to store sums or two-pointer approaches, the brute force method with four nested loops is the most intuitive starting point. It directly translates the problem requirements into code: pick four indices in order, check if they satisfy the sum condition, and count the valid ones.

The range limits in each loop (n-3 for the first, n-2 for the second, etc.) ensure we always have enough elements remaining to form a complete quadruplet. This prevents index out-of-bounds errors and unnecessary iterations.

Solution Approach

The implementation uses a brute force approach with four nested loops to enumerate all possible quadruplets. Let's walk through the algorithm step by step:

1. Initialize variables: We set ans = 0 to count valid quadruplets and store the array length in n for convenience.

2. First loop (index a): The outermost loop iterates from 0 to n-3. We stop at n-3 because we need at least 3 more elements after position a to form a valid quadruplet.

3. Second loop (index b): For each fixed a, we iterate b from a+1 to n-2. Starting from a+1 ensures a < b, and stopping at n-2 leaves room for indices c and d.

4. Third loop (index c): For each fixed pair (a, b), we iterate c from b+1 to n-1. This maintains b < c and leaves at least one position for d.

5. Fourth loop (index d): For each triple (a, b, c), we iterate d from c+1 to n. This ensures c < d and completes our quadruplet.

6. Check the sum condition: Inside the innermost loop, we check if nums[a] + nums[b] + nums[c] == nums[d]. If this condition is satisfied, we've found a valid quadruplet and increment our answer counter.

7. Return the result: After examining all possible quadruplets, we return the total count.

The algorithm systematically explores all combinations where a < b < c < d by design of the loop structure. Each inner loop starts one position after its parent loop's current index, which automatically enforces the ordering constraint without additional checks.

The time complexity is O(n^4) due to the four nested loops, and the space complexity is O(1) as we only use a constant amount of extra space for the counter and loop variables.

Example Walkthrough

Let's walk through the solution with nums = [1, 5, 3, 2, 6].

We need to find all quadruplets (a, b, c, d) where a < b < c < d and nums[a] + nums[b] + nums[c] == nums[d].

Step-by-step iteration:

Starting with a = 0 (nums[0] = 1):

• b = 1 (nums[1] = 5):
  • c = 2 (nums[2] = 3):
    • d = 3: Check if 1 + 5 + 3 = 9 equals nums[3] = 2? No.
    • d = 4: Check if 1 + 5 + 3 = 9 equals nums[4] = 6? No.
  • c = 3 (nums[3] = 2):
    • d = 4: Check if 1 + 5 + 2 = 8 equals nums[4] = 6? No.
• b = 2 (nums[2] = 3):
  • c = 3 (nums[3] = 2):
    • d = 4: Check if 1 + 3 + 2 = 6 equals nums[4] = 6? Yes! Count = 1

Moving to a = 1 (nums[1] = 5):

• b = 2 (nums[2] = 3):
  • c = 3 (nums[3] = 2):
    • d = 4: Check if 5 + 3 + 2 = 10 equals nums[4] = 6? No.

The algorithm continues checking all remaining combinations, but no other valid quadruplets are found.

Final result: 1 valid quadruplet at indices (0, 2, 3, 4) where 1 + 3 + 2 = 6.

The nested loop structure ensures we check all possible combinations exactly once while maintaining the required index ordering. Each loop's starting point (a+1, b+1, c+1) guarantees the strict inequality constraint is satisfied without additional conditional checks.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^4)

The code uses four nested loops to iterate through all possible quadruplets (a, b, c, d) where a < b < c < d.

• The outer loop runs n-3 times
• The second loop runs approximately n-2 times for each iteration of the first loop
• The third loop runs approximately n-1 times for each iteration of the second loop
• The innermost loop runs approximately n times for each iteration of the third loop

This results in approximately (n-3) * (n-2) * (n-1) * n / 4! iterations in the worst case, which simplifies to O(n^4).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variable ans to store the count
• Variable n to store the length of the array
• Loop variables a, b, c, d

No additional data structures are created that depend on the input size, so the space complexity is constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Loop Boundaries

One of the most common mistakes is setting incorrect loop boundaries, which can lead to either missing valid quadruplets or causing index out of bounds errors.

Incorrect Implementation:

# Wrong: This misses valid quadruplets or causes errors
for i in range(n):           # Should be n-3
    for j in range(i+1, n):   # Should be n-2
        for k in range(j+1, n): # Should be n-1
            for l in range(k+1, n):
                if nums[i] + nums[j] + nums[k] == nums[l]:
                    count += 1

Why it's wrong: The outer loops don't leave enough room for the remaining indices. For example, if i = n-1, there's no room for j, k, and l.

Correct Implementation:

for i in range(n - 3):        # Leaves room for j, k, l
    for j in range(i + 1, n - 2):  # Leaves room for k, l
        for k in range(j + 1, n - 1):  # Leaves room for l
            for l in range(k + 1, n):
                if nums[i] + nums[j] + nums[k] == nums[l]:
                    count += 1

2. Using Same Index Multiple Times

Another pitfall is accidentally allowing the same index to be used multiple times in a quadruplet.

Incorrect Implementation:

# Wrong: Allows same index to be used multiple times
for i in range(n - 3):
    for j in range(i, n - 2):    # Should start at i+1, not i
        for k in range(j, n - 1):  # Should start at j+1, not j
            for l in range(k, n):    # Should start at k+1, not k
                if nums[i] + nums[j] + nums[k] == nums[l]:
                    count += 1

Why it's wrong: Starting inner loops at the same index as the outer loop variable allows duplicate indices like (0, 0, 1, 2), which violates the requirement that all four indices must be distinct.

3. Optimization Opportunity: Early Termination

While not a bug, the brute force solution can be optimized with early termination when the sum becomes impossible.

Enhanced Implementation with Optimization:

def countQuadruplets(self, nums: List[int]) -> int:
    count = 0
    n = len(nums)
  
    # Sort to enable early termination (optional optimization)
    # Note: This changes indices, so only use if you don't need original positions
  
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            for k in range(j + 1, n - 1):
                target_sum = nums[i] + nums[j] + nums[k]
                for l in range(k + 1, n):
                    if nums[l] == target_sum:
                        count += 1
  
    return count

4. Memory-Efficient Alternative Using HashMap

For larger arrays, a more efficient approach uses a hashmap to reduce time complexity from O(n⁴) to O(n²).

Optimized Solution:

def countQuadruplets(self, nums: List[int]) -> int:
    count = 0
    n = len(nums)
  
    # Use hashmap to store sums of pairs
    for c in range(2, n - 1):
        sum_count = {}
        # Count all possible a+b where a < b < c
        for b in range(1, c):
            for a in range(b):
                sum_ab = nums[a] + nums[b]
                sum_count[sum_ab] = sum_count.get(sum_ab, 0) + 1
      
        # For each d > c, check if nums[d] - nums[c] exists in our map
        for d in range(c + 1, n):
            target = nums[d] - nums[c]
            if target in sum_count:
                count += sum_count[target]
  
    return count

This approach transforms the equation nums[a] + nums[b] + nums[c] = nums[d] into nums[a] + nums[b] = nums[d] - nums[c] and uses a hashmap to count matching pairs efficiently.