4ms C++ solution, O(nlgn) time complexity, using binary search


  • 1
    I
    int binary_search(vector<int>& vec, int target) {
        int low = 0, high = vec.size() - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (target > vec[mid]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (low == (int)vec.size() - 1 && vec[low] < target) low++;
        return low;
    }
    
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for (int i : nums) {
            int idx = binary_search(dp, i);
            if (idx > (int)dp.size() - 1) {
                dp.push_back(i);
            } else {
                dp[idx] = i;
            }
        }
        return dp.size();
    }

  • 0
    M

    Hi man,

    I appreciate your comment and correction!

    You are a bit rude right there though! Why couldn't I tease you on the fact that your code needs extra O(N) space in the worst case. Not to mention that dp could allocate memory on the fly.

    Should I vote it down here as you just did? Probably not.

    Yours,


  • 0
    I

    It could be an improvement to overwrite nums instead of allocating extra memory. On this problem, you're right. I'm considering what if we need to get the longest sequence instead of the length. Then we cannot overwrite 'nums'.
    I vote up for good answers and vote down for bad ones. I feel sorry if that offended you. I would 't mind receving a vote down if it's really awful. I can learn from it. And I would learn it by heart and avoid programming or making mistakes like that.


  • 0
    M

    Thanks!

    If you said so, could you go back to my thread and help me test if the "overwritten" nums does catches the LIS up to maxlen?

    Let me know if you see any odd again...


  • 0
    I

    What do you mean?


Log in to reply
 

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