3Sum With Multiplicity - Practice Coding Problems

3Sum With Multiplicity - Problem

Given an integer array arr and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 10⁹ + 7.

Note: We need to count the number of valid index triplets, not unique value triplets.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,1,2,2,3,3], target = 6

› Output: 8

💡 Note: We need triplets where arr[i] + arr[j] + arr[k] = 6 and i < j < k. Valid combinations: 1+2+3=6. With indices: (0,2,4), (0,2,5), (0,3,4), (0,3,5), (1,2,4), (1,2,5), (1,3,4), (1,3,5) = 8 triplets

Example 2 — No Valid Triplets

$ Input: arr = [1,1,2,2,2,2], target = 5

› Output: 12

💡 Note: Valid triplet: 1+2+2=5. We have 2 ways to choose first element (value 1) and C(4,2)=6 ways to choose two elements with value 2. Total: 2 × 6 = 12 triplets

Example 3 — Same Values

$ Input: arr = [2,2,2,2], target = 6

› Output: 4

💡 Note: Need three 2's to sum to 6: 2+2+2=6. With 4 elements, we can choose 3 in C(4,3) = 4 ways: (0,1,2), (0,1,3), (0,2,3), (1,2,3)

Constraints

3 ≤ arr.length ≤ 3000
0 ≤ arr[i] ≤ 100
0 ≤ target ≤ 300

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,1,2,2,3,3] and target 6

Find Valid Triplets

Find all i < j < k where arr[i] + arr[j] + arr[k] = 6

Count Results

Total of 8 valid index triplets

Key Takeaway

🎯 Key Insight: Count frequencies first, then calculate combinations for each unique triplet mathematically

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to avoid checking all O(n³) combinations by using frequency counting. Count how many times each unique value appears, then for each valid triplet of values that sum to target, calculate the number of ways to choose indices using combinatorics. Best approach is frequency counting with Time: O(n + m³), Space: O(m) where m is number of unique values.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible triplets with three nested loops
Two Pointers with Sorting	O(n²)	O(n)	Sort array and use two pointers for each fixed first element
Frequency Counting	O(n + m³)	O(m)	Count frequencies of each value, then calculate combinations mathematically

Brute Force — Algorithm Steps

Use three nested loops for indices i, j, k where i < j < k
For each triplet, check if sum equals target
Count valid triplets and return result modulo 10⁹ + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Three Nested Loops

Generate all i < j < k combinations

Sum Check

Check if arr[i] + arr[j] + arr[k] = target

Count Valid

Increment counter for valid triplets

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int arrSize, int target) {
    const int MOD = 1000000007;
    int count = 0;
    
    for (int i = 0; i < arrSize; i++) {
        for (int j = i + 1; j < arrSize; j++) {
            for (int k = j + 1; k < arrSize; k++) {
                if (arr[i] + arr[j] + arr[k] == target) {
                    count = (count + 1) % MOD;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && (token[0] >= '0' && token[0] <= '9') || token[0] == '-') {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(arr, arrSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops each running up to n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

956 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler