Q: LeetCode 189. Rotate Array
I have a working solution for this problem that was accepted in LeetCode:
"Given an array, rotate the array to the right by k steps, where k is non-negative."
function rotate(nums, k) {
for (let i = 1; i <= k; i += 1) {
const poppedNum = nums.pop();
nums.unshift(poppedNum);
}
return nums;
}
// rotate([1, 2, 3, 4, 5, 6, 7], 3) -> [5, 6, 7, 1, 2, 3, 4]
Questions:
Would the time complexity be O(k) and space complexity be O(1)?
Is there a better way to solve this? The question asked to rotate the elements in-place if possible, but I am not sure how to accomplish this at the moment.
javascript algorithm interview-questions
asked 1 hour ago
davidatthepark
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
I have a working solution for this problem that was accepted in LeetCode:
"Given an array, rotate the array to the right by k steps, where k is non-negative."
function rotate(nums, k) {
for (let i = 1; i <= k; i += 1) {
const poppedNum = nums.pop();
nums.unshift(poppedNum);
}
return nums;
}
// rotate([1, 2, 3, 4, 5, 6, 7], 3) -> [5, 6, 7, 1, 2, 3, 4]
Questions:
Would the time complexity be O(k) and space complexity be O(1)?
Is there a better way to solve this? The question asked to rotate the elements in-place if possible, but I am not sure how to accomplish this at the moment.
javascript algorithm interview-questions
asked 1 hour ago
davidatthepark
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
I have a working solution for this problem that was accepted in LeetCode:
"Given an array, rotate the array to the right by k steps, where k is non-negative."
function rotate(nums, k) {
for (let i = 1; i <= k; i += 1) {
const poppedNum = nums.pop();
nums.unshift(poppedNum);
}
return nums;
}
// rotate([1, 2, 3, 4, 5, 6, 7], 3) -> [5, 6, 7, 1, 2, 3, 4]
Questions:
Would the time complexity be O(k) and space complexity be O(1)?
Is there a better way to solve this? The question asked to rotate the elements in-place if possible, but I am not sure how to accomplish this at the moment.
javascript algorithm interview-questions
asked 1 hour ago
davidatthepark
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I have a working solution for this problem that was accepted in LeetCode:
"Given an array, rotate the array to the right by k steps, where k is non-negative."
function rotate(nums, k) {
for (let i = 1; i <= k; i += 1) {
const poppedNum = nums.pop();
nums.unshift(poppedNum);
}
return nums;
}
// rotate([1, 2, 3, 4, 5, 6, 7], 3) -> [5, 6, 7, 1, 2, 3, 4]
Questions:
Would the time complexity be O(k) and space complexity be O(1)?
Is there a better way to solve this? The question asked to rotate the elements in-place if possible, but I am not sure how to accomplish this at the moment.
javascript algorithm interview-questions
javascript algorithm interview-questions
asked 1 hour ago
davidatthepark
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 1 hour ago
davidatthepark
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 1 hour ago
davidatthepark
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 1 hour ago
davidatthepark
1113
asked 1 hour ago
davidatthepark
1113
1113
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
davidatthepark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Review
Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.
Style
Some points on your code.
- The names
numsandkcould be better, maybearrayandrotateBy
- Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line
nums.unshift(nums.pop());
- Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be
for (let i = 0; i < k; i++) {
Complexity
Your complexity is O(n) and storage O(1) where n is the number of rotations, the range of n is > 0
However consider the next examples
rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0
rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1
rotate([1], 8e9); // Will spend a lot of time not changing anything
Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.
You can limit the complexity to O(n) where n <= array.length / 2
Rewrite
This is a slight improvement on your function to ensure you don't rotate more than needed.
function rotate(array, rotateBy) {
rotateBy %= array.length;
if (rotateBy < array.length - rotateBy) {
while (rotateBy--) { array.unshift(array.pop()) }
} else {
rotateBy = array.length - rotateBy;
while (rotateBy--) { array.push(array.shift()) }
}
return array;
}
You could also use Array.splice
array.unshift(...array.splice(-rotateBy,rotateBy));
However under the hood the complexity would be a little greater O(2n) (which is still O(n)) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.
The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage O(n)
If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.
answered 39 mins ago
Blindman67
7,0321521
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
davidatthepark is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210530%2fq-leetcode-189-rotate-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Review
Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.
Style
Some points on your code.
- The names
numsandkcould be better, maybearrayandrotateBy
- Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line
nums.unshift(nums.pop());
- Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be
for (let i = 0; i < k; i++) {
Complexity
Your complexity is O(n) and storage O(1) where n is the number of rotations, the range of n is > 0
However consider the next examples
rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0
rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1
rotate([1], 8e9); // Will spend a lot of time not changing anything
Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.
You can limit the complexity to O(n) where n <= array.length / 2
Rewrite
This is a slight improvement on your function to ensure you don't rotate more than needed.
function rotate(array, rotateBy) {
rotateBy %= array.length;
if (rotateBy < array.length - rotateBy) {
while (rotateBy--) { array.unshift(array.pop()) }
} else {
rotateBy = array.length - rotateBy;
while (rotateBy--) { array.push(array.shift()) }
}
return array;
}
You could also use Array.splice
array.unshift(...array.splice(-rotateBy,rotateBy));
However under the hood the complexity would be a little greater O(2n) (which is still O(n)) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.
The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage O(n)
If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.
answered 39 mins ago
Blindman67
7,0321521
add a comment |
Review
Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.
Style
Some points on your code.
- The names
numsandkcould be better, maybearrayandrotateBy
- Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line
nums.unshift(nums.pop());
- Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be
for (let i = 0; i < k; i++) {
Complexity
Your complexity is O(n) and storage O(1) where n is the number of rotations, the range of n is > 0
However consider the next examples
rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0
rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1
rotate([1], 8e9); // Will spend a lot of time not changing anything
Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.
You can limit the complexity to O(n) where n <= array.length / 2
Rewrite
This is a slight improvement on your function to ensure you don't rotate more than needed.
function rotate(array, rotateBy) {
rotateBy %= array.length;
if (rotateBy < array.length - rotateBy) {
while (rotateBy--) { array.unshift(array.pop()) }
} else {
rotateBy = array.length - rotateBy;
while (rotateBy--) { array.push(array.shift()) }
}
return array;
}
You could also use Array.splice
array.unshift(...array.splice(-rotateBy,rotateBy));
However under the hood the complexity would be a little greater O(2n) (which is still O(n)) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.
The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage O(n)
If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.
answered 39 mins ago
Blindman67
7,0321521
add a comment |
Review
Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.
Style
Some points on your code.
- The names
numsandkcould be better, maybearrayandrotateBy
- Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line
nums.unshift(nums.pop());
- Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be
for (let i = 0; i < k; i++) {
Complexity
Your complexity is O(n) and storage O(1) where n is the number of rotations, the range of n is > 0
However consider the next examples
rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0
rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1
rotate([1], 8e9); // Will spend a lot of time not changing anything
Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.
You can limit the complexity to O(n) where n <= array.length / 2
Rewrite
This is a slight improvement on your function to ensure you don't rotate more than needed.
function rotate(array, rotateBy) {
rotateBy %= array.length;
if (rotateBy < array.length - rotateBy) {
while (rotateBy--) { array.unshift(array.pop()) }
} else {
rotateBy = array.length - rotateBy;
while (rotateBy--) { array.push(array.shift()) }
}
return array;
}
You could also use Array.splice
array.unshift(...array.splice(-rotateBy,rotateBy));
However under the hood the complexity would be a little greater O(2n) (which is still O(n)) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.
The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage O(n)
If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.
answered 39 mins ago
Blindman67
7,0321521
Review
Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.
Style
Some points on your code.
- The names
numsandkcould be better, maybearrayandrotateBy
- Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line
nums.unshift(nums.pop());
- Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be
for (let i = 0; i < k; i++) {
Complexity
Your complexity is O(n) and storage O(1) where n is the number of rotations, the range of n is > 0
However consider the next examples
rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0
rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1
rotate([1], 8e9); // Will spend a lot of time not changing anything
Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.
You can limit the complexity to O(n) where n <= array.length / 2
Rewrite
This is a slight improvement on your function to ensure you don't rotate more than needed.
function rotate(array, rotateBy) {
rotateBy %= array.length;
if (rotateBy < array.length - rotateBy) {
while (rotateBy--) { array.unshift(array.pop()) }
} else {
rotateBy = array.length - rotateBy;
while (rotateBy--) { array.push(array.shift()) }
}
return array;
}
You could also use Array.splice
array.unshift(...array.splice(-rotateBy,rotateBy));
However under the hood the complexity would be a little greater O(2n) (which is still O(n)) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.
The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage O(n)
If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.
answered 39 mins ago
Blindman67
7,0321521
edited 3 mins ago
answered 39 mins ago
Blindman67
7,0321521
answered 39 mins ago
Blindman67
7,0321521
answered 39 mins ago
Blindman67
7,0321521
7,0321521
add a comment |
add a comment |
davidatthepark is a new contributor. Be nice, and check out our Code of Conduct.
davidatthepark is a new contributor. Be nice, and check out our Code of Conduct.
davidatthepark is a new contributor. Be nice, and check out our Code of Conduct.
davidatthepark is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210530%2fq-leetcode-189-rotate-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
