15. 3Sum

 

Finding All Unique Triplets in an Array with Zero Sum

Problem Description

Given an integer array nums, our goal is to return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Intuition

To solve this problem, we need to find triplets in the array that sum up to zero. By sorting the array first, we can efficiently find these triplets using a two-pointer technique. Sorting the array also helps us easily skip duplicate elements and manage indices better.

Approach

  1. Initial Check: If the array has fewer than 3 elements, return an empty list as no triplet can be formed.

  2. Sorting: Sort the array in non-decreasing order, which helps in managing duplicates and using the two-pointer approach.

  3. Iterate and Find Triplets:

    • Use a for-loop to iterate through the array, treating each element as the potential start of a triplet.

    • For each element, use two pointers (startIndex and endIndex) to find pairs that, along with the current element, sum up to zero.

    • Skip duplicate elements to ensure unique triplets.

  4. Two-Pointer Technique:

    • Initialize two pointers: startIndex just after the current element and endIndex at the end of the array.

    • Calculate the total sum of the triplet.

    • If the sum is zero, store the triplet in the results list.

    • If the sum is less than zero, increment the startIndex to increase the sum.

    • If the sum is greater than zero, decrement the endIndex to decrease the sum.

    • Continue this process until the pointers meet.

  5. Result: Return the list of unique triplets.

Complexity Analysis

  • Time Complexity: The time complexity is O(n^2) because sorting the array takes O(n log n) and the nested loop runs in O(n^2).

  • Space Complexity: The space complexity is O(1) for the input array and O(k) for the output list of triplets, where k is the number of triplets found.

LeetCode Solution

Check out my .

Code

javascript
function threeSum(nums) {
    let results = [];
    //check the size
    if(nums.length < 3) {
        return results;
    }
    // sort the array
    nums.sort((a,b) => a - b);
    // find the first value
    for(let i = 0; i < nums.length -2; i++) {
        // skip duplicates
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let startIndex = i + 1;
        let endIndex = nums.length - 1;
        while(startIndex < endIndex) {
            let total = nums[i] + nums[startIndex] + nums[endIndex];
            if(0 === total) {
                results.push([nums[i],nums[startIndex],nums[endIndex]]);
                // skip duplicates
                while(nums[startIndex] === nums[startIndex + 1]){
                    startIndex++;
                }
                while(nums[endIndex] === nums[endIndex - 1]) {
                    endIndex--;
                }
                // final updation
                startIndex++;
                endIndex--;
            }else if(total < 0) {
                startIndex++;
            }else{
                endIndex--;
            }
        }
    }
    return results;
}

I hope you find this guide helpful for understanding and implementing the threeSum function. Feel free to share your thoughts or ask any questions! šŸ˜Š

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement 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. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more