3 Sum Leetcode Solution

3 Sum Leetcode 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.

3 Sum Leetcode Solution :

Constraints :

  • 3<=nums.length<=3000
  • -10^5<=nums[i]<=10^5

Example 1:

Input: nums=[0,1,1]

Output: [ ]

Example 2:

Input: nums = [0,0,0]

Output: [[0,0,0]]

In the “3 sum” problem you are given an integer array nums, the goal is to find all  unique triplets within the array such that the sum of the elements in each triplet is equal to zero (i.e.,nums[i] + nums[j] + nums[k] == 0), and the indices i, j, and k are all distinct (i.e., i != j, i != k, and j != k). 

Here are the key points for the given constraints and examples:

  • Constraints:

    • The length of the nums array is between 3 and 3000.
    • The values in the nums array can range from -100,000 to 100,000.

Approach :

For Solving 3 sum sum Leetcode Problem we can use following procedure :

To solve the problem of finding all unique triplets in an integer array nums such that the sum of the elements in each triplet is equal to zero (i.e., nums[i] + nums[j] + nums[k] == 0), you can use a modified version of the “3Sum” algorithm. Here’s the approach:

  • Sort the Array: Start by sorting the input array nums in non-decreasing order. Sorting the array will help simplify the problem and allow for an efficient solution.
  • Iterate Through the Array: Iterate through the sorted array using a loop. For each element at index i, consider it as a potential first element of the triplet.
  • Use Two-Pointers Approach: Inside the loop, use a two-pointers approach to find the other two elements that, when combined with nums[i], sum to zero. Initialize two pointers, left and right, where left points to the element just after nums[i], and right points to the last element in the array.
  • Check the Sum:
    • Calculate the sum of the current triplet, i.e., nums[i] + nums[left] + nums[right].
    • If the sum is equal to zero, you’ve found a valid triplet.
    • Add it to the result.
    • If the sum is less than zero, increment the left pointer to move towards larger values.
    • If the sum is greater than zero, decrement the right pointer to move towards smaller values.
  • Avoid Duplicates: To avoid duplicate triplets in the result, ensure that you skip duplicate elements for nums[i], nums[left], and nums[right]. When you find a valid triplet or adjust the pointers, make sure to check for duplicates and skip them.
  • Continue Iterating: Continue this process until the i index reaches the third-to-last element in the array. This ensures that you’ve considered all possible first elements of the triplet.
  • Return the Result: After completing the loop, return the list of unique triplets that sum to zero.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription