Three Reverse

Three Reverse

Three reverse is a trick when you want to rotate an array. For example, the original array is [1,2,3,4,5], rotate this array by k=2 will become [4,5,1,2,3]. This problem can be abstracted as: given an array of length n, rotate this array by k.

First Though

One intuitive solution is that we can first create another array of same length as the original array, then loop the original array, calculate the new position of every element, copy the element to new position in new created array. The python program below express such process.

def rotate(nums, k):
    new_arr = nums[:]
    length = len(nums)
    k = k % length
    for i in range(length):
        new_position = (i + k) % length
        new_arr[new_position] = nums[i]

    return new_arr

This method need O(n) space for the new created array and O(n) time for one loop through the original array.

Better One

The time complexity is hard to improve, but we may improve space complexity from O(n) to O(1) using three reverse method.

To rotate an array with length n by k, three reverse method just needs three reverse process.

  • reverse the whole array from index 0 to n-1
  • reverse array from index 0 to k-1
  • reverse array from index k to n-1

Take above array [1,2,3,4,5] with k=2 for example, the first reverse process will output an array [5,4,3,2,1], the second reverse process will output array [4,5,3,2,1], the last reverse process will output array [4,5,1,2,3], which is the rotated array.

Below python program shows this three reverse process:

def rotate(nums, k):
    def reverse(arr, begin, end):
        while begin < end:
            arr[begin], arr[end] = arr[end], arr[begin]
            begin += 1
            end -= 1

    length = len(nums)
    k = k % length
    reverse(nums, 0, length-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, length-1)

    return nums

Three reverse method only use a tmp variable for reverse process, which lead to O(1) space complexity. Cool !~

Currently unrated

Comments

ADDRESS

  • Email: jimmykobe1171@126.com
  • Website: www.catharinegeek.com