Reverse Array Order

Question

I am trying to reverse the order of an Array in java.
What is the most efficient way to do so in O(n) with the least amount of memory used.
No need to answer with code, pseudo code will be fine.
Here is my thought process:

  create a new temp array //I think this is a waste of memory, 
                          //but I am not sure if there's a better way
 grab elements from the end of the original array -decrement this variable
 insert element in beginning of temp array -increment this variable
then make the original array point to the temp array? //I am not sure 
            //if I can do this in java; so let's say the 
            //original array is Object[] arr; and the temp array is 
            //Object[] temp. Can I do temp = arr; ?

Is there a better more efficient way to do this perhaps without using a temp array? and Lastly, assume that there are no nulls in the array, so everything can work. Thank you

Edit: no this is not homework.

consider swaping first and last items and then the second and second last items till you reach half the list... you will just need one temporary variable and will still go over the list once? — Osama Javed, Apr 03 '12 at 14:36
http://stackoverflow.com/questions/2137755/how-do-i-reverse-an-int-array-in-java — , Apr 03 '12 at 14:36
Just loop through the original array in reverse order, and create a new container to contain the new order inserts. it's O(n) — Churk, Apr 03 '12 at 14:38

Louis Wasserman · Accepted Answer · 2012-04-03T16:15:06.693

56

If it's an Object array, then Collections.reverse(Arrays.asList(array)) will do the job with constant memory and linear time -- no temporary array required.

edited Apr 03 '12 at 16:15

answered Apr 03 '12 at 14:39

Louis Wasserman

191,574
25
345
413

4

+1 Indeed, since the OP now says this is not homework, this is a great answer. – Ernest Friedman-Hill Apr 03 '12 at 14:42
Love the solution. Just confirmed that no temporary array is required see: http://ideone.com/api/embed.js/link/xLLTpl ... click "Clone" and then "Run" – eddyparkinson Jan 23 '13 at 04:22
Does not work, at least with Java 1.6: System.out.println( X[ 0 ] + " to " + X[ X.length - 1 ] ); Collections.reverse( Arrays.asList( X ) ); System.out.println( X[ 0 ] + " to " + X[ X.length - 1 ] ); prints: 2272.6270739116 to 186.704625250768 2272.6270739116 to 186.704625250768 – Jean-Yves Aug 13 '14 at 20:51
1

@Jean-Yves: What is the type of `X`? I strongly suspect it's not an object array, which I specified in my answer was necessary. – Louis Wasserman Aug 13 '14 at 21:10

ArjunShankar · Answer 2 · 2013-06-23T22:20:04.413

13

Use a single temp element.

int array[SIZE];
int temp;

for (int i = 0; i < SIZE/2; i++)
  {
     temp = array[i];
     array[i] = array[SIZE-1 - i];
     array[SIZE-1 - i] = temp;
  }

edited Jun 23 '13 at 22:20

answered Apr 03 '12 at 14:36

ArjunShankar

23,020
5
61
83

score 12 · Answer 3 · answered Apr 03 '12 at 14:36

12

You don't need to use a temporary array; just step through the array from the beginning to half-way through, swapping the element at i for the element at array.length-i-1. Be sure the handle the middle element correctly (not hard to do, but do make sure.)

answered Apr 03 '12 at 14:36

Ernest Friedman-Hill

80,601
10
150
186

score 2 · Answer 4 · edited Apr 03 '12 at 14:39

2

you can do it without needing a temp array

loop from the beginning (or end doesn't matter) to the middle of the array
swap element with element at (last element - index) (so 0 and size - 1, 1 and size - 2 etc)
you'll do something like this to swap:

    temp = a[i];
    a[i] = a[end-i];
    a[end-i] = temp;

repeat

edited Apr 03 '12 at 14:39

Ted Hopp

232,168
48
399
521

answered Apr 03 '12 at 14:36

twain249

5,666
1
21
26

score 0 · Answer 5 · answered Apr 03 '12 at 14:37

0

Here's two solutions:

    loop to N/2
      swap each element at i with element at N - i

Another solution is (depending on your circumstances) fake reversing the array by indexing:

    GetValueAt(int i){return array[N - i];}

answered Apr 03 '12 at 14:37

SirGuy

10,660
2
36
66

Andy · Answer 6 · 2022-07-26T14:40:02.213

-1

Lets consider we have Integer array arr[] - Integer array.

for(int i=0,int J=arr.length-1 ; i<j ; i++,j--)
{
    temp =a[i];
    a[i]=a[j];
    a[j]=temp;
 }

this algorithm has O(n/2) as we will perfrom n/2 swaps. and its space complexity is constant 1 , as we are taking on temp variable.

edited Jul 26 '22 at 14:40

answered Apr 20 '15 at 09:52

Andy

89
6

score -2 · Answer 7 · answered Jun 21 '17 at 03:32

-2

You can Do this in just two steps

ArrayList<Element> YourTempElement= new ArrayList<Element>(mElements);
Collections.reverse(YourTempElement);

answered Jun 21 '17 at 03:32

Darshan

11

Uses same methods as accepted answer, just less elegantly and with less of an explanation. – Nathan Tuggy Jun 21 '17 at 04:10
there are no need of explanation bro it's little two step nd i'm not explainer. – Darshan Jun 21 '17 at 04:34
Good answers on Stack Overflow explain things. The accepted answer does. If there's already a good answer that says the same thing you would, or if there's no way to write a good answer at all, there's no real point in adding an answer to the question: that just adds noise. – Nathan Tuggy Jun 21 '17 at 05:38

score -2 · Answer 8 · answered Apr 03 '12 at 14:37

-2

pseudocode, assuming 0-based-index arrays:

for i in range(0, len(array)/2):
     swap(array[i], array[(len(array)-1)-i])

answered Apr 03 '12 at 14:37

mcfinnigan

11,442
35
28

1

This does not look like Java. – ceving Dec 05 '13 at 10:10

Reverse Array Order

8 Answers8

Linked

Related