3Sum

                                            
class Solution(object):
    def threeSum(self, nums):
        
        res = []
        nums.sort()
        for i in range(len(nums)):
            # nums is **sorted** & all numbers > 0 can NOT sum to 0
            if nums[i] > 0: break
            # avoid duplicates
            if i == 0 or nums[i - 1] != nums[i]: 
                self.sum0(nums, i, res)
        return res
        
    def sum0(slef, nums, i, res):
        # 2 pointers
        sm = i + 1
        lg = len(nums)-1

        while sm < lg:
            # sum 3 numbers; goal is `total = 0`
            total = nums[i] + nums[sm] + nums[lg]
            
            if total < 0:
                ''' 
                    IF ⬇️
                    nums = [ -3, -3, 0, 1, 2, 4 ]
                                  i sm    lg     
                    nums[i] = -3
                    nums[sm] = 0
                    nums[lg] = 2
                    # then `total` is ⬇️
                    total = -1

                    # ℹ️ then we must increase the sm index by one `sm+=1`
                        # Indexes before `sm` are smaller, & our total is smaller. 
                        # We need a larger total. 
                        # Increasing `sm` by 1 ensures all numbers are `>=` to.
                        # Because we sorted the List e.g >>> `nums.sort()`

                    # `sm+=1` we have ⬇️
                    nums = [ -3, -3, 0, 1, 2, 4 ]
                                  i    sm lg  
                    nums[i] = -3
                    nums[sm] = 1
                    nums[lg] = 2
                    # & `total` is ⬇️
                    total = 0
                '''
                sm+=1
            elif total > 0:
                ''' 
                    if ⬇️
                    nums = [ -4, -1, -1, 0, 1, 2 ]
                                  i     sm    lg  
                    nums[i] = -1
                    nums[sm] = 0
                    nums[lg] = 2
                    # & `total` is ⬇️
                    total = 1

                    # then we must decrease the lg index by 1 `lg-=1`
                    # & then we have ⬇️
                    nums = [ -4, -1, -1, 0, 1, 2 ]
                                  i     sm lg 
                    nums[i] = -1
                    nums[sm] = 0
                    nums[lg] = 1
                    # & `total` is ⬇️
                    total = 0
                '''
                lg-=1
            else:
                # `total = 0` so add it to `res`
                res.append([nums[i], nums[sm], nums[lg]])
                # change numbers... 
                sm+=1
                lg-=1
                # avoiding duplicates
                while sm < lg and nums[sm] == nums[sm - 1]: sm+=1

                                            
const threeSum = function(nums, res=[]) {
    nums.sort((a,b) => a - b);
    for(let i = 0; i < nums.length; i++){
        if(nums[i] > 0){
            break;
        } else if(i === 0 || nums[i-1] !== nums[i]){
            sum0(nums, i, res);
        }
    }
    return res;
};

const sum0 = (nums, i, res, sm=i+1, lg=nums.length-1) => {
    while(sm < lg){
        const sum = nums[i] + nums[sm] + nums[lg];
        if(sum < 0){
            sm++;
        } else if(sum > 0) {
            lg--;
        } else {
            res.push([nums[i], nums[sm], nums[lg]]);
            sm++;
            lg--;
            while(nums[sm] === nums[sm-1]){
                sm++;
            }
        }
    }
};

                                            
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size() < 3) {
            return result;
        }
        
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < nums.size() - 2; i++) {
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            
            int target = -nums[i];
            int left = i + 1;
            int right = nums.size() - 1;
            
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum == target) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left+1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right-1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if(sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
};

                                            
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int left = i + 1, right = nums.length - 1, target = -nums[i];
                while (left < right) {
                    if (nums[left] + nums[right] == target) {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        
        return result;
    }
}

                                            
public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        
        for(int i = 0; i < nums.Length - 2; i++){
            if(i == 0 || (i > 0 && nums[i] != nums[i-1])){
                int low = i + 1, high = nums.Length - 1, sum = 0 - nums[i];
                
                while(low < high){
                    if(nums[low] + nums[high] == sum){
                        result.Add(new List<int>{nums[i], nums[low], nums[high]});
                        while(low < high && nums[low] == nums[low+1]) low++;
                        while(low < high && nums[high] == nums[high-1]) high--;
                        low++;
                        high--;
                    } else if(nums[low] + nums[high] < sum){
                        low++;
                    } else {
                        high--;
                    }
                }
            }
        }
        return result;
    }
}

                                            
function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length - 2; i++) {
        if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
            let lo = i + 1;
            let hi = nums.length - 1;
            const sum = 0 - nums[i];
            
            while (lo < hi) {
                if (nums[lo] + nums[hi] === sum) {
                    result.push([nums[i], nums[lo], nums[hi]]);
                    while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
                    while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
                    lo++;
                    hi--;
                } else if (nums[lo] + nums[hi] < sum) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        $result = [];
        sort($nums);
        $n = count($nums);
        
        for ($i = 0; $i < $n - 2; $i++) {
            if ($i == 0 || ($i > 0 && $nums[$i] != $nums[$i - 1])) {
                $lo = $i + 1;
                $hi = $n - 1;
                $sum = 0 - $nums[$i];
                
                while ($lo < $hi) {
                    if ($nums[$lo] + $nums[$hi] == $sum) {
                        $result[] = [$nums[$i], $nums[$lo], $nums[$hi]];
                        while ($lo < $hi && $nums[$lo] == $nums[$lo + 1]) $lo++;
                        while ($lo < $hi && $nums[$hi] == $nums[$hi - 1]) $hi--;
                        $lo++;
                        $hi--;
                    } elseif ($nums[$lo] + $nums[$hi] < $sum) {
                        $lo++;
                    } else {
                        $hi--;
                    }
                }
            }
        }
        
        return $result;
    }
}

                                            
class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        let nums = nums.sorted()
        
        for i in 0..<nums.count {
            if i > 0 && nums[i] == nums[i - 1] {
                continue
            }
            var left = i + 1
            var right = nums.count - 1
            
            while left < right {
                let sum = nums[i] + nums[left] + nums[right]
                if sum == 0 {
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right && nums[left] == nums[left + 1] {
                        left += 1
                    }
                    while left < right && nums[right] == nums[right - 1] {
                        right -= 1
                    }
                    left += 1
                    right -= 1
                } else if sum < 0 {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        nums.sort()
        val result = mutableListOf<List<Int>>()

        for (i in 0 until nums.size - 2) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                var left = i + 1
                var right = nums.size - 1
                val target = 0 - nums[i]

                while (left < right) {
                    when {
                        nums[left] + nums[right] == target -> {
                            result.add(listOf(nums[i], nums[left], nums[right]))
                            while (left < right && nums[left] == nums[left + 1]) left++
                            while (left < right && nums[right] == nums[right - 1]) right--
                            left++
                            right--
                        }
                        nums[left] + nums[right] < target -> left++
                        else -> right--
                    }
                }
            }
        }

        return result
    }
}

                                            
class Solution {
  List<List<int>> threeSum(List<int> nums) {
      List<List<int>> result = [];
      nums.sort();
      for (int i = 0; i < nums.length - 2; i++) {
          if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
              int lo = i + 1;
              int hi = nums.length - 1;
              int sum = 0 - nums[i];
              while (lo < hi) {
                  if (nums[lo] + nums[hi] == sum) {
                      result.add([nums[i], nums[lo], nums[hi]]);
                      while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                      while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                      lo++;
                      hi--;
                  } else if (nums[lo] + nums[hi] < sum) {
                      lo++;
                  } else {
                      hi--;
                  }
              }
          }
      }
      return result;
  }
}

                                            
func threeSum(nums []int) [][]int {
    res := [][]int{}
    
    for i := 0; i < len(nums)-2; i++ {
        for j := i + 1; j < len(nums)-1; j++ {
            for k := j + 1; k < len(nums); k++ {
                if nums[i]+nums[j]+nums[k] == 0 {
                    triplet := []int{nums[i], nums[j], nums[k]}
                    sort.Ints(triplet)
                    found := false
                    for _, v := range res {
                        if reflect.DeepEqual(v, triplet) {
                            found = true
                            break
                        }
                    }
                    if !found {
                        res = append(res, triplet)
                    }
                }
            }
        }
    }
    
    return res
}

                                            
# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
    nums.sort!
    res = []
    (0..nums.length-2).each do |i|
        next if i > 0 && nums[i] == nums[i-1]
        left, right = i+1, nums.length-1
        while left < right
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0
                left += 1
            elsif sum > 0
                right -= 1
            else
                res << [nums[i], nums[left], nums[right]]
                left += 1 while nums[left] == nums[left+1]
                right -= 1 while nums[right] == nums[right-1]
                left += 1
                right -= 1
            end
        end
    end
    return res
end

                                            
impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        
        if nums.len() < 3 {
            return res;
        }
        
        let mut nums = nums;
        nums.sort();

        for i in 0..nums.len() - 2 {
            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 {
                    res.push(vec![nums[i], nums[left], nums[right]]);
                    while left < right && nums[left] == nums[left + 1] {
                        left += 1;
                    }
                    while left < right && nums[right] == nums[right - 1] {
                        right -= 1;
                    }
                    left += 1;
                    right -= 1;
                } else if sum < 0 {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
        
        res
    }
}

To solve this coding challenge, we need to find all unique triplets in the given array that sum up to zero. We will use an efficient two-pointer approach after sorting the array to achieve this. Here's a detailed explanation of how to approach and solve this challenge.

Explanation

Sorting the Array : Begin by sorting the input array. Sorting helps in efficiently locating the triplets using the two-pointer technique.
Iterating through the Array : Iterate through the array with a loop. This loop will fix one element of the triplet, and the subsequent two-pointer technique will find the other two elements of the triplet.
Two-pointer Technique :

For each fixed element, use two pointers to find the other two elements.
One pointer (
left

) starts just after the fixed element, and the other pointer (
right

) starts at the end of the array.
Adjust these pointers based on the sum of the values they point to:

If the sum is less than zero, move the
left

pointer to the right to increase the sum.
If the sum is more than zero, move the
right

pointer to the left to decrease the sum.
If the sum equals zero, store the triplet and then move both pointers inward while skipping duplicate values.

Avoiding Duplicates :

Skip over any duplicate values of the fixed element.
Ensure that the resultant triplets are unique by checking the immediate neighbors for duplicates.

Let's breakdown this approach step by step with pseudocode, including detailed comments to explain each step:

Detailed Steps in Pseudocode

Sort the Array :

                                            
Sort the nums array

Iterate Through the Array :

                                            
Initialize an empty list `result` to store the unique triplets

For each index `i` from 0 to length of nums - 3:
If nums[i] is greater than 0:
Break the loop as further elements cannot sum to zero (since nums is sorted)

If `i` is greater than 0 and nums[i] is equal to nums[i-1]:
Skip to avoid duplicate triplets

Set `left` pointer to i + 1
Set `right` pointer to length of nums - 1

While `left` is less than `right`:
Calculate the `current_sum` as nums[i] + nums[left] + nums[right]

If `current_sum` is less than 0:
Increment `left` by 1

Else If `current_sum` is greater than 0:
Decrement `right` by 1

Else:  # Found a triplet
Append the triplet [nums[i], nums[left], nums[right]] to `result`
Increment `left` by 1 and decrement `right` by 1

# Skip duplicate elements
While `left` is less than `right` and nums[left] equals nums[left - 1]:
Increment `left` by 1
While `right` is greater than `left` and nums[right] equals nums[right + 1]:
Decrement `right` by 1

Return the `result` list

Example with comments in each section

                                            
Sort nums           # Ensures array is sorted
Initialize result   # List to store unique triplets

For i = 0 to len(nums)-3 do
    If nums[i] > 0 then
        Break        # Remaining elements can't sum to zero
        
    If i > 0 and nums[i] == nums[i-1] then
        Continue     # Skip duplicate fixed element

    Set left to i+1
    Set right to len(nums)-1

    While left < right do
        Set current_sum to nums[i] + nums[left] + nums[right]

        If current_sum < 0 then
            Increment left    # Move left pointer to the right to increase sum
        Else if current_sum > 0 then
            Decrement right   # Move right pointer to the left to decrease sum
        Else:
            Append [nums[i], nums[left], nums[right]] to result
            Increment left
            Decrement right
            
            # Skip duplicate elements
            While (left < right and nums[left] == nums[left-1]) do:
                Increment left
            While (right > left and nums[right] == nums[right+1]) do:
                Decrement right

Return result       # List of unique triplets that sum to zero

This detailed explanation and pseudocode guide you through the entire process of solving the challenge, ensuring clarity in understanding how we efficiently find the unique triplets summing to zero.

Search 🔍🌐 Results:

Below 👇 are additional resources found across the 🌐 World Wid Web (WWW) 🥳