Three sum closest

The 3Sum Closest 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 of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

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

	
		
			
			
		
	

	Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Since we just did the 3 sum problem in our last problem, we can take a similar approach. The difference here is that we’re not returning the array of numbers, but we’re returning the closest sum.

I’ll be writing this in rust, but the solution translates to other languages pretty straightforward-ly… that’s a word, right?

The initial setup they give us is:

	
		
			
			
		
	

	impl Solution {
    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
        // Input solution here
    }
}

With this in mind, let’s talk strategy. Overall, we’ll need to iterate through the problem for every loop, so the Big-O scenario is we’ll have a O(n^2). First thoughts here are thinking 2-pointers where we’ll keep not of the best difference as we iterate through the numbers. If the number is found, we can just return the target because the target is in the list. If it’s less-than, we can move the left pointer forward otherwise the right.

Let’s see this in code. See the detailed comments for solutioning thoughts:

	
		
			
			
		
	

	impl Solution {
    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
        // sort the array so we can iterate forward
        let mut sorted = nums.clone();
        sorted.sort();
        // initially start out with a super high number (infinity)
        let mut closest = i32::MAX;

        // for every number, set an index for iterating through the numbers
        // this allows us to use a 2-pointer solution
        for (curr, num) in sorted.iter().enumerate() {
            // the left pointer is the next value
            let mut left = curr + 1;
            // right is the last possible value
            let mut right = sorted.len() - 1;

            // keeping a previous difference allows us to check if we're closer to
            // the target at every iteration
            let previous_diff = sorted[curr] - target;
            // loop for each pointer
            while left < right {
                // Get the current difference
                let curr_diff: i32 = previous_diff + sorted[left] + sorted[right];
                // if the current difference is closer than the initial target
                // set the closest to the current difference
                if curr_diff.abs() < closest.abs() {
                    closest = curr_diff;
                }
                // match on the number, if it's positive, move the right pointer
                // left, if it's negative, move the left pointer forward
                // if it's zero, we can kill the entire process early
                match curr_diff.signum() {
                    1 => right -= 1,
                    -1 => left += 1,
                    0 => return target,
                    _ => unreachable!(),
                }
            }
        }

        // The closest difference will be the sum of the target
        // and the closest possible value
        return target + closest;
    }
}

As always, check out the solutions for all of these problems at https://github.com/auser/leetcode.