« back

4Sum

Tags : array, pointers, sorting, leetcode, cpp, medium

Problem Statement - link #

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:

You may return the answer in any order.

Examples #

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

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

Constraints #

Solutions #

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
      sort(nums.begin(), nums.end());
      vector<vector<int>> res;
      int n = nums.size();
      for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
          int l = j+1, r = n-1;
          int t = target - nums[i] - nums[j];
          
          while(l<r){
            int s = nums[l] + nums[r];
            if(s<t) l++;
            else if(s>t) r--;
            else{
              vector<int> v = {nums[i],nums[j],nums[l],nums[r]};
              res.push_back(v);
              while(l<r and nums[l]==v[2]) l++;
              while(l<r and nums[r]==v[3]) r--;
            }
            
          }
          while(j+1<n and nums[j]==nums[j+1]) j++;
        }        
        while(i+1<n and nums[i]==nums[i+1]) i++;
      }
      return res;
    }
};