clueless coding // TODO: be smarter

LeetCode 18. 4Sum: CPP Solution



Problem Statement

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: The solution set must not contain duplicate quadruplets.

Function Signature (C++):
  vector<vector<int>> fourSum(vector<int>& nums, int target)

Inputs:
  nums = [1, 0, -1, 0, -2, 2]
  target = 0

Outputs:
  [
    [-1,  0, 0, 1],
    [-2, -1, 1, 2],
    [-2,  0, 0, 2]
  ]



TL;DR Code Solution

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());

    vector<vector<int>> result;

    int size = (int)nums.size();
    for (int i = 0; i < size - 3; i++) {
        int first = nums[i];
        for (int j = i + 1; j < size - 2; j++) {
            int second = nums[j];
            int left = j + 1;
            int right = size - 1;
            while (left < right) {
                int numLeft = nums[left];
                int numRight = nums[right];

                int sum = first + second + nums[left] + nums[right];
                if (sum == target) {
                    vector<int> current = {first, second, nums[left], nums[right]};
                    result.push_back(current);

                    while (left < right && nums[left] == numLeft)
                        left++;
                    while (left < right && nums[right] == numRight)
                        right--;
                }
                else if (sum < target) {
                    left++;
                }
                else {
                    right--;
                }
            }
            while (j + 1 < size  - 2 && nums[j+1] == nums[j])
                j++;
        }
            while (i + 1 < size  - 3 && nums[i+1] == nums[i])
                i++;
    }

    return result;
}