# Rearranging numbers of an array like a wave

Given an array of integers, sort the array into a wave like array and return it, In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

### Example

Given [1, 2, 3, 4]

One possible answer: [2, 1, 4, 3]
Another possible answer : [4, 1, 3, 2]

NOTE: If there are multiple answers possible, return the one thats lexicographically smallest. So, in example case, you will return [2, 1, 4, 3]

My approach:

public class Solution {
public ArrayList<Integer> wave(ArrayList<Integer> A) {

Collections.sort(A);
int swap1, swap2,temp1,temp2;
//We will have to swap all the odd numbered elements with the even numbered elements
//such that all numbers with a gap 0f 1 are sorted
for( swap1= 0, swap2 = swap1 + 1; swap1 <= A.size()- 2; swap1 = swap1+2,swap2 = swap2+2 )
{
//Check if swap1 reaches last element
if( (swap1 == A.size() - 1) || (swap2 == A.size()) )
break;
else
{
temp1 = A.get(swap1);
temp2 = A.get(swap2);
A.set(swap1,temp2);
A.set(swap2, temp1);
}
}
return A;
}
}


I have the following questions regarding my code:

1. How can I further optimize my code? (I am unable to solve these questions within the prescribed time limit. What can I do?)

2. Is there any better approach to do this question?

3. Have I violated any convention in coding?

4. Are there any redundancies in my approach?

Reference

Few observations.

1. You don't need to maintain swap2 separately, it is always swap1 + 1, so can be simply declared inside the loop's body.

2. Your boundaries check inside the loop body is redundant, loop condition alone is enough.

3. You're probably performing too many int-to-Integer and back conversions. Even more, the question deals with arrays, you don't need to pre-convert the argument into a list. Accept, process and return an array of plain ints.

• You are correct about the redundancy of variables. I could do it with swap1 alone. I had received the input as an arrayList of integers, so I am not converting it to an integer array. Thanks for the advice. Could you also give some advice regarding 4 and 5? Mar 20, 2018 at 10:41
• See 2. in my response concerning boundaries. As 5. can you specify what exactly you mean? Are 'there questions' numbers 1) through 4)? Too broad. Mar 20, 2018 at 11:08
• And for a better approach, technically, a wave array could have been built faster than NlogN if not for the smallest solution requirement. Mar 20, 2018 at 11:11
• By 5, I meant that I was unable to solve a particular interview question within a time limit. What can I do for this kind of problem? Mar 20, 2018 at 14:06
• Practice. When you face a problem, you need to a) formalize it; b) decompose into elementary pieces trivially solvable; c) construct a valid solution of those pieces. This looks like a reasonable strategy to solve problems in a given time frame. Something like "Learn kung fu," but more detailed. Mar 20, 2018 at 14:28