Java Code with Full comments and explanation. Very easy to understand.


  • 0
    public class Solution {
        public List<List<Integer>> threeSum(int[] input) {
            
           List<List<Integer>> resultList = new ArrayList<>();
    		
    		if (input == null || input.length == 0) {
    			return resultList;
    		}
    		
    		//First we have to sort the array to make it easy for us.
    		Arrays.sort(input);
    		
    		//The premise here is simple. We first have to pick an element. Then we have to find two other elements in the array
    		//which will be the inverse of our picked element. We can use 2 pointers one from the beginning and other from the end
    		//to achieve this.
    		
    		//The iteration needs to be from 0 to input.length.2 because the start and end pointers will be at the last 2 elements
    		for (int i=0; i<input.length-2; i++) {
    		    //This is the most important condition. so either the iteration should be undergoing its first loop or the next
    		    //element in the iteration must be greater than the previous. If it is the same. Then we will again face a //duplicate entry
    			if (i == 0 || input[i] > input[i-1]) {
    			    //start is one greater than the current element
    				int start = i+1;
    				//end is the last element in the input array.
    				int end = input.length-1;
    				
    				while (start < end) {
    				    //if the sum results in zero.. add it to the resultant arraylist
    					if (input[i]+input[start]+input[end] == 0) {
    						List<Integer> tempList = new ArrayList<>();
    						tempList.add(input[i]);
    						tempList.add(input[start]);
    						tempList.add(input[end]);
    						resultList.add(tempList);
    					}
    					
    					//increment or decrement the counter according to the result obtained.
    					//for eg. if result is greater than zero then end-- if it is less than zero then start++;
    					if (input[i]+input[start]+input[end] < 0) {
    						int currentStart = start;
    						while (input[start] == input[currentStart] && start < end) {
    							start++;
    						}
    					} else {
    						int currentEnd = end;
    						while (input[end] == input[currentEnd] && start < end) {
    							end--;
    						}
    					}
    				}
    			}
    		}
    		
    		//finally return resultList.
    		return resultList;
        }
    }
    

  • 0
    T

    @gokulrama
    Thanks for solution. But its giving time limit exceeded error on submitting..


  • 0

    @TechPrep Hi ,

    Please try this one.. It works for me.

    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            
            List<List<Integer>> result = new ArrayList<>();
            
            if (nums == null || nums.length == 0) {
                return result;
            }
            
            Arrays.sort(nums);
            
            for (int i=0; i<nums.length-2; i++) {
                
                if (i==0 || nums[i] > nums[i-1]) {
                
                    int start = i+1;
                    int end = nums.length-1;
                    
                    while (start < end) {
                        
                        if (nums[i]+nums[start]+nums[end] == 0) {
                            
                            ArrayList<Integer> tempList = new ArrayList<>();
                            tempList.add(nums[i]);
                            tempList.add(nums[start]);
                            tempList.add(nums[end]);
                            result.add(tempList);
                        } 
                        
                        if (nums[i]+nums[start]+nums[end] > 0) {
                            int currEnd = end;
                            while (nums[end] == nums[currEnd] && start < end) {
                                end--;
                            }
                        } else {
                            int currStart = start;
                            while (nums[start] == nums[currStart] && start < end) {
                                start++;
                            }
                        }
                        
                    }
                
                }
                
            }
            
            return result;
        }
    } 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.