[LeetCode] 4Sum

Problem: 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:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• 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
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Approach: We can sort this array and then can use two pointer approach to solve this problem.

Implementation in C#:

    public IList<IList<int>> FourSum(int[] nums, int target)

    {

        int length = nums?.Length ?? 0;

        var result = new List<IList<int>>();

        if (length <= 3)

        {

            return result;

        }

        Array.Sort(nums);

        for (int i = 0; i < length - 3; ++i)

        {

            if (i > 0 && nums[i] == nums[i - 1])

            {

                continue;

            }

            for (int j = i + 1; j < length - 2; ++j)

            {

                if (j > i + 1 && nums[j] == nums[j - 1])

                {

                    continue;

                }

                int k = j + 1;

                int l = length - 1;

                while (k < l)

                {

                    long currSum = (long)nums[i] +

                                   (long)nums[j] +

                                   (long)nums[k] +

                                   (long)nums[l];

                    if (currSum == target)

                    {

                        result.Add(new List<int>{nums[i],

                                                 nums[j],

                                                 nums[k++],

                                                 nums[l--]});

                        while (k < l && nums[k] == nums[k - 1])

                        {

                            ++k;

                        }

                        while (k < l && nums[l] == nums[l + 1])

                        {

                            --l;

                        }

                    }

                    else if (currSum < target)

                    {

                        ++k;

                    }

                    else

                    {

                        --l;

                    }

                }

            }

        }

        return result;

    }

Complexity: O(n^3)