My accepted O(n^3) solution without extra space or duplicate deletion (Comments included)


  • 0
    T
    public static List<List<Integer>> fourSum(int[] num, int target) {
    		 Arrays.sort(num);
    		 List<List<Integer>> quadrapules= new ArrayList<List<Integer>>();
    		 int arraylen = num.length;
    		 if(arraylen < 4) 
    			 return quadrapules;
    		 // Enumerate every possible (i,j) until arraylen-4.
    		 // Because we are looking for quadruples
    		 for(int i = 0; i <= arraylen-4; i++){
    			 if(i > 0 && num[i] == num [i-1]) // Avoid i, if it is same as previous iteration
    				 continue;
    			 for(int j=i+1; j <= arraylen-3; j++){
    				 if(j > i+1 && num[j] == num[j-1]) // avoid j, if it same as previous iteration
    					 continue;
    				 int newTarget = target - (num[i]+num[j]); 
    				 int l = j+1, r = arraylen - 1; //Now l and r denote the array boundaries of a 2sum problem
    				 while(r > l){
    					 if((r < arraylen - 1) && num[r] == num[r+1]){ //To avoid duplicates
    						 r--;
    						 continue;
    					 }
    					 if(l > (j+1) && num[l] == num[l-1]){ //To avoid duplicates
    						 l++;
    						 continue;
    					 }
    						 
    					 int twoSum = num[l] + num[r];
    					 if(twoSum > newTarget)
    						 r--;
    					 else if(twoSum < newTarget)
    						 l++;
    					 else{
    						 ArrayList<Integer> quad = new ArrayList<Integer>();
    						 quad.add(num[i]);quad.add(num[j]);quad.add(num[l]);quad.add(num[r]);
    						 quadrapules.add(quad);
    						 l++;r--;
    					 }
    				 }
    			 }	
    		 }
    		 return quadrapules;        
    	}

Log in to reply
 

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