[Leetcode] 4Sum | Yufei Zhao @ Columbia University

[Leetcode] 4Sum | Yufei Zhao @ Columbia University

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

My Idea
4Sum is also similar with 3Sum/3Sum closest problem. Here we user 4 pointers instead of 3 to track the 4 elements in quadruplet.
First we sort the array to make quadruplet in non-descending order and avoid same quadruplet with elements in different order.
Then we loop the first and second pointer through array and try to find the third and fourth elements which sums to target-num[first]-num[second]. Here we are solving 2Sum problem again.
The time complexity is O(n^3)

Read full article from [Leetcode] 4Sum | Yufei Zhao @ Columbia University