## DEV Community is a community of 871,761 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

sachin26

Posted on

# Striver's SDE Sheet Journey - #19 Four sum

Problem Statement :-

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,

1. 0 <= a, b, c, d < n
2. a, b, c, and d are distinct.
3. nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example

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

Result : `[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`

## Solution 1

fix three pointers and look for the last one

``````nums = [1,0,-1,0,-2,2] ,target=0

nums = [1,0,-1,0,-2,2]
| |  | < look for the last one >
i j  k
``````

step-1 sort the array `nums` and initialise an variable `ans`.

step-2 run three loops linearly for `i`, `j`, `k` pointers

1. find the last element, using binary search.
2. if the last element found then add the quadruplet to `ans`

## Java

``````class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {

Set<List<Integer>> ans = new HashSet<List<Integer>>();
int n = nums.length;

Arrays.sort(nums);

for(int i=0; i<n; i++){

for(int j=i+1; j<n; j++){

for(int k=j+1; k<n; k++){

int x = target - (nums[i] + nums[j] + nums[k]);

if(Arrays.binarySearch(Arrays.copyOfRange(nums,k+1,n),x) >= 0){
List<Integer> r = new ArrayList<Integer>();

}
}
}
}

List<List<Integer>> result = new ArrayList<List<Integer>>();

for(List<Integer> list : ans){