Is ther an O(n) soln? OR the best we can do is O(nlogn)


#1

Is ther an O(n) soln? OR the best we can do is O(nlogn)


#2

Yes there is an O(n) solution available. Basically you make two pass on the array.
In the first pass, pick two index per iteration. If input[i] > input[i+1] then swap it.
Now in the second pass, starting index is 1 and we check if input[i]<input[i+1] then we swap.
Here is the algorithm
for (i = 0; i+1<arr.size; i+=2) {
if (arr[i]>arr[i+1) { swap(i, i+1) } } for (i = 1; i+1<arr.size; i+=2) { if(input[i]<input[i+1]) {
swap(i, i+1)
}
}

Why this algorithm works?
Lets say we have input{a, b, c, d}
After first pass, we know that a< b and c < d
In the second pass, if b > c then we already have a wave array now and we need not do anything. If however, b < c, then we swap them so array becomes {a, c, b, d}
Now, since a < b and b < c, therefore a < c and similarly since d > c and c > b therefore d > b


#3

I don’t think this will give the lexicographically smallest answer though. You’d have to sort the array first for that and it will take O(nlogn) time.


#4

I agree to explanation provided by the Steven. But the thing is, We have to differentiate multiple solutions from the one we have to submit.

We have to return the array which is lexicographically smallest.

That’s why, I used sorting. Please correct me if I am wrong.


#5

Your solution does not satisfy this condition:
a1 >= a2 <= a3 >= a4 <= a5…


#6

Well, it is not difficult to show that an O(n) solution can be modified into an O(n) sorting algorithm. This should hint about the possibility to provide a linear-time solution…


#7

galam1483 is right. If you can solve this problem (of course with the lexicographical condition) in O(n) time, then you could bring it into a fully sorted array in O(n) time, implying sorting can be done in linear worst-case time which we know is impossible for a comparison-based method like this.


#8

i agree to the stevens answer. But to print in the lexicographic order, we have to first sort the array. rest of the code is Order n. Its can also give soln in Order n but not the lexico… one.
heres the code.
class Solution:
# @param A : list of integers
# @return a list of integers
def wave(self, A):
c=0
A.sort()
for i in range(len(A)-1):

        if(i%2==0):
            if(A[i]>=A[i+1]):
                # print("even true")
                continue
            else:
                # print("even false")
                tmp=A[i]
                A[i]=A[i+1]
                A[i+1]=tmp
        else:
            if(A[i]<=A[i+1]):
                # print("odd true")
                continue
            else:
                # print("odd false")
                tmp=A[i]
                A[i]=A[i+1]
                A[i+1]=tmp
    return A

#9

I don’t think this is a O(n) solution because there is a nested for loop.


#10

O(n) is possible just swap the odd index elements of the array with the previous elements :slight_smile:


#11

nice! the common sense you used here will help a lot in solving problems. It will narrow down your thinking approach and you will think in the right direction. Like sorting cant be done in O(n) unless it is already sorted!


#12

If it is not mentioned to get lexicographically smallest, this question transforms to creating a permutation from a stringhere.