C++ adjacent values

Question

I saw the following question, while managed to solve it in O(n^2) I think we can do better.

Given a vector of integers return the maximum number of non-adjacent copies of similar number.

For example, given: [9,2,3,4,0,4,5,6,0,8]

we can see that we have 2 non adjacent 0 and 2 non adjacent 4 (the rest are ones) so the answer is max(2,2)=2;

given: [4,4,4,4,4]

we have 3 non adjacent 4 so the answer is 3. we take first 4, then we can't take the one next to it (they are adjacent) so we take the one after and so on.

My solution: Iterate over the vector and check how many non adjacent copies we see from the current number, if it's bigger than current max we update max accordingly.

Q: How can we solve this more efficiently?

Answer 1

This problem can be solved by creating an array which contains number and it's index as showed below,

original array = [9, 2, 3, 4, 0, 4, 5, 6, 0, 8],
number index array = [9, 0], [2, 1], [3, 2], [4, 3], [0, 4], [4, 5], [5, 6], [6, 7], [0, 8], [8, 9]

Here first element of std::pair is number itself and second element is index of number.
After it, sort this array by numbers and result would be as follows,
[0, 8], [0, 4], [2, 1], [3, 2], [4, 5], [4, 3], [5, 6], [6, 7], [8, 9], [9, 0]

Purpose of sorting is to bring same numbers adjacent to each other. Once same numbers are adjacent a simple iteration is required to find answer. Let's see how it works,

First number in sorted array is 0 and by finding upper bound of 0 will give all adjacent 0, it means following will be available,
[0, 8], [0, 4]
But As you can see above these entries are not in order of index entry of index 4 is following entry of index 8 and this is because std::sort is not a stable sort, it means relative order of elements are not preserved. So before proceeding these elements have to sort again by index and result would be

[0, 4], [0, 8]
As showed above index 4 and 8 are not adjacent 4 + 1 != 8, and count of non adjacent numbers is two.

All entries of 0 are examined, and algorithm will consider next number which is 2, but as you see above in array there is only one entry of number 2 which is [2, 1] and due to this next number will be considered, same will happen for all numbers so let directly see number 4 and it has more then one entries as showed below,
[4, 5], [4, 3]
then sort these entries by index,

[4, 3], [4, 5]
here again indexes are not adjacent indexes 3 + 1 != 5, and count of non adjacent number is two. Same process will be applied on all numbers and final answer will be max non adjacent number count = 2

For other example of array [4, 4, 4, 4, 4] final number and index array of it will be,

[4, 0], [4, 1], [4, 2], [4, 3], [4, 4]
And as you can see index 0, 2, 4 are not adjacent indexes and max non adjacent number count = 3

#include <iostream>

#include <vector>
#include <algorithm>

using std::cout;

std::size_t countNonAdjacentEntries(std::vector<std::pair<int, std::size_t>>::const_iterator firstIt,
                                    std::vector<std::pair<int, std::size_t>>::const_iterator lastIt){


    std::size_t count = 0;

    for(std::vector<std::pair<int, std::size_t>>::const_iterator preIt = firstIt, it = preIt + 1; lastIt != it;){

        if(preIt->second + 1 != it->second){

            ++count;

            preIt = it;
            ++it;
        }
        else{
            ++it;
        }
    }

    ++count;
    return count;
}

std::size_t maxNonAdjacentNumber(const std::vector<int>& numbers){

    std::vector<std::pair<int, std::size_t>> numAndIndex;
    numAndIndex.reserve(numbers.size());

    for(std::vector<int>::size_type i = 0, numbersCount = numbers.size(); i < numbersCount; ++i){

        numAndIndex.emplace_back(numbers[i], i);
    }

    std::sort(numAndIndex.begin(), numAndIndex.end(),
              [](const std::pair<int, std::size_t>& a, const std::pair<int, std::size_t>& b){
        return a.first < b.first;});

    std::size_t count = 0;

    for(std::vector<std::pair<int, std::size_t>>::const_iterator it = numAndIndex.cbegin(), endIt = numAndIndex.cend();
        endIt != it; ){

        std::vector<std::pair<int, std::size_t>>::const_iterator upBoundIt = std::upper_bound( it + 1, endIt, it->first,
                    [](int val, const std::pair<int, std::size_t>& ele){return val < ele.first;});

        if(upBoundIt - it > 1){

            std::sort(numAndIndex.begin(), numAndIndex.end(),
                      [](const std::pair<int, std::size_t>& a, const std::pair<int, std::size_t>& b){
                return a.second < b.second;});

            count = std::max(count, countNonAdjacentEntries(it, upBoundIt));
            it = upBoundIt;
        }
        else{
            ++it;
        }
    }

    return count;
}

int main(){

    cout<< "[9, 2, 3, 4, 0, 4, 5, 6, 0, 8] => "<< maxNonAdjacentNumber({9, 2, 3, 4, 0, 4, 5, 6, 0, 8})<< '\n';
    cout<< "[4, 4, 4, 4, 4] => "<< maxNonAdjacentNumber({4, 4, 4, 4, 4})<< '\n';
}

Output

[9, 2, 3, 4, 0, 4, 5, 6, 0, 8] => 2
[4, 4, 4, 4, 4] => 3

Answer 2

unique to remove duplicates, sort to clump remaining, then find longest run.

template<class T, class A>
std::optional<T> most_runs_of( std::vector<T, A> r ) {
  if (r.empty()) return std::nullopt;
  r.erase( std::unique( begin(r), end(r) ), end(r) );
  std::sort( begin(r), end(r) );
  T winner = r.front();
  std::size_t winner_count = 0;
  T const* cur = nullptr;
  std::size_t cur_count = 0;
  for (T const& e:r) {
    if (e == winner)
    {
      ++winner_count;
      continue;
    }
    if (cur && *cur==e) {
      ++cur_count;
      if (cur_count > winner_count) {
        winner = e;
        winner_count = cur_count;
        cur = nullptr;
        continue;
      }
    }
    cur = std::addressof(e);
    cur_count = 1;
  }
  return winner;
}

This copies the std::vector and does it in-place in the copy in O(nlgn) and O(n) space.

If you don't need the std::vector after you call the above, std::move it into the algorithm.

Answer 3

If you're fine with using O(n) space, you can use buckets for the values you see to achieve an O(n) runtime.

The easiest way to implement that would be with a map. ie:

std::pair<int, int> max_adj(std::vector<int> arr) {
    std::map<int, int> buckets;
    
    for(int x = 0; x < arr.size(); x++) {
        // Loop to eat up adjacent values
        int in_a_row = 1;
        for(int curr = x++;
            x < arr.size() && arr[curr] == arr[x];
            x++, in_a_row++) { }
        x--; // The loop will increment x one past last dupe, so go back
        
        // Only count every other adjacent value seen
        buckets[arr[x]] += (in_a_row + 1) / 2;
    }
    
    // Find the most seen
    std::map<int, int>::iterator mx = std::max_element
    (
        buckets.begin(), buckets.end(),
        [] (const std::pair<int, int> &p1, const std::pair<int, int> &p2) {
            return p1.second < p2.second;
        }
    );
    
    if(mx != buckets.end()) {
        return *mx;
    }
    return std::pair<int, int>(-1, -1);
}

Live example: https://ideone.com/v9OOIA