Approach

We can first sort array and then swap all adjacent array elements so that it forms a wave pattern. This solution will take O(nlogn) time if sorting algorithms like Merge Sort are used and time complexity will increase if time costlier algorithms like Insertion Sort are used.
We'd have done only swapping of adjacent elements in O(n) time and it would have satisfied first condition of this problem but this solution would fail in second condition i.e., Lexicographically smallest answer which could only be achieved by sorting the array first and then swapping.

Pseudo Code

This Program sorts the given array in a wave form

function wave ( Arguement givenArray ){

   Sort the givenArray using sort() function from STL
   swap Numbers of array in interval of two until last element is reached

   return sorted array
}

C++ Function Implementation

vector<int> wave(vector<int> &A) {
  sort(A.begin() , A.end());
  for(int i = 0 ; i < A.size() ; i += 2)
   if(i + 1 < A.size())
    swap(A[i] , A[i+1]);
  return A;
}

Program Code

#include <iostream>
#include <algorithm>
#include <vector>

//using namespace std;

using std::cin;
using std::cout;
using std::vector;
using std::swap;
using std::sort;

vector<int> wave(vector<int> &A) {
        sort(A.begin(),A.end());
        for(int i = 0 ; i < A.size() ; i += 2)
                if(i + 1 < A.size())
                        swap(A[i] , A[i+1]);
        return A;
}

int main(){

        int n, temp;
        vector<int> A;

        cin >> n;

        for( int i = 0; i < n; i++ ){
                cin >> temp;
                A.push_back(temp);
        }
        A = wave(A);

        for( int i = 0; i < n; i++ ){
                cout << A[i];
        }

        return 0;
}