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.....


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) {

        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()) )
                        temp1 = A.get(swap1);
                        temp2 = A.get(swap2);
                        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?



1 Answer 1


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.

  • \$\begingroup\$ 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? \$\endgroup\$ Mar 20, 2018 at 10:41
  • \$\begingroup\$ 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. \$\endgroup\$
    – bipll
    Mar 20, 2018 at 11:08
  • \$\begingroup\$ And for a better approach, technically, a wave array could have been built faster than NlogN if not for the smallest solution requirement. \$\endgroup\$
    – bipll
    Mar 20, 2018 at 11:11
  • \$\begingroup\$ 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? \$\endgroup\$ Mar 20, 2018 at 14:06
  • \$\begingroup\$ 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. \$\endgroup\$
    – bipll
    Mar 20, 2018 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.