4Sum passing with N^3 * LogN

Revisited an old problem: https://leetcode.com/problems/4sum/description/

Given an array nums of n integers and an integer target, are there elements abc, and d in nums 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.
Example:
Given array nums = [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]
]
It failed for me 2 years back when I tried a simple N^4 solution (four nested for loops). An optimization for the last loop - using Binary Search instead of a loop - made the trick, bringing the complexity down to N^3 * LogN, good enough to pass. Cheers, ACC.


public class Solution
{
public IList<IList<int>> FourSum(int[] nums, int target)
{
if (nums == null || nums.Length == 0) return new List<IList<int>>();

Hashtable htSolutions = new Hashtable();
List<IList<int>> solutions = new List<IList<int>>();

Array.Sort(nums);
long t = (long)target;

long partialSum = 0;

if (target >= 0)
{
for (int a = 0; a < nums.Length; a++)
{
partialSum += nums[a];
if (partialSum > t)
{
partialSum -= nums[a];
break;
}

for (int b = a + 1; b < nums.Length; b++)
{
partialSum += nums[b];
if (partialSum > t)
{
partialSum -= nums[b];
break;
}

for (int c = b + 1; c < nums.Length; c++)
{
partialSum += nums[c];
if (partialSum > t)
{
partialSum -= nums[c];
break;
}

if (BinarySearch(nums, c + 1, nums.Length - 1, target - partialSum))
{
string key = nums[a].ToString() + "@" + nums[b].ToString() + "@" + nums[c].ToString() + "@" + (target - partialSum).ToString();
if (!htSolutions.ContainsKey(key))
{
List<int> list = new List<int>();
list.Add(nums[a]);
list.Add(nums[b]);
list.Add(nums[c]);
list.Add((int)(target - partialSum));
solutions.Add(list);
htSolutions.Add(key, true);
}
}

partialSum -= nums[c];
}

partialSum -= nums[b];
}

partialSum -= nums[a];
}
}
else
{
for (int a = nums.Length - 1; a >= 0; a--)
{
partialSum += nums[a];
if (partialSum < t)
{
partialSum -= nums[a];
break;
}

for (int b = a - 1; b >= 0; b--)
{
partialSum += nums[b];
if (partialSum < t)
{
partialSum -= nums[b];
break;
}

for (int c = b - 1; c >= 0; c--)
{
partialSum += nums[c];
if (partialSum < t)
{
partialSum -= nums[c];
break;
}

if (BinarySearch(nums, 0, c - 1, target - partialSum))
{
string key = nums[a].ToString() + "@" + nums[b].ToString() + "@" + nums[c].ToString() + "@" + (target - partialSum).ToString();
if (!htSolutions.ContainsKey(key))
{
List<int> list = new List<int>();
list.Add(nums[a]);
list.Add(nums[b]);
list.Add(nums[c]);
list.Add((int)(target - partialSum));
solutions.Add(list);
htSolutions.Add(key, true);
}
}

partialSum -= nums[c];
}

partialSum -= nums[b];
}

partialSum -= nums[a];
}
}
return solutions;
}

private bool BinarySearch(int[] nums,
int left,
int right,
long target)
{
while (left >= 0 &&
left < nums.Length &&
right >= 0 &&
right < nums.Length &&
left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}

return false;
}
}

Comments

  1. My old solution https://gist.github.com/ttsugriy/ef7f21755df78d4825b7607c3a6299fe had a O(N^3) complexity by taking advantage of the fact that it's possible to find a target sum for the 2 numbers in O(N) time.

    class Solution {
    public:
    vector> fourSum(vector& nums, int target) {
    if (nums.size() < 4) return {};
    sort(nums.begin(), nums.end());
    set> solutions;
    int left = 0;
    int right = nums.size() - 1;
    for (int left = 0; left <= nums.size() - 4; ++left) {
    for (int right = left + 3; right < nums.size(); ++right) {
    int halfSum = nums[left] + nums[right];
    int otherHalf = target - halfSum;
    int innerLeft = left + 1;
    int innerRight = right - 1;
    while (innerLeft < innerRight) {
    int innerSum = nums[innerLeft] + nums[innerRight];
    if (innerSum < otherHalf) {
    innerLeft += 1;
    } else if (innerSum > otherHalf) {
    innerRight -= 1;
    } else {
    solutions.insert({nums[left], nums[innerLeft], nums[innerRight], nums[right]});
    innerLeft += 1;
    innerRight -= 1;
    }
    }
    }
    }
    return vector>(solutions.cbegin(), solutions.cend());
    }
    };

    I think it can be further optimized by generating all sums O(N^2), sorting them and using O(N) sum finding algorithm to find 2 sums that add up to the final sum, but I was too lazy to try this out :)

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons