4 Sum

Intuition

The idea is to check all possible quadruplets and among them, consider the ones whose sum is equal to the given target. And before considering them as our answer, sort the quadruplets in ascending order.

Approach

For getting quadruplets, 4 nested loops will be used.

The first loop(say i) will run from 0 to n-1. Inside which, there will be the second loop(say j) that will run from i+1 to n-1. The third loop(say k) that runs from j+1 to n-1. Inside loop k, the fourth loop(say l) will run from k+1 to n-1, yielding 4 elements from array for considering a quadruplet.

Now, inside these four nested loops, check the sum of arr[i], arr[j], arr[k] and arr[l], and if it is equal to the target, sort this quadruplet and insert it in the set data structure declared to store ans. Finally, return a list of stored quadruplets.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    //function to find quadruplets having sum equal to target
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // Size of the array
        int n = nums.size(); 
        
        // Set to store unique quadruplets
        set<vector<int>> st;
        
        // Checking all possible quadruplets
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        // Calculate the sum of the current quadruplet
                        long long sum = nums[i] + nums[j] + nums[k] + nums[l];
                        
                        // Check if the sum matches the target
                        if (sum == target) {
                            vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
                            // Sort the quadruplet to ensure uniqueness
                            sort(temp.begin(), temp.end());
                            st.insert(temp);
                        }
                    }
                }
            }
        }
        
        // Convert set to vector (unique quadruplets)
        vector<vector<int>> ans(st.begin(), st.end());
        return ans;
    }
};

int main() {
    vector<int> nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
    int target = 9;
    
    // Create an instance of Solution class
    Solution sol;

    vector<vector<int>> ans = sol.fourSum(nums, target);
    
    // Print the result
    cout << "The quadruplets are: \n";
    for (auto& it : ans) {
        cout << "[";
        for (auto& ele : it) {
            cout << ele << " ";
        }
        cout << "] ";
    }
    cout << "\n";
    
    return 0;
}
import java.util.*;

class Solution {
    //function to find quadruplets having sum equal to target
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //size of the array
        int n = nums.length;
        
        // Set to store unique quadruplets
        Set<List<Integer>> set = new HashSet<>();
        
        // Checking all possible quadruplets
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        // Calculate the sum of the current quadruplet
                        long sum = nums[i] + nums[j] + nums[k] + nums[l];
                        
                        // Check if the sum matches the target
                        if (sum == target) {
                            List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                            // Sort the quadruplet to ensure uniqueness
                            Collections.sort(temp);
                            set.add(temp);
                        }
                    }
                }
            }
        }
        
        // Convert set to list (unique quadruplets)
        return new ArrayList<>(set);
    }
    
    public static void main(String[] args) {
        int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
        int target = 9;
        
        //create an instance of the Solution class
        Solution sol = new Solution();
        
        List<List<Integer>> ans = sol.fourSum(nums, target);
        
        // Print the result
        System.out.println("The quadruplets are: ");
        for (List<Integer> quad : ans) {
            System.out.print("[");
            for (int num : quad) {
                System.out.print(num + " ");
            }
            System.out.print("] ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    #function to find quadruplets having sum equal to target
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #size of array
        n = len(nums)
        
        #Set to store unique quadruplets
        ans = set()
        
        # Checking all possible quadruplets
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    for l in range(k + 1, n):
                        # Calculate the sum of the current quadruplet
                        sum_val = nums[i] + nums[j] + nums[k] + nums[l]
                        
                        # Check if the sum matches the target
                        if sum_val == target:
                            temp = [nums[i], nums[j], nums[k], nums[l]]
                            # Sort the quadruplet to ensure uniqueness
                            temp.sort()
                            ans.add(tuple(temp))
        
        return list(ans)

if __name__ == "__main__":
    nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
    target = 9
    
    #Create an instance of Solution class
    sol = Solution()
    
    ans = sol.fourSum(nums, target)
    
    # Print the result
    print("The quadruplets are: ")
    for quad in ans:
        print(f"[{', '.join(map(str, quad))}]")
class Solution {
    // Function to find quadruplets with sum equal to target
    fourSum(nums, target) {
        const n = nums.length;
        const resultSet = new Set();
        
        // Checking all possible quadruplets
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                for (let k = j + 1; k < n; k++) {
                    for (let l = k + 1; l < n; l++) {
                        // Calculate the sum of the current quadruplet
                        const sum = nums[i] + nums[j] + nums[k] + nums[l];
                        
                        // Check if the sum matches the target
                        if (sum === target) {
                            const temp = [nums[i], nums[j], nums[k], nums[l]];
                            // Sort the quadruplet to ensure uniqueness
                            temp.sort((a, b) => a - b);
                            resultSet.add(temp.join(',')); // Use join to store as unique string
                        }
                    }
                }
            }
        }
        
        // Convert set back to array of arrays (unique quadruplets)
        const ans = Array.from(resultSet).map(item => item.split(',').map(Number));
        return ans;
    }
}

// Sample usage
const nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1];
const target = 9;

// Create an instance of Solution class
const sol = new Solution();
const ans = sol.fourSum(nums, target);

// Print the result
console.log("The quadruplets are:");
ans.forEach(quadruplet => {
    console.log(`[${quadruplet.join(' ')}]`);
});

Complexity Analysis

Time Complexity: O(N⁴) for using 4 nested loops, where N is size of the array. Space Complexity: O(2 x no. of the quadruplets), for using a set data structure and a list to store the quads.

Intuition

The better approach uses simple mathematics where some calculative parameter is taken in RHS(right hand side) to compute the result.

For example if a + b + c + d = 0, then a + b + c = -d. Similar idea is used here.

Approach

Iterate in the array from 0 to n-1 where n is the length of the array. Inside this loop, there will be the second loop(say j) that will run from i+1 to n-1. Then using a 3rd nested loop(say k) that runs from j+1 to n-1 try to calculate the value of the fourth element i.e. target - (nums[i]+nums[j]+nums[k]).

Declare a HashSet to store the specific array elements as we intend to search the fourth element in that HashSet.

If the fourth element exists in the HashSet, sort these four values i.e. nums[i], nums[j], nums[k], and the fourth element, and insert it in the set data structure declared to store ans.

After that, insert the k-th element i.e. nums[k] in the HashSet as we only want to insert those array elements that are in between indices j and k. Finally, return a list of stored quadruplets stored in the set data structure.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // Size of the array
        int n = nums.size(); 
        
        // Set to store unique quadruplets
        set<vector<int>> st; 

        // Checking all possible quadruplets
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                
                // Set to store elements seen so far in the loop
                set<long long> hashset; 
                for (int k = j + 1; k < n; k++) {
                    
                    // Calculate the fourth element needed to reach target
                    long long sum = nums[i] + nums[j];
                    sum += nums[k];
                    long long fourth = target - sum;
                    
                    /* Find if fourth element exists in
                    hashset (complements seen so far)*/
                    if (hashset.find(fourth) != hashset.end()) {
                        
                        // Found a quadruplet that sums up to target
                        vector<int> temp = {nums[i], nums[j], nums[k], static_cast<int>(fourth)};
                        // Sort the quadruplet to ensure uniqueness
                        sort(temp.begin(), temp.end()); 
                        st.insert(temp);
                        
                    }
                    
                    // Insert the kth element into hashset for future checks
                    hashset.insert(nums[k]);
                }
            }
        }
        
        // Convert set to vector (unique quadruplets)
        vector<vector<int>> ans(st.begin(), st.end());
        return ans;
    }
};

int main() {
    vector<int> nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
    int target = 9;
    
    // Create an instance of Solution class
    Solution sol;
    
    vector<vector<int>> ans = sol.fourSum(nums, target);
    
    // Print the result
    cout << "The quadruplets are: \n";
    for (auto& it : ans) {
        cout << "[";
        for (auto& ele : it) {
            cout << ele << " ";
        }
        cout << "] ";
    }
    cout << "\n";
    
    return 0;
}
import java.util.*;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        
        // Set to store unique quadruplets
        Set<List<Integer>> set = new HashSet<>();
        
        // Checking all possible quadruplets
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Set to store elements seen so far in the loop
                Set<Long> hashset = new HashSet<>();
                
                for (int k = j + 1; k < n; k++) {
                    /* Calculate the fourth element
                    needed to reach target*/
                    long sum = (long) nums[i] + nums[j] + nums[k];
                    long fourth = target - sum;
                    
                    /* Find if fourth element exists in 
                    hashset (complements seen so far)*/
                    if (hashset.contains(fourth)) {
                        // Found a quadruplet that sums up to target
                        List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k], (int) fourth);
                        Collections.sort(temp);
                        set.add(temp);
                    }
                    
                    // Insert the kth element into hashset for future checks
                    hashset.add((long) nums[k]);
                }
            }
        }
        
        // Convert set to list (unique quadruplets)
        ans.addAll(set);
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
        int target = 9;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        List<List<Integer>> ans = sol.fourSum(nums, target);
        
        // Print the result
        System.out.println("The quadruplets are:");
        for (List<Integer> quad : ans) {
            System.out.print("[");
            for (int num : quad) {
                System.out.print(num + " ");
            }
            System.out.println("]");
        }
    }
}
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        ans = []
        n = len(nums)
        
        # Set to store unique quadruplets
        st = set()
        
        # Checking all possible quadruplets
        for i in range(n):
            for j in range(i + 1, n):
                # Set to store elements seen so far in the loop
                hashset = set()
                
                for k in range(j + 1, n):
                    # Calculate the fourth element needed to reach target
                    summ = nums[i] + nums[j] + nums[k]
                    fourth = target - summ
                    
                    """ Find if fourth element exists in
                    hashset (complements seen so far)"""
                    if fourth in hashset:
                        
                        # Found a quadruplet that sums up to target
                        temp = sorted([nums[i], nums[j], nums[k], fourth])
                        st.add(tuple(temp))
                    
                    # Insert the kth element into hashset for future checks
                    hashset.add(nums[k])
        
        # Convert set to list (unique quadruplets)
        ans = [list(t) for t in st]
        return ans

if __name__ == "__main__":
    nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
    target = 9
    
    # Create an instance of Solution class
    sol = Solution()
    
    ans = sol.fourSum(nums, target)
    
    # Print the result
    print("The quadruplets are:")
    for quad in ans:
        print(quad)
class Solution {
    // Function to find quadruplets with sum equal to target
    fourSum(nums, target) {
        let ans = [];
        let n = nums.length;
        
        // Set to store unique quadruplets
        let set = new Set();
        
        // Checking all possible quadruplets
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                // Set to store elements seen so far in the loop
                let hashset = new Set();
                
                for (let k = j + 1; k < n; k++) {
                    /* Calculate the fourth element
                    needed to reach target*/
                    let sum = nums[i] + nums[j] + nums[k];
                    let fourth = target - sum;
                    
                    /* Find if fourth element exists in 
                    hashset (complements seen so far)*/
                    if (hashset.has(fourth)) {
                        
                        // Found a quadruplet that sums up to target
                        let temp = [nums[i], nums[j], nums[k], fourth].sort((a, b) => a - b);
                        set.add(temp.join());
                        
                    }
                    
                    // Insert the kth element into hashset for future checks
                    hashset.add(nums[k]);
                }
            }
        }
        
        // Convert set to array (unique quadruplets)
        set.forEach(item => {
            ans.push(item.split(',').map(Number));
        });
        
        return ans;
    }
}

// Sample usage
const nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1];
const target = 9;

// Create an instance of Solution class
const sol = new Solution();
const ans = sol.fourSum(nums, target);

// Print the result
console.log("The quadruplets are:");
ans.forEach(quadruplet => {
    console.log(`[${quadruplet.join(' ')}]`);
});

Complexity Analysis

Time Complexity: O(N³xlog(M)), for using 3 nested loops and inside the loops there are some operations on the set data structure which take log(M) time complexity, where N is size of the array, M is number of elements in the set. Space Complexity: O(2 x no. of the quadruplets)+O(N) for using a set data structure and a list to store the quads. This results in the first term. And the second space is taken by the set data structure we are using to store the array elements. At most, the set can contain approximately all the array elements and so the space complexity is O(N).

Intuition

The optimal approach is based on similar idea from 2-Sum and 3-Sum problem, which is sorting the entire array in the first step and to get the unique quads and using pointers to keep getting unique quads.

Approach

Sort the entire array and iterate from 0 to n-1 in the array where n is length of the array, lets call the loop variable i. In each iteration, i will be fixed for all different values of the rest of the 3 pointers. Inside the loop, first check if the current and the previous element is the same and if it is, do nothing and continue to the next value of i.

After the first check inside the loop, introduce another fixed pointer j(runs from i+1 to n-1). Again check for duplicate elements and only perform any further operation if the elements are different.

Now, there will be 2 moving pointers i.e. k(starts from j+1) and l(starts from the last index). The pointer k will move forward and the pointer l will move backward in the array until they cross each other while the value of i and j will be fixed.

Check the sum i.e. nums[i]+nums[j]+nums[k]+nums[l], if the sum is greater, then the idea is to minimize the sum, hence we need lesser elements and so decrease the value of l and if the sum is lesser than the target, we need a bigger value and so we will increase the value of k.

If the sum is equal to the target, simply insert the quad i.e. nums[i], nums[j], nums[k], and nums[l] into answer and move the pointers k and l skipping the duplicate elements(i.e. by checking the adjacent elements while moving the pointers). Finally, return the list of unique quadruplets.

Dry Run

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    //function to find quadruplets having sum equals to target
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // Vector to store the quadruplets that sum up to target
        vector<vector<int>> ans;
        
        int n = nums.size();
        
        // Sort the input array nums
        sort(nums.begin(), nums.end());
        
        // Iterate through the array to find quadruplets
        for (int i = 0; i < n; i++) {
            // Skip duplicates for i
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            
            for (int j = i + 1; j < n; j++) {
                // Skip duplicates for j
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                
                // Two pointers approach
                int k = j + 1;
                int l = n - 1;
                
                while (k < l) {
                    long long sum = nums[i] + nums[j] + nums[k] + nums[l];
                    
                    if (sum == target) {
                        // Found a quadruplet that sums up to target
                        vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
                        ans.push_back(temp);
                        
                        // Skip duplicates for k and l
                        k++;
                        l--;
                        while (k < l && nums[k] == nums[k - 1]) k++;
                        while (k < l && nums[l] == nums[l + 1]) l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        
        return ans;
    }
};

int main() {
    vector<int> nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
    int target = 9;
    
    // Create an instance of Solution class
    Solution sol;
    
    vector<vector<int>> ans = sol.fourSum(nums, target);
    
    // Print the result
    cout << "The quadruplets are: \n";
    for (auto& it : ans) {
        cout << "[";
        for (auto& ele : it) {
            cout << ele << " ";
        }
        cout << "] ";
    }
    cout << "\n";
    
    return 0;
}
import java.util.*;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        
        // Sort the input array nums
        Arrays.sort(nums);
        
        // Iterate through the array to find quadruplets
        for (int i = 0; i < n; i++) {
            // Skip duplicates for i
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            
            for (int j = i + 1; j < n; j++) {
                // Skip duplicates for j
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                
                // Two pointers approach
                int k = j + 1;
                int l = n - 1;
                
                while (k < l) {
                    long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
                    
                    if (sum == target) {
                        // Found a quadruplet that sums up to target
                        List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                        ans.add(temp);
                        
                        // Skip duplicates for k and l
                        k++;
                        l--;
                        while (k < l && nums[k] == nums[k - 1]) k++;
                        while (k < l && nums[l] == nums[l + 1]) l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        
        return ans;
    }
    
    public static void main(String[] args) {
        int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
        int target = 9;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        List<List<Integer>> ans = sol.fourSum(nums, target);
        
        // Print the result
        System.out.println("The quadruplets are: ");
        for (List<Integer> quad : ans) {
            System.out.print("[");
            for (int num : quad) {
                System.out.print(num + " ");
            }
            System.out.println("]");
        }
    }
}
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        ans = []
        n = len(nums)
        
        # Sort the input array nums
        nums.sort()
        
        # Iterate through the array to find quadruplets
        for i in range(n):
            # Skip duplicates for i
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            for j in range(i + 1, n):
                # Skip duplicates for j
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                
                # Two pointers approach
                k = j + 1
                l = n - 1
                
                while k < l:
                    sum_val = nums[i] + nums[j] + nums[k] + nums[l]
                    
                    if sum_val == target:
                        # Found a quadruplet that sums up to target
                        temp = [nums[i], nums[j], nums[k], nums[l]]
                        ans.append(temp)
                        
                        # Skip duplicates for k and l
                        k += 1
                        l -= 1
                        while k < l and nums[k] == nums[k - 1]:
                            k += 1
                        while k < l and nums[l] == nums[l + 1]:
                            l -= 1
                    elif sum_val < target:
                        k += 1
                    else:
                        l -= 1
        
        return ans

if __name__ == "__main__":
    nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
    target = 9
    
    # Create an instance of Solution class
    sol = Solution()

    ans = sol.fourSum(nums, target)
    
    # Print the result
    print("The quadruplets are: ")
    for quad in ans:
        print(quad)
class Solution {
    // Function to find quadruplets with sum equal to target
    fourSum(nums, target) {
        let ans = [];
        let n = nums.length;
        
        // Sort the input array nums
        nums.sort((a, b) => a - b);
        
        // Iterate through the array to find quadruplets
        for (let i = 0; i < n; i++) {
            // Skip duplicates for i
            if (i > 0 && nums[i] === nums[i - 1])
                continue;
            
            for (let j = i + 1; j < n; j++) {
                // Skip duplicates for j
                if (j > i + 1 && nums[j] === nums[j - 1])
                    continue;
                
                // Two pointers approach
                let k = j + 1;
                let l = n - 1;
                
                while (k < l) {
                    let sum = nums[i] + nums[j] + nums[k] + nums[l];
                    
                    if (sum === target) {
                        // Found a quadruplet that sums up to target
                        ans.push([nums[i], nums[j], nums[k], nums[l]]);
                        
                        // Skip duplicates for k and l
                        k++;
                        l--;
                        while (k < l && nums[k] === nums[k - 1]) k++;
                        while (k < l && nums[l] === nums[l + 1]) l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        
        return ans;
    }
}

// Sample usage
const nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1];
const target = 9;

// Create an instance of Solution class
const sol = new Solution();
const ans = sol.fourSum(nums, target);

// Print the result
console.log("The quadruplets are:");
ans.forEach(quadruplet => {
    console.log(`[${quadruplet.join(' ')}]`);
});

Complexity Analysis

Time Complexity: O(N³), as each of the pointers i and j, is running for approximately N times. And both the pointers k and l combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N³). Here N is size of the array. Space Complexity: O(no. of quadruplets), this space is only used to store the answer. No extra space is used to solve this problem. So, from that perspective, space complexity can be written as O(1).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code