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(N³), 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(N³). 

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