We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Obviously this solves the problem, but is a terrible solution. Pop is an O(N) operation. So your solution becomes O(K*N). This should be done in O(N) total time complexity. You do have the space requirement of O(1) correct. All the standard solutions have a O(N) space complexity.
True. However, it becomes an elegant solution if we use collections.dequeue instead of list. Double ended queues have a popleft method, which is an O(1) operation:
And array_left_rotation only takes O(k) instead of O(n).
Note that a is pased by reference, so there is no need to return anything, but this could be an issue for some user cases, for this particular problem, it works.
Yes both qzangs and my answer is correct. In python index slicing (indices[start:stop:step]), works like so...
We will begin with the index specified at start and traverse to the next index by our step amount (i.e. if step = 2, then we jump over every other element, if step = 3, we jump over 2 elements at a time). If step is not specified it is defaulted to 1. We continue steping from our start point until we come to or exeed our stop point. We do NOT get the stop point, it simply represents the point at which we stop.
This won't work if the number of rotations is greater than the length of the array.
The test cases must have all had d < n I guess
This is a modification that I did so it satisfies the above case too.
Arrays: Left Rotation
You are viewing a single comment's thread. Return to all comments →
Python 3
It is way easier if you choose python since you can play with indices.
Yeah index slicing FTW, here was my 1-liner in definition, lol:
is that scala?
It's Python 3
you dont need to pass n to your function, right..
I agree - I ended up not using 'n' (Python):
Obviously this solves the problem, but is a terrible solution. Pop is an O(N) operation. So your solution becomes O(K*N). This should be done in O(N) total time complexity. You do have the space requirement of O(1) correct. All the standard solutions have a O(N) space complexity.
True. However, it becomes an elegant solution if we use collections.dequeue instead of list. Double ended queues have a popleft method, which is an O(1) operation:
More info: https://wiki.python.org/moin/TimeComplexity#collections.deque https://docs.python.org/3/library/collections.html#collections.deque
They have rotate built into the deque
You have O(n) in:
In order to avoid this, you should use a deque from the beginning like:
And array_left_rotation only takes O(k) instead of O(n).
Note that a is pased by reference, so there is no need to return anything, but this could be an issue for some user cases, for this particular problem, it works.
i'd change '''for _ in range(k%len(a)) ''' to be more eficent
def array_left_rotation(a, n, k): return (a[k:] + a[:k])
k -> k%nk%n handles any range of shifts, but the problem specifies n < k so you can just use k in this case
This logic fails when k>n.
for that, do:
Nice, only one line was added
Perfection. Short, simple, & clean.
hmm nice....
It's so smart! well done:)
Can you please explain how (a[k:]+a[:k]) is working?
Damn this is super impressive.
Pretty smart, but are you sure you are not copying the
kth eleement, in ruby it would be:In ruby,
...means excluding the right number.Yes both qzangs and my answer is correct. In python index slicing (indices[start:stop:step]), works like so...
We will begin with the index specified at start and traverse to the next index by our step amount (i.e. if step = 2, then we jump over every other element, if step = 3, we jump over 2 elements at a time). If step is not specified it is defaulted to 1. We continue steping from our start point until we come to or exeed our stop point. We do NOT get the stop point, it simply represents the point at which we stop.
I love Python :)
Ok, so it's exclusive by default in Python, interesting.
Haha that's what I did, got to love Python !
@qzhang63 isnt a already a list when it is passed? why convert it to a list a second time?
thanks. makes more sense
Thanks ....... Its working and simple to learn
I think 'k' should be allowed to be greater than 'n'':
What about if 'k' is greater than 'n'? You should use modular arithmetic to get actual rotate count.
Then your solution would work for every k values.
This won't work if the number of rotations is greater than the length of the array. The test cases must have all had d < n I guess This is a modification that I did so it satisfies the above case too.
return a[k:] + a[:k]
Great answer, you just need %size_of_list for cases the k is greater than the size of the list
where did the k parameter come from?
This is a very good answer. But if the constraint k
Same goes for Golang
func rotLeft(a []int32, d int32) []int32 {
}