2
\$\begingroup\$

I'm looking to learn more about data structures, time complexity, and efficient algorithms. I have solved the Left Rotation Problem on HackerRank using JavaScript. I am looking to see ways to optimize the time complexity. I feel like I have a lot to learn, as don't grok Big O.

function main() {
    const nd = readLine().split(' ')
    const numbers = parseInt(nd[0], 10)
    const rotations = parseInt(nd[1], 10)
    const arr = readLine().split(' ').map(aTemp => parseInt(aTemp, 10))
    const front = arr.slice(0, rotations)
    const back = arr.slice(rotations, numbers)
    const new_arr = back.concat(front)
    console.log(new_arr.join(' '))
}

I feel like this likely has bad time complexity, as under the hood, I believe the slice function uses a loop and has a time complexity of \$O(n)\$. In addition, I'm unsure of how JavaScript implements the merge from the concat method under the hood.

\$\endgroup\$
2
\$\begingroup\$

Review

  • Since you are building the array yourself, as opposed to you get a source array from a consumer of your method, I don't think you should create a new array, but rather just adapt the source array. This way, you could avoid slice and concat altogether.
  • The number of rotations is an integer. However, reading the description behind the link tells use it's clamped between 1 <= rotations <= nd. There is a slight optimization here. If rotations = nd you don't have to do anything, since a rotation is circular. An elegant way to check this is to normalize rotations as rotations = rotations % nd; assuming you have already checked rotations againsts the clamped range. if rotations = 0, don't rotate.
  • There's another optimization if nd < 2, then any rotation is the source itself.
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.