Three sum

This post is to recap and organize some thoughts on algorimthic operations

Problem

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.

Step-by-step approach

1) Sorting

First of all, we want to make sure that there is no duplicate of triplet. How can we achieve? In one way or another, we are to take three elements and get the same of it when each index is different.
Sorting can help in this situation because it not only sorts the values but also streamlines duplicate checking - I will get back to this shortly.

So, the first line will be:

pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        todo!()
}

2) skipping duplicate

Now, let's loop over the vector using index. Why index? it's because we need pointers to save number of instruction and have more flexibility.

And then the very first logic we want to add is skip-over logic for duplicate triplet

    for i in 0..nums.len() {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            //

What does this do? Rememeber we started with sorting vector. Now, when values are sorted out, if num[i] is the same as num[i-1], then any triplets starting with nums[1] will already have been considered in the previous iteration except when i == 0, therefore additional i>0.

For example, given input nums = [-1,-1,0,1,2],

• When i = 0, nums[i] = -1. The algorithm processes this value.
• When i = 1, nums[i] = -1 (same as nums[i - 1]), so the continue statement skips this iteration, avoiding duplicate triplets starting with -1.

3) two pointer after i

Right now, the situation we are in is:

• vector is sorted.
• Inside for loop,
  • we are not processing duplicate triplet
  • i increases all the way until the last index

Now, i is set and I'm going to take two pointers that follows i.

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

So the given nums[i] being fixed, we try to find the values, sum of which becomes zero as follows:

   while left < right {
       let sum = nums[i] + nums[left] + nums[right];
       if sum > 0 {
           right -= 1;
           } else if sum < 0 {
               left += 1
           } else {
               res.push(vec![nums[i], nums[left], nums[right]]);
               left += 1;
               while nums[left] == nums[left - 1] && left < right {
                   left += 1;
                    }
                }
            }

Solution

pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let mut res = Vec::new();
     
        for i in 0..nums.len() {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

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

            while left < right {
                let sum = nums[i] + nums[left] + nums[right];
                if sum > 0 {
                    right -= 1;
                } else if sum < 0 {
                    left += 1
                } else {
                    res.push(vec![nums[i], nums[left], nums[right]]);
                    left += 1;

                    while nums[left] == nums[left - 1] && left < right {
                        left += 1;
                    }
                }
            }
        }

        return res;
    }