Binary search + Two pointers ?


  • 0
    N

    Hi, In leetcode clean code handbook, it provided a solution :

    add – O(log n) runtime, find – O(n) runtime, O(n) space – Binary search + Two
    pointers:
    Maintain a sorted array of numbers. Each add operation would need O(log n) time to
    insert it at the correct position using a modified binary search (See Question [48. Search
    Insert Position]). For find operation we could then apply the [Two pointers] approach in
    O(n) runtime.

    I am not clear about add operation runtime. I know to find the inserted position is O(lgn)
    However for maintain a sorted array seems still O(n).As we need to shift all bigger value.

    So am I right or wrong about this ?

    Thanks


Log in to reply
 

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