ThreeSum

The 3Sum challenge is particularly an interesting one that we tend to get stuck on… at least I do.

The problem description:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

With that in mind, let’s look at their example output:

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

Although there are a few ways to handle this that require more code, we’re going to look at a slightly more daunting method for solving this challenge by using a HashSet.

We’ll be working in rust for this challenge, but it should be easy to translate to other languages.

Implementation

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        // Fill it out here
    }
}

Let’s set up a return value, aka what we’ll return back as a Vec<Vec<i32>> and sort the array. (We’ll also declare the solution input to be mut otherwise we’d have to create a mutable copy).

There is a second way to handle this without sorting, but by presorting, we don’t have to work through dealing with duplicates and can bring the problem down to split and conquer.

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort(); // initial sort
        let mut ret: Vec<Vec<i32>> = Vec::new();

        return ret;
    }
}

Next, we’ll run through each of the entries in the input, starting with the 0th. Notice that we can only ever get to a solution that works if the index is non-zero and we’re not duplicating elements in the input. Let’s create a loop to handle these conditions:

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort(); // initial sort
        let mut ret: Vec<Vec<i32>> = Vec::new();

        for i in 0..nums.len() {
            // If we're at the initial index _or_ we're repeating a number
            // skip it
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            // Build the solution
        }

        return ret;
    }
}

Now we can get to finding a solution. This is the easier part. Now we have to iterate down through the remaining parts of the input and test if the solution is zero or not. This is a perfect case to use two pointers.

The first pointer starts at the following number while the second starts at the last element. We’ll loop through them until the two pointers meet. For each iteration, we’ll test if the two elements sum to zero. If they do, we’ll add them to the return value.

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort(); // initial sort
        let mut ret: Vec<Vec<i32>> = Vec::new();

        for i in 0..nums.len() {
            // If we're at the initial index _or_ we're repeating a number
            // skip it
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            let mut left = i + 1;
            let mut right = nums.len() - 1;

            // For every iteration where the left pointer has not met the right
            while left < right {
                // Calculate the sum
                let sum = nums[i] + nums[left] + nums[right];

                if sum == 0 {
                    ret.push(vec![nums[i], nums[left], nums[right]]);
                }
            }
        }

        return ret;
    }
}

We’re not done yet… we need to move the pointers otherwise we’re in an infinite loop.

There are 3 cases:

• The sum is negative: we should move the right pointer back because the negative number is pushing the sum down
• The sum is positive: the positive number is greater than the negative.
• The sum is zero… we’ve already found this solution, so let’s push it up one

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort(); // initial sort
        let mut ret: Vec<Vec<i32>> = Vec::new();

        for i in 0..nums.len() {
            // If we're at the initial index _or_ we're repeating a number
            // skip it
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            let mut left = i + 1;
            let mut right = nums.len() - 1;

            // For every iteration where the left pointer has not met the right
            while left < right {
                // Calculate the sum
                let sum = nums[i] + nums[left] + nums[right];

                if sum == 0 {
                    ret.push(vec![nums[i], nums[left], nums[right]]);
                    left += 1;
                } else if sum > 0 {
                    // Sum is positive
                    right -= 1;
                } else {
                    // Sum is negative
                    left += 1;
                }
            }
        }

        return ret;
    }
}

One more optimization we can make is to skip through the remaining values when the sum is zero where the number on the left is equal to that of the previous element. This helps us skip duplicates.

	

		

			Toggle
Numbering
			Copy
		
	

	
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort(); // initial sort
        let mut ret: Vec<Vec<i32>> = Vec::new();

        for i in 0..nums.len() {
            // If we're at the initial index _or_ we're repeating a number
            // skip it
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            let mut left = i + 1;
            let mut right = nums.len() - 1;

            // For every iteration where the left pointer has not met the right
            while left < right {
                // Calculate the sum
                let sum = nums[i] + nums[left] + nums[right];

                if sum == 0 {
                    ret.push(vec![nums[i], nums[left], nums[right]]);
                    left += 1;

                    while left < right && nums[left] == nums[left - 1] {
                        left += 1;
                    }
                } else if sum > 0 {
                    // Sum is positive
                    right -= 1;
                } else {
                    // Sum is negative
                    left += 1;
                }
            }
        }

        return ret;
    }
}