HackerRank - Almost Sorted

Question

I've written the following algorithm to solve this HackerRank problem using STL algorithms.

Problem statement

Given an array with n elements, can you sort this array in ascending order using only one of the following operations?

1. Swap two elements.
2. Reverse one sub-segment.

Input Format

The first line contains a single integer, n, which indicates the size of the array. The next line contains integers separated by spaces.

n  
d1 d2 ... dn

Output Format

1. If the array is already sorted, output yes on the first line. You do not need to output anything else.

2. If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:

   • If you can sort the array by swapping d_l and d_r, output "swap l r" in the second line. l and r are the indices of the elements to be swapped, assuming that the array is indexed from 1 to n.

   • Else if it is possible to sort the array by reversing the segment d[l...r], output "reverse l r" in the second line. l and r are the indices of the first and last elements of the subsequence to be reversed, assuming that the array is indexed from 1 to n.

d[l...r] represents the sub-sequence of the array, beginning at index l and ending at index r, both inclusive.

If an array can be sorted by either swapping or reversing, stick to the swap-based method.

3. If you cannot sort the array in either of the above ways, output "no" in the first line.

Code

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

int main() {
    int n; std::cin >> n;
    std::vector<int> v;
    v.reserve(n);
    while(n--){
        int x; std::cin >> x;
        v.push_back(x);
    }
    auto v_sorted = v;
    std::sort(v_sorted.begin(),v_sorted.end());

    auto mismatch_1 = std::mismatch(v.begin(),v.end(),
                                    v_sorted.begin());
    auto mismatch_2 = std::mismatch(std::next(mismatch_1.first),v.end(),
                                    std::next(mismatch_1.second));
    auto mismatch_3 = std::mismatch(v.rbegin(),v.rend(),
                                    v_sorted.rbegin());

    if (std::prev(mismatch_3.first.base()) == mismatch_2.first) {
        if (*std::prev(mismatch_2.first)<=*mismatch_1.first) {
           std::cout 
               << "yes\n" << "swap " 
               << std::distance(v.begin(),mismatch_1.first) + 1
               << " "
               << std::distance(v.begin(),mismatch_2.first) + 1;
        }
    }
    else {
       std::reverse(mismatch_1.first,mismatch_3.first.base());
       if (std::equal(mismatch_1.first,std::prev(mismatch_3.first.base()),mismatch_1.second)) {
           std::cout
               << "yes\n" << "reverse "
               << std::distance(v.begin(),mismatch_1.first) + 1
               << " "
               << std::distance(v.begin(),std::prev(mismatch_3.first.base())) + 1;
       }
       else {
           std::cout << "no";
       }
    }

    return 0;
}

Questions

My main question is about reverse iterators. I feel it's a little bit confusing when I compare them with forward iterators, as I need to do std::prev(reverse_iterator.base()). Do you think this affects readability or is the code fine like it is? Any other suggestion?

Answer 1

I find the reverse iterators a bit confusing, but I might be a little slow. That said, I'm probably not the only one, so you wouldn't waste your time looking for a simpler way to express yourself.

I'd add that you forgot to handle the case where the input is already sorted, meaning that you could have been overwhelmed yourself ;-)

My suggestion, using std::adjacent_find to detect sign changes (note that I use a reverse iterator only once, to denote the vector's last element -in that case it feels intuitive to me):

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

void is_almost_sorted(std::vector<int>& vec) {
    // find swap candidates, swap and check if sorted
    auto first  = std::adjacent_find(vec.begin(), vec.end(), std::greater<int>()); // first sign change... 
    if (first == vec.end()) {
        std::cout << "Already sorted";
        return;
    }
    auto bkp = vec;
    auto second = std::adjacent_find(first+1, vec.end(), std::greater<int>()); // and second
    if (second != vec.end() 
        && (std::iter_swap(first, second+1), std::is_sorted(vec.begin(), vec.end()))) {
        std::cout << "swap " << *first << " and " << *++second;
        return;
    }
    // restore from original vec
    auto offset = std::distance(vec.begin(), first);
    vec = std::move(bkp);
    first = vec.begin()+offset;
    // find inverse change of signs, reverse and check if sorted
    second = std::adjacent_find(first+1, vec.end(), std::less<int>());
    std::reverse(first, second == vec.end() ? second : second + 1);
    if (std::is_sorted(vec.begin(), vec.end())) {
        std::cout << "reverse from " << *first 
                  << " to " << (second == vec.end() ? *std::rbegin(vec) : *++second);
        return;
    }
    std::cout << "no solution";
}