4Sum - Practice Coding Problems

4Sum - Problem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Input & Output

Example 1 — Basic Case

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

› Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

💡 Note: Three unique quadruplets sum to 0: [-2,-1,1,2], [-2,0,0,2], and [-1,0,0,1]

Example 2 — No Solution

$ Input: nums = [2,2,2,2,2], target = 8

› Output: [[2,2,2,2]]

💡 Note: Only one unique quadruplet: [2,2,2,2] with sum = 8

Example 3 — Empty Result

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

› Output: []

💡 Note: No four numbers can sum to 20, maximum possible is 1+2+3+4=10

Constraints

1 ≤ nums.length ≤ 200
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹

Asked in

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

The 4Sum problem finds all unique quadruplets that sum to target. The key insight is to sort first, then use nested loops with two-pointer technique. Best approach uses Sort + Two Pointers with careful duplicate handling. Time: O(n³), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort + Three Pointers	O(n³)	O(1)	Sort array first, then fix one element and solve 3Sum for remaining
Optimized Two Pointers	O(n³)	O(1)	Sort first, then use two nested loops with two pointers for the innermost elements
Brute Force - Four Nested Loops	O(n⁴)	O(k)	Check all possible combinations of 4 elements

Sort + Three Pointers — Algorithm Steps

Sort the array
Fix first element, solve 3Sum on remaining
Use two pointers for efficient 3Sum solution
Skip duplicates to avoid repeated quadruplets

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort enables duplicate skipping and two-pointer technique

Fix Two Elements

Nested loops fix first two elements

Two Pointers

Use left/right pointers for remaining two elements

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int** solution(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare);
    int** result = malloc(1000 * sizeof(int*));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                long long total = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (total == target) {
                    int* quad = malloc(4 * sizeof(int));
                    quad[0] = nums[i]; quad[1] = nums[j]; quad[2] = nums[left]; quad[3] = nums[right];
                    result[*returnSize] = quad;
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                    
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    left++; right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int target;
    scanf("%d", &target);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(nums, numsSize, target, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < 4; j++) {
            printf("%d", result[i][j]);
            if (j < 3) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

One loop for first element, O(n²) for 3Sum on remaining n-1 elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for pointers and variables

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 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