Sharing my O(nlogn) solution


  • 0
    X

    O(N^2) solution:

    //longest increasing subsequence O(nlogn) implementation
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            if (n == 0) return 0;
            //use a val_min, val_min[k] indicates the smallest value with a increasing subsequence k
            vector<int> val_min(1, nums[0]);
            int len = 1;
            
            for (int i = 1; i < n; i++) {
                int curVal = nums[i];
                int k = len;
                for (; k > 0; k--) {
                    if (curVal > val_min[k-1]) break;
                }
                if (k == len) {
                    val_min.push_back(curVal); len++;
                } else {
                    val_min[k] = curVal;
                }
            }
            return len;
        }
    };
    

    Optimize it to O(n*logn) using binary search:

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            if (n == 0) return 0;
            //use a val_min, val_min[k] indicates the smallest value with a increasing subsequence k
            vector<int> val_min(1, nums[0]);
            int len = 1;
            
            for (int i = 1; i < n; i++) {
                int curVal = nums[i];
                int k = binarySearch(1, len, val_min, curVal);
                if (k == len) {
                    val_min.push_back(curVal); len++;
                } else {
                    val_min[k] = curVal;
                }
            }
            return len;
        }
        
        int binarySearch(int begin, int end, vector<int> val_min, int target) {
            if (target > val_min[end-1]) return end;
            if (target <= val_min[begin-1]) return begin - 1;
            int first = begin - 1, last = end - 1;
            while (first <= last) {
                int mid = (first + last) / 2;
                if (val_min[mid] >= target) {
                    last = mid - 1;
                } else {
                    if (val_min[mid] < target && val_min[mid+1] >= target)
                        return mid + 1;
                    first = mid + 1;
                }
            }
            return -1;
        }
    };

Log in to reply
 

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