# 4 Sum | Find Quads that add up to a target value4 Sum

[Question]: Find Quads that add up to a target value4 Sum

##### Approach# using the 4 pointers

Two pointers a & b are fixed and we have two moving pointers c and d. where c starts from b + 1 and d is start from last index

``````
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
guard len >= 4 else { return [] }// minimum 4 items required for 4 sum

var result = [[Int]]()
let sort = nums.sorted()

for a in 0..<(len - 1) where a == 0 || sort[a] != sort[a-1] { // if sort[a] == sort[a-1] discard the loop // a is fix pointer
for b in (a + 1)..<len where b == a + 1 || sort[b] != sort[b-1] {// if sort[b] == sort[b-1] discard the loop // b is fix pointer
var c = b + 1, d = len - 1// c pointer is b+1 which is movable
while c < d {// As array is sorted check if c pointer doesn't jump
let val = (a: sort[a], b: sort[b], c: sort[c], d: sort[d])
let sum = (val.a + val.b + val.c + val.d)
if sum == target { result.append([val.a,val.b,val.c,val.d]) }// add result to the array as we found the desired sum
if sum < target {
while sort[c] == val.c, c < d { c += 1 }// increment c pointer as we get lesser sum
} else {
while sort[d] == val.d, d > b { d -= 1 }// decrement d pointer which is the last
}
}
}
}
return result
}

let fourSumInputArray = [1,0,-1,0,-2,2]
let fourSumOutputArray = fourSum(fourSumInputArray, 0)
print("Output array-->", fourSumOutputArray) //[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
``````
##### Complexity Analysis

Time Complexity: O(N3), where N = size of the array.
Reason: Each of the pointers c and d, 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(N3).

Space Complexity:  O(n) where we stores the result.