Java Solution | Binary Search | O(n) time checking | O(n) space | Adds duplicates also | 98.28%


  • 0
    M
    public class TwoSum {
        
        List<Integer> numbers;
    
        /** Initialize your data structure here. */
        public TwoSum() {
            numbers = new ArrayList<Integer>();
        }
        
        /** Add the number to an internal data structure.. */
        public void add(int number) {
            if (numbers.size() == 0) {
                numbers.add(number);
                return;
            }
            
            if (number > numbers.get(numbers.size() - 1)) {
                numbers.add(number);
            } else if (number < numbers.get(0)) {
                numbers.add(0, number);
            } else {
                int idx = Collections.binarySearch(numbers, number);
                if (idx < 0) {
                    numbers.add(-(idx + 1), number);
                } else {
                    numbers.add(idx, number);
                }
            }
        }
        
        /** Find if there exists any pair of numbers which sum is equal to the value. */
        public boolean find(int value) {
            int left = 0, right = numbers.size() - 1;
            
            while (left < right) {
                if (numbers.get(left) + numbers.get(right) > value) {
                    right--;
                } else if (numbers.get(left) + numbers.get(right) < value) {
                    left++;
                } else {
                    return true;
                } 
            }
            
            return false;
        }
    }
    
    /**
     * Your TwoSum object will be instantiated and called as such:
     * TwoSum obj = new TwoSum();
     * obj.add(number);
     * boolean param_2 = obj.find(value);
     */
    

Log in to reply
 

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