Hill Sequence ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 A sequence 

A1,A2,…,AN$A_1,A_2,\dots ,A_N$ of length N$N$ is called good if any one of the following hold:

• The sequence is strictly increasing, or
• The sequence is strictly decreasing, or
• There exists an index i(1<i<N)$i(1<i<N)$ such that:
  • Aj<Aj+1$A_j<A_{j+1}$, for each 1≤j<i$1\le j<i$
  • Aj>Aj+1$A_j>A_{j+1}$, for each i≤j<N$i\le j<N$

For example, the sequences [3,5,9]$[3,5,9]$, [2,1]$[2,1]$, [5,7,4,1]$[5,7,4,1]$ are good, while [6,7,7]$[6,7,7]$, [5,2,3]$[5,2,3]$ are not.

You are given an array A$A$ consisting of N$N$ integers. Find a good sequence by rearranging the elements of the array A$A$ or report that this is impossible. If there are multiple good sequences, print the lexicographically largest one.

Output Format

For each test case, if it is not possible to rearrange the given array into a good sequence, print −1$-1$. Otherwise, print a single line containing N$N$ space-separated integers - the lexicographically largest good sequence that can be made.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤Ai≤109$1\le A_i\le {10}^9$
• Sum of N$N$ over all test cases does not exceed 5⋅105

Code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

int main() 

{

ll t;

cin>>t;

while(t--)

{

    ll n,x,f=0;

    cin>>n;

    map<ll,ll> m;

    vector<ll>res,v;

    for(ll i=0;i<n;i++)

    {

        cin>>x;

        m[x]++;

    }

    for(auto x: m)

    {

        if(x.second>2)

        {

            f=1;

            break;

        }

        v.push_back(x.first);

    }

    sort(v.begin(),v.end());

    if(f==1 || m[v[v.size()-1]]==2)

    cout<<"-1";

    else

    {

        for(ll i=0;i<v.size();i++)

        {

            if(m[v[i]]==2)

            cout<<v[i]<<" ";

        }

        for(ll i=v.size()-1;i>=0;i--)

        cout<<v[i]<<" ";

        

    }

    cout<<endl;

}

}

• Tweet
• Share
• Share
• Share
• Share

Related Post