Tag Archives: constant space

Rotate an Array

Posted on by

Given an array of integers. Rotate the array by k position to right (or left).

For example, given array A=[1,2,3,4,5,6] then rotateRight(A, 2) will return [5, 6, 1, 2, 3, 4] and rotateLeft(A,2) will return [3, 4, 5, 6, 1, 2]. Also, otateRight(A, 8) will return [5, 6, 1, 2, 3, 4] because after k=length of array(=6) the rotated array will be same as original array.

This is a preview of Rotate an Array. Read the full post (970 words, estimated 3:53 mins reading time)

Inorder traversal using constant space – Morris Traversal

Posted on by

Usual approach using linear space (stack)
We can easily do the traversal by using a stack where we keep pushing left. If no left is there then we pop an element to print it and then push its right. This is O(n) time and O(n) space algorithm.

This is a preview of Inorder traversal using constant space – Morris Traversal. Read the full post (450 words, estimated 1:48 mins reading time)