Monday, May 27, 2024
HomeProgramming3 Sum | Leetcode #15 | 100 Days of Code Day 10

3 Sum | Leetcode #15 | 100 Days of Code Day 10

-

Today we are going to solve 3 Sum – our first Medium Level Array problem from Coderefer DSA Sheet. If you are new to this blog, here’s the link for the same:

https://www.coderefer.com/blog/coderefer-dsa-sheet/

Problem Statement

Now let us understand the problem statement. You can read from the below link but here’s the brief: Given an Integer Array, you need to find all the triplets with different indices but if added should return zero.

https://leetcode.com/problems/3sum/description/

Solution

Now let us understand the solution. Here we need to keep two things in mind.

  1. Can we convert 3 Sum to 2 Sum? We know that nums[i] + nums[j] + nums[k] should be 0. But what if we take one value to the right of (=)? This becomes nums[i] + nums[j] = -nums[k]. If you closely look, it becomes a 2 Sum problem where the sum of 2 numbers must be equal to a target number (here it is -nums[k]). Hence we were able to convert 3 sum to 2 sum
  2. To avoid duplicate triplets. This can be done by skipping the processing of duplicate values. How can we do this? By sorting the array to make the duplicate values fall adjacent so that we can skip after processing first among them.

Now by keeping these two things in mind, let us solve the code. The code is commented wherever necessary. If you feel stuck anywhere, feel free to comment below so I can guide you.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> sol = new ArrayList<>();
        // To sort the values as we will consider skipping them if same, to avoid duplicates
        Arrays.sort(nums);
        for(int i = 0; i< nums.length-2; i++) {
            if(nums[i] > 0) {
                break;
            }
            if(i>0 && nums[i] == nums[i-1]) {
                // comparing with previous. If both are same, 
                // then skip to avoid duplicate triplets
                continue;
            }
            Set<Integer> set = new HashSet<>(); // set because it can retreive in O(1)
            int target = -nums[i];
            for(int j = i+1; j < nums.length; j++) {
                int rem = target - nums[j];
                if(set.contains(rem)) { // here we are retrieving from set in O(1)
                    // we found our triplet. Hence adding to the sol
                    sol.add(Arrays.asList(nums[i], nums[j], rem));
                    if(j< nums.length-1 && nums[j] == nums[j+1]) {
                        // skipping duplicate values while considering for triplets
                        j++;
                    }
                } else {
                    set.add(nums[j]);
                }
            }
        }
        return sol;
    }
}

Time & Space Complexities

Here the time complexity is O(N^2) as we are iterating through the array twice using nested for loops.

Space complexity of using HashSet is O(N) and List of List is O(N^2). Hence the total Space Complexity is O(N) + O(N^2) ~= O(N^2).

Vamsi Tallapudi
Vamsi Tallapudi
Architect Technology at Cognizant | Full Stack Engineer | Technical Blogger | AI Enthusiast

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.

LATEST POSTS

Best Time to Buy and Sell Stock – Day 7 | 100 Days of Code

Welcome to Day 7 of 100 Days of Code where today we solve yet another most frequently asked easy array problem called - Best Time...

Contains Duplicate – Day 8 | 100 Days of Code

Welcome to Day 8 of 100 Days of Code and today we are going to solve yet another easy-level problem - Contains Duplicate as part...

Two Sum – Day 6 | 100 Days of Code

Welcome to Day 6 of 100 Days of Code where we solve the most frequently asked Easy level Array problem - Two Sum. Let us...

Embarking on a 100-day adventure: Day 5 – No.Of Occurrences In An Array

Welcome to Day 5 of our coding journey! Today, we dive deep into the world of programming to tackle a common, yet curious problem: finding...

Follow us

1,358FansLike
10FollowersFollow
398SubscribersSubscribe

Most Popular