My simple O(N) idea


  • 2

    Scan from start to end, then check if

    • s[i]>s[i+1], delete s[i];
    • s[i]<=s[i+1], don't delete s[i] continue;

    If we still need to delete, delete from the end.

    Total: O(N).

    Correctness: we only delete if there is "descending". The reason is, if there is an "ascending", say s[i]<=s[i+1], and we delete s[i], then since s[i+1]>s[i], the result can't be the minimal.


  • 0
    C

    I think you need to to this K pass so it should be O(N * K)?


  • 0

    This idea is the same as my solution https://discuss.leetcode.com/topic/59327/o-n-solution/2
    And it is O(n + k) = O(n) (if you can remove a letter in O(1)) as it only does 1 pass with at most k returns to previous letter.


  • 0
    C

    @dettier Yes, you're right, the point is that we only need to return to previous letter after removing a letter, instead of start from the beginning again. Good solution.


Log in to reply
 

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