Binary Search JAVA solution, runtime beats 92.78% of java submissions!


  • 1
    R

    who doesn't love HashMap for this problem? However Binary search is faster even though more lines of code :(

    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] sorted= new int[nums.length];
            System.arraycopy(nums, 0, sorted, 0, nums.length);
            Arrays.sort(sorted);
            
            int left=0;
            int right= nums.length-1;
            
            while(left+1<right){
                if(sorted[left]+sorted[right]<target){
                    left++;
                    continue;
                }
                else if(sorted[left]+sorted[right]>target){
                    right--;
                    continue;
                }
                else{
                    break; //found it! sorted[left]+sorted[right]==target
                }
            }
            //find the index in nums 
            int index1 =-1; 
            int index2= -1; 
            
            for(int i=0; i<sorted.length; i++){
                if(nums[i]==sorted[left] || nums[i]==sorted[right]){
                    if(index1 == -1){
                        index1=i;
                    }
                    else{
                        index2=i;
                    }
                }
            }
            
            //sort the final result
            int [] result= {index1, index2};
            Arrays.sort(result);
            return result; 
            
        }
    }

  • 0
    S

    Nice solution. However, I don't think it is binary search. Rather, it should be two pointers.


  • 0
    X

    I am curious about this solution.

    Theoretically, HashMap runs in O(n), while your solution is in O(nlogn), because of the sorting.


  • 0
    R

    @sampsonchan you're right. Thanks for the correction.


  • 0
    R

    @xCookies yes. but somehow. using two pointer is faster for this problem.


Log in to reply
 

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