Share Java O(n logn) solution


  • 2

    I saw this solution here a long time ago, for me it's really hard to think of it :)

    public class Solution {
      public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        
        int n = nums.length, len = 1;
        int[] tailTable = new int[n];
        
        tailTable[0] = nums[0];
        
        for (int i = 1; i < n; i++) {
          if (nums[i] < tailTable[0]) {
            // new smallest value
            tailTable[0] = nums[i];
          } else if (nums[i] > tailTable[len - 1]) {
            // nums[i] wants to extend largest subsequence
            tailTable[len++] = nums[i];
          } else {
            // nums[i] wants to be current end candidate of an existing subsequence
            // It will replace ceil value in tailTable
            tailTable[ceilIndex(tailTable, -1, len - 1, nums[i])] = nums[i];
          }
        }
    
        return len;
      }
      
      // binary search helper
      int ceilIndex(int[] tailTable, int lo, int hi, int key) {
        while (hi - lo > 1) {
          int mid = lo + (hi - lo) / 2;
            
          if (tailTable[mid] >= key) {
            hi = mid;
          } else {
            lo = mid;
          }
        }
        
        return hi;
      }
    }
    

  • 0
    A

    @jeantimex
    I like your answers a lot.
    I had trouble understanding this algorithm until I stumbled upon your implementation.
    You are answers are always easy to read.
    Thanks!


Log in to reply
 

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