3 Line C++ Solution, O(1) space


  • 1
    A
     void rotate(vector<int>& nums, int k) 
        {
            for(int i=0;i<k;i++)
            {
                nums.insert(nums.begin(), nums.back());
                nums.pop_back();
            }
        }

  • 0
    A

    Are you sure the insertion into the beginning of the vector is O(1) space? I am not that good with C++ but doesn't front insertion require reallocation of the memory? According to C++ reference vector::insert has a logarithmic complexity in size (i.e. the size is increased by 1.5 for best performance).


  • 0
    A

    I think what they mean by constant size is, irrespective of the number of elements, you're using only constant extra space to run your logic. Programming language-wise, each language has a different complexity and runtime associated with each operation. For example, if I used the same logic in C, it would use lesser space but more time.
    However, here, I think the focus is on the logic (where I'm using only constant extra space of 1 additional cell) as opposed to the specific programming language implementation.


  • 0
    A

    Hmm.. I see your point. Though it's kind of like saying that "sort() has O(1) space complexity because in the end you have the same size array but sorted", or "getting the bottom element of a stack is O(1) because you only get 1 element". I think that it's important to know what the space complexity of the underlying operation of a specific data structure is in order to reason about it logically (e.g. removing the bottom element of a stack is O(n) space but O(1) for a doubly-linked list). I'd like others' input on this. Maybe I am just overthinking terribly, I'll upvote it back if see more arguments against me :)

    On the second though, if I think of the vector as a queue, then it is indeed O(1) space, but the question is should I think of it as a queue or should I take it for what it is? My point is that this is a very elegant solution, but it doesn't use the right data structure to make the claim that it's O(1) space. Using better data structure would make it less elegant, so it should be a trade-off.


  • 0
    A

    Well maybe my understanding is wrong, but I've always been under the impression that a sort that doesn't require any extra data structure (eg: simple linear sort) is O(1) space. Merge sort for instance, requires extra allocation for each iteration, and hence would not be O(1) space.
    A better data structure could be used (as you suggested, a queue would work wonders) but in this case, that would mean reallocating the entire vector to a new space, which would mean a space complexity of O(n). So given a vector as input, the operations possible on a vector, and the constraints imposed by the question, I felt this solution worked. I also assumed that they aren't very programming-language specific and focus more on how much space and time the pseudo-code would take. But it's a good reflection :)
    I'm


Log in to reply
 

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