3Sum Closest - Practice Coding Problems

3Sum Closest - Problem

Given an integer array nums of length n and an integer target, find three integers at distinct indices in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input will have exactly one solution.

Input & Output

Example 1 — Basic Case

$ Input: nums = [-1,2,1,-4], target = 1

› Output: 2

💡 Note: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)

Example 2 — Exact Match

$ Input: nums = [0,0,0], target = 1

› Output: 0

💡 Note: The only possible sum is 0 + 0 + 0 = 0, which has distance |0-1| = 1 from target

Example 3 — Negative Target

$ Input: nums = [1,1,1,0], target = -100

› Output: 2

💡 Note: Closest sum is 0 + 1 + 1 = 2, which is closest to target -100

Constraints

3 ≤ nums.length ≤ 500
-1000 ≤ nums[i] ≤ 1000
-10⁴ ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers and target value

Process

Find three numbers whose sum is closest to target

Output

Return the actual sum (not indices)

Key Takeaway

🎯 Key Insight: Sort first to enable efficient two-pointer search, reducing from O(n³) to O(n²)

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to sort the array first, then use two pointers to efficiently find the closest triplet sum. Best approach is Sort + Two Pointers with Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible triplets and track the closest sum
Sort + Two Pointers	O(n²)	O(1)	Sort the array, then use two pointers for each element to find closest triplet

Brute Force — Algorithm Steps

Step 1: Use three nested loops to generate all triplets
Step 2: Calculate sum for each triplet
Step 3: Update closest sum if current is closer to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Use three nested loops to create all combinations

Calculate Sum

Add the three elements in each triplet

Track Closest

Keep the sum closest to target

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int target) {
    int closestSum = INT_MAX;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                int currentSum = nums[i] + nums[j] + nums[k];
                if (abs(currentSum - target) < abs(closestSum - target)) {
                    closestSum = currentSum;
                }
            }
        }
    }
    
    return closestSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || strcmp(token, "0") == 0) {
            nums[numsSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops iterate through all possible triplet combinations

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for variables

✓ Linear Space

68.0K Views

High Frequency

~25 min Avg. Time

2.4K 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