Coding Questions - Arrays

This page will collect all the array related questions.

LeetCode 189. Rotate Array

After i tried so many different solutions, i can’t believe the real answer is so simple.

My initial solution with failures:

class Solution(object):
    def rotate(self, nums, k):
        # Swap the last k elements with the first k elements.
        # The last k elements will be in the correct positions
        # but we need to rotate the remaining (n - k) elements
        # to the right by k steps.
        k = k%len(nums)
        def helper(nums, k):
            for i in range(k):
                nums[i], nums[len(nums)-k+i] = nums[len(nums)-k+i], nums[i]
            for i in range(k):
                start = k+i
                end = len(nums)-k+i
                for j in range(end, start, -1):
                    nums[j], nums[j-1] = nums[j-1], nums[j]
        if k < len(nums)/2:
            helper(nums, k)
            nums = nums[len(nums)/2:] + nums[:len(nums)/2]
            for i in range(k-len(nums)/2):
                for j in range(len(nums)-1):
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]

The expected solution:

class Solution(object):
    def rotate(self, nums, k):
        def reverseInPlace(nums, start, end):
            while start<end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        k = k % len(nums)
        reverseInPlace(nums, 0, len(nums)-1)
        reverseInPlace(nums, 0, k-1)
        reverseInPlace(nums, k, len(nums)-1)

Tip: 1. 2 pointers can accelerate the search on a sorted array.