4Sum In C,CPP,JAVA,PYTHON,C#,JS

Spread the love

Close-up of HTML code highlighted in vibrant colors on a computer monitor.

Table of Contents

Problem Statement: 4Sum

You are given an array of integers, nums, and an integer, target. Your task is to find all unique quadruplets [a,b,c,d][a, b, c, d][a,b,c,d] in the array such that: a+b+c+d=target a + b + c + d = \text{target}a+b+c+d=target

Constraints:

The array may contain both positive and negative integers.
The solution set must not contain duplicate quadruplets.
Return the list of quadruplets in any order.

Approaches to Solve the Problem

1. Brute Force Approach

Description:
- Use four nested loops to generate all possible quadruplets.
- Check if the sum of the quadruplet equals the target.
- Store the quadruplets in a set to avoid duplicates.
Time Complexity: O(n4)O(n^4)O(n4), as we are iterating through all possible quadruplets.
Space Complexity: O(1)O(1)O(1) (excluding the result storage).

2. Optimized Approach Using Sorting and Two Pointers

Steps:
1. Sort the array: Sorting the array helps in efficiently managing duplicates and using two pointers.
2. Fix two pointers:
  - Use two nested loops for the first two pointers, i and j.
  - Ensure duplicates are skipped by checking if the current element is the same as the previous one.
3. Two-pointer search:
  - For the remaining two numbers, use the two-pointer approach:
    - Initialize left to j+1j+1j+1 and right to the end of the array.
    - Calculate the sum: nums[i]+nums[j]+nums[left]+nums[right]\text{nums}[i] + \text{nums}[j] + \text{nums}[left] + \text{nums}[right]nums[i]+nums[j]+nums[left]+nums[right].
    - Adjust pointers:
      - If the sum equals the target, add the quadruplet to the result.
      - Move left and right pointers to avoid duplicates.
      - If the sum is less than the target, increment left.
      - If the sum is greater than the target, decrement right.
Time Complexity: O(n3)O(n^3)O(n3), due to two nested loops and two-pointer search for each iteration.
Space Complexity: O(1)O(1)O(1), as no additional space is used except for the result.

3. Hash Table Approach (Alternate Method)

Description:
- Use a hash table to store pairs of numbers along with their indices.
- Iterate through the array and for every pair, check if the complement (target – current sum) exists in the hash table.
- Ensure that indices of quadruplets do not overlap.
- Avoid duplicates by maintaining unique quadruplets in the result.
Time Complexity: O(n2)O(n^2)O(n2) for generating pairs and O(n2)O(n^2)O(n2) for checking complements, leading to O(n2+n2)=O(n2)O(n^2 + n^2) = O(n^2)O(n2+n2)=O(n2).
Space Complexity: O(n2)O(n^2)O(n2), for storing pairs in the hash table.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	O(n4)O(n^4)O(n4)	O(1)O(1)O(1)	Simple to implement	Inefficient for large arrays
Sorting + Two Pointers	O(n3)O(n^3)O(n3)	O(1)O(1)O(1)	Efficient, avoids duplicates easily	Sorting modifies original array
Hash Table	O(n2)O(n^2)O(n2)	O(n2)O(n^2)O(n2)	Faster for large arrays	High memory usage

Key Observations

Sorting is crucial for efficiently avoiding duplicates.
Two-pointer technique reduces the time complexity significantly compared to brute force.
Hash table-based approaches can outperform two-pointer approaches for very large datasets, but they may require significant memory.

C Implementation

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

void fourSum(int* nums, int numsSize, int target) {
    // Sort the array
    qsort(nums, numsSize, sizeof(int), cmp);

    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) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    printf("[%d, %d, %d, %d]\n", nums[i], nums[j], nums[left], nums[right]);
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
}

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

int main() {
    int nums[] = {1, 0, -1, 0, -2, 2};
    int target = 0;
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    fourSum(nums, numsSize, target);
    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size() - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < nums.size() - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> result = fourSum(nums, target);

    for (const auto& quad : result) {
        cout << "[" << quad[0] << ", " << quad[1] << ", " << quad[2] << ", " << quad[3] << "]\n";
    }

    return 0;
}

Java Implementation

import java.util.*;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;

        List<List<Integer>> result = fourSum(nums, target);
        for (List<Integer> quad : result) {
            System.out.println(quad);
        }
    }
}

Python Implementation

def four_sum(nums, target):
    nums.sort()
    result = []

    for i in range(len(nums) - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, len(nums) - 1
            while left < right:
                sum_ = nums[i] + nums[j] + nums[left] + nums[right]
                if sum_ == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif sum_ < target:
                    left += 1
                else:
                    right -= 1
    return result

# Example usage
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(four_sum(nums, target))

C# Implementation

using System;
using System.Collections.Generic;

class FourSum {
    public static IList<IList<int>> FourSumSolution(int[] nums, int target) {
        Array.Sort(nums);
        var result = new List<IList<int>>();

        for (int i = 0; i < nums.Length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.Length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.Length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        int[] nums = { 1, 0, -1, 0, -2, 2 };
        int target = 0;

        var result = FourSumSolution(nums, target);
        foreach (var quad in result) {
            Console.WriteLine($"[{string.Join(", ", quad)}]");
        }
    }
}

JavaScript Implementation

function fourSum(nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            let left = j + 1, right = nums.length - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

// Example usage
console.log(fourSum([1, 0, -1, 0, -2, 2], 0));