LeetCode Challenge: 15. 3Sum - JavaScript Solution 🚀

Top Interview 150

The 3Sum problem is a classic interview challenge that combines sorting, two-pointer techniques, and efficient duplicate handling. Let’s break it down and solve it step-by-step.

---

📝 Problem Overview:

You’re given an integer array nums and need to find all unique triplets [nums[i], nums[j], nums[k]] such that:

where 𝑖 ≠ 𝑗 ≠ 𝑘

Important Notes:

• The output must not contain duplicate triplets.
• The order of triplets and elements within triplets doesn’t matter.

---

🌟 Key Concepts:

• Sorting: Sorting the array simplifies duplicate handling and enables the two-pointer technique.
• Two-Pointer Technique: For each element in the array, use two pointers to find pairs that sum up to the target.
• Duplicate Handling: Avoid duplicate triplets by skipping over consecutive duplicate values.

---

Approach 🚦

1. Sort the Array: Sorting helps identify duplicates and makes the two-pointer approach efficient.
2. Iterate Through the Array: For each element nums[i], treat it as a potential first element of a triplet.

3. Two-Pointer Search:

   • Use two pointers (left and right) to find pairs that sum up to -nums[i].
   • Adjust pointers based on whether the sum is less than, greater than, or equal to the target.

4. Skip Duplicates: Ensure unique triplets by skipping over duplicate elements.

---

JavaScript Implementation 👨‍💻

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum === 0) {
                result.push([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 < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
};

---

📊 Complexity Analysis:

1. Time Complexity:

   • Sorting the array takes O(nlogn).
   • The two-pointer search for each element takes O(n).
   • Overall: 𝑂(𝑛2), as the two-pointer search runs for each element.

2. Space Complexity:

   • O(1), as we use no extra space apart from the output list.

---

✨ Examples:

Example 1:

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

Explanation:

• The triplets [-1, -1, 2] and [-1, 0, 1] sum to 0.
• Duplicates are avoided.

Example 2:

Input: nums = [0, 1, 1]
Output: []

Explanation:

• No three numbers sum to 0.

Example 3:

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

Explanation:

• Only one triplet [0, 0, 0] is valid.

---

Dry Run 🧐

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

1. Step 1: Sort the Array

   • Sorted Array: [-4, -1, -1, 0, 1, 2]

2. Step 2: Process Each Element
   

Output:

Unique Triplets Found:

---

✨ Pro Tips for Interviews:

1. Understand the Problem Thoroughly

   • Before writing any code, ensure you understand the input, output, and constraints clearly. For problems like 3Sum, identifying the need for efficient solutions is critical due to the size of inputs.

2. Explain Your Thought Process

   • Walk the interviewer through your solution: Why did you sort the array? Why use two pointers? Demonstrating a clear thought process matters as much as writing the correct code.

3. Optimize Gradually

   • Mention brute-force solutions first (e.g., three nested loops for 3Sum) and explain why they are inefficient. Then propose the optimal approach (sorting + two-pointer).

4. Handle Edge Cases

   • Test cases with empty arrays, arrays with all zeros, or duplicate numbers can reveal if your code handles edge scenarios effectively. Always discuss edge cases during your explanation.

5. Avoid Duplication

   • For 3Sum, explicitly mention how you plan to skip duplicate numbers to avoid redundant triplets. This is often a point of focus in interviews.

6. Time and Space Complexity

   • Highlight the time complexity of the approach. For 3Sum, sorting takes O(nlogn), and the two-pointer approach is O(n2). Total complexity: O(n2).

7. Write Clean, Modular Code

   • Use functions to make the code readable. For example, extracting the logic for finding triplets into its own function can demonstrate good coding practices.

8. Ask Questions if Stuck

   • If you're unsure about specific constraints or test cases, ask the interviewer. It shows you're methodical.

---

📚 Learn More Final Thoughts 💡:

1. Deep Dive Into Two-Pointer Techniques:

   • 3Sum is a great example of how two-pointer techniques can reduce complexity. Mastering this approach will help with related problems like 4Sum, Container With Most Water, and more.

2. Practice Common Variations:

   • 2Sum, 3Sum Closest, and KSum are all variations of this problem. Familiarity with these ensures you're prepared for most sum-related problems.

3. Leverage Sorting:

   • Sorting simplifies many array problems. Recognize patterns where sorting helps reduce the problem's complexity.

4. Coding Platforms to Practice:

   • Explore problems on LeetCode, HackerRank, or Codeforces. Focus on the Array and Two-Pointer tags for structured learning.

5. Join Mock Interviews:

   • Practice explaining solutions under timed conditions. Platforms like Pramp or interviewing.io provide mock interviews with feedback.

6. Reflect on Post-Interview:

   • After every interview, revisit the problems and your solutions. Analyze what went well and what could improve.

---

---

By mastering the core concepts, communicating effectively, and practicing regularly, you'll not only solve problems like 3Sum but also stand out in technical interviews. Good luck—you’ve got this! 🚀

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!