Shift k array elements after a given array index

Question

Initial array: 2 23 34 27 89 14 26 30 60

k = 3

starting from index i = 1 we have to shift k elements so that they occur after the element 26 (i.e. after givenIndex = 6) in the array.

Final array: 2 89 14 26 23 34 27 30 60

We are NOT allowed to use extra space.

My approach:

count = 0;   
while(count < k)  
{  
  count++;  
  temp = arr[i];  
  shift all elements from (i+1) to givenIndex to their immediate left position;  
  arr[givenIndex] = temp;  
}

First iteration:
temp = 23
shift all elements from [i+1](i.e. index=2) to givenIndex(i.e. index=6) to left one by one
array after shifting: 2 34 27 89 14 26 26 30 60
arr[givenIndex] = temp
array after applying this operation: 2 34 27 89 14 26 23 30 60

Similarly
array after second iteration: 2 27 89 14 26 23 34 30 60
array after third iteration: 2 89 14 26 23 34 27 30 60

worst case complexity O(n*k) where n is the no. of elemnts in the array.

Can we solve the problem in O(n)

Wait... what? How did the shifting take place? Can you please explain a bit more. It's not clear much. From my point of view, I see some numbers swapped. — Matin Kh
– Matin Kh, Commented Aug 7, 2012 at 6:24
We are allowed to use a temporary varaible. But we aren't allowed to use space proportional to the number of elements being swapped. i.e. in the example mentioned in my question we can't use an extra space of O(k) where k is the number of elements we have to shift. — Prateek
– Prateek, Commented Aug 7, 2012 at 7:26
As there is 'k' rotation, it would be o(n * k). right? Or am I still missing something? — Matin Kh
– Matin Kh, Commented Aug 7, 2012 at 7:32

Blastfurnace · Accepted Answer · 2012-08-07 07:45:43Z

1

This rotation can be done in linear time using a reverse() helper function. Assuming that reverse(x, y) reverses array[x]..array[y] in place.

reverse(1, 3); // 27 34 23 .. .. ..
reverse(4, 6); // .. .. .. 26 14 89
reverse(1, 6); // 89 14 26 23 34 27

Writing a linear-time reverse is simple and might even be available in your favorite language library (for example, C++ includes std::rotate and std::reverse).

edited Aug 7, 2012 at 7:45

answered Aug 7, 2012 at 7:25

Blastfurnace

18.7k57 gold badges61 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Matin Kh Over a year ago

I don't think it improves the time-complexity.

lavin · Accepted Answer · 2012-08-07 07:39:49Z

0

as far as i can tell from your code(and the example), I think you are trying to put the block [i,i+k-1] after the block [i+k,givenIndex]

If that is the case, @Blastfurnace 's suggestion does lead to one solution in O(n) and no extra space:

simply do:

reverse(i,givenIndex)
reverse(i,givenIndex-k)
reverse(givenIndex-k+1,givenIndex)

and you have what you want :)

answered Aug 7, 2012 at 7:39

lavin

2,4562 gold badges14 silver badges15 bronze badges

Comments

Matin Kh · Accepted Answer · 2012-08-07 07:44:16Z

0

The question is quite amazing
See your requested answer here. If you are looking for a way to rotate your arraylist using JAVA, there is a complete solution for you here.
public static void rotate(List list, int distance)

Simply rotate your collection (ArrayList or LinkedList ...)
Its parameters are a list (in your case arraylist) and a distance (in your case k). Do you see the similarities? Simply use this.

answered Aug 7, 2012 at 7:44

Matin Kh

5,1986 gold badges58 silver badges81 bronze badges

2 Comments

Blastfurnace Over a year ago

That Java method uses the 3 reverse algorithm for large lists. The description even mentions Jon Bentley's Programming Pearls where I first learned the algorithm.

Matin Kh Over a year ago

Sure it does. So? To find out the solution he has to learn the algorithm too. But if he is using java, he can simply take advantage of the rotation which is using that.

Collectives™ on Stack Overflow

Shift k array elements after a given array index

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related