Insertion Sort - Find the Number of Larger Values in the Remaining Array

1. Problem Description

This is a Google interview question from careercup. Here is the original thread,

"

Given an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array. 

Brute force is obvious, but must be done faster than O(n^2)

Ex. [3,4,5,9,2,1, 3]
Return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc

- PradeepN about a month ago in United States | Report Duplicate | Flag ".

2. Pseudo-code

The idea is to start from the right hand side of array to the left hand side and use insertion sort.

    - Initialize a sorted data like std::set as sortedArray

    - Initialize a linked list to take the result, result

    - Take the element, x, from the array in the reverse order

    - Find the number of larger value in sortedArray than x, as n

    - Push n into the front of result

    - Insert x into sortedArray
    - Loop the above 4 steps until exhaust the whole array

    - Return result

As the loop goes on, each element is inserted into a sorted array. This is good hint to employ insertion sort. But normally insertion sort uses continuous memory array, then it requires linear memory shift. Therefore the key is to use node-based data structure like binary tree in this case. Again the result is populated in the reverse order. Therefore a linked-list is good option to take the result because it take constant time to push a value in the front.

Alternative approach:

    - Sort the array by a binary tree, sortedArray

    - Initialize a vector to take result, result

    - Take the element, x, in the left-to-right order

    - Find the number of larger value than x in sortedArray, as n

    - Push back n into result

    - Remove x from sortedArray

    - Repeat the above 4 steps until exhaust the whole array

    - Return result

3. C++ Implementation

// ********************************************************************************

// Implementation

// ********************************************************************************

#include <set>

#include <list>

#include <vector>

template <typename T>

std::vector<T> FindTheNumberOfLargerValuesInTheRemainingArray(std::vector<T> const& input)

{

    std::set<T> sortedArray;

    std::list<T> result;

    auto iterEnd = input.rend();

    for (auto iter = input.rbegin(); iter != iterEnd; ++iter) {

        auto ub = sortedArray.upper_bound(*iter);

        result.push_front(std::distance(ub, sortedArray.end()));

        sortedArray.insert(*iter);

    }

    return std::vector<T>(result.begin(), result.end());

}

// ********************************************************************************

// Test

// ********************************************************************************

#include <cassert>

void TestFindTheNumberOfLargerValuesInTheRemainingArray()

{

    {

        std::vector<int> input;

        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);

        assert(output.empty() == true);

        input.push_back(0);

        output = FindTheNumberOfLargerValuesInTheRemainingArray(input);

        assert(output.size() == 1);

        assert(output[0] == 0);

    }

    {

        std::vector<int> input = { 3, 4, 5, 9, 2, 1, 3 };

        const std::vector<int> result = { 3, 2, 1, 0, 1, 1, 0 };

        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);

        assert(result == output);

    }

    {

        std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

        const std::vector<int> result = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);

        assert(result == output);

    }

    {

        std::vector<int> input = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

        const std::vector<int> result = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);

        assert(result == output);

    }

}