Gained 1ms by implementing my own binary search 2ms runtime; compared to my 30ms n^2 algo


  • 0
    M
    public class Solution {
        public int lengthOfLIS(int[] nums) {
          int[] arr = new int[nums.length];
          int len = 0;
          for(int x : nums) {
              int id = binarySearch(arr, 0, len, x);
              if(id < 0) id = -(id);
              arr[id] = x;
              if(id == len) len++;
          }
          return len;
            
        }
        
        public int binarySearch(int[] arr, int start, int end, int key) {
            end = end-1;
            while(start <= end) {
                int mid = (start + end)/2;
                if(arr[mid] == key) return mid;
                if(arr[mid] > key ) end= mid-1;
                else start = mid + 1;
            }
            
            return -(start);
        }
    }

Log in to reply
 

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