Friday, March 18, 2016

LeetCode OJ - Count of Smaller Numbers After Self

Problem: 

Please find the problem here.

Analysis:

A straightforward solution for this one is simply actually count them, that would mean a $ O(n^2) $ algorithm, can we do faster?

Note that the last entry must be zero, can we build that up from the end? As a first thought, we might be able to by having a data structure that can tell me the answer, then we can incrementally update the answer. The data structure must tell the number of numbers less than a certain value, a sorted list, or binary search tree, would be ideal. That would mean a performance of $ O(n \log n) $.

The only drawback would be complicated. Building a balanced binary search tree is complicated, can we simplify?

Solution:

If we wanted an $ O(n \log n) $ solution, we would normally think divide and conquer. Suppose we were given the answers to the subproblems, can we solve merge the subproblem in linear time?

Yes, and that is essentially the same as merge sort.

Suppose we have an array 5 2 6 1, we have the subproblem (5 2) and (6 1), and we already have the answers to them

(5[1] 2[0]) (6[1] 1[0]) // count is put inside the square bracket, what would be the merged solution.

Let's work backwards, the final answer is

(5[2] 2[1] 6[1] 1[0])

Note one thing, the right hand side counts do not change right, of course, they should not.

The 2 has increased count by 1, and that is because it is larger than 1. So if we do the merge just like what one would do with mergesort (and fill the output array from the right hand side first), then we can follow this simple rule.

Whenever a left hand side number get filled to the output buffer, its count increase by the number of already filled numbers on the right.

Let's illustrate that with the array above, we have

Input: (5[1] 2[0]) (6[1] 1[0])
Output: ()

First step, nothing changed, the entry get filled was on the right
Input: (5[1] 2[0]) (6[1])
Output: (1[0])

Second step, count of 2 increase by 1 (that is the number of numbers added from the right hand side so far)

Input: (5[1]) (6[1])
Output: (2[1] 1[0])

Third step, count of 5 increase by 1 (again, that is the number of numbers added from the right hand side so far)

Input: () (6[1])
Output: (5[2] 2[1] 1[0])

First step, nothing changed, the entry get filled was on the right
Input: () ()
Output: (6[1] 5[2] 2[1] 1[0])

Wait, this isn't exactly the answer sequence we wanted! Don't get tricked by this, the right answer sequence is 5[2] 2[1] 6[1] 1[0], apparently, when we sort the sequence, of course, the number sequence changes, only the count stay correct!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/count-of-smaller-numbers-after-self/

#include "LEET_COUNT_OF_SMALLER_NUMBERS_AFTER_SELF.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_COUNT_OF_SMALLER_NUMBERS_AFTER_SELF
{
    class Solution
    {
    public:
        vector<int> countSmaller(vector<int>& nums)
        {
            vector<int> counts(nums.size());
            vector<int> result(nums.size());
            vector<int> buffer(nums.size());
            for (size_t i = 0; i < result.size(); i++)
            {
                counts[i] = 0;
            }
            countSmaller(0, nums.size(), nums, result, buffer, counts);
            return counts;
        }

        void countSmaller(int begin, int end, vector<int>& nums, vector<int>& result, vector<int>& buffer, vector<int>& counts)
        {
            // At this point, we have a correct merge sort implementation
            if (end - begin <= 1)
            {
                for (size_t i = begin; i < end; i++)
                {
                    result[i] = i;
                }
                return;
            }
            int mid = (begin + end) / 2;
            countSmaller(begin, mid, nums, buffer, result, counts);
            countSmaller(mid, end, nums, buffer, result, counts);
            int i = mid - 1;
            int j = end - 1;
            int k = end - 1;
            while ((i >= begin) || (j >= mid))
            {
                if (i < begin)
                {
                    result[k--] = buffer[j--];
                }
                else if (j < mid)
                {
                    counts[buffer[i]] += (end - 1 - j);
                    result[k--] = buffer[i--];
                }
                else
                {
                    // Prioritize moving the left hand side item 
                    // to avoid counting identical element as smaller
                    if (nums[buffer[i]] <= nums[buffer[j]])
                    {
                        counts[buffer[i]] += (end - 1 - j);
                        result[k--] = buffer[i--];
                    }
                    else
                    {
                        result[k--] = buffer[j--];
                    }
                }
            }
            /*cout << "After merge" << endl;
            for (int i = begin; i < end; i++)
            {
                cout << nums[result[i]] << " ";
            }
            cout << endl;
            for (int i = begin; i < end; i++)
            {
                cout << counts[result[i]] << " ";
            }
            cout << endl;*/
        }
    };
};

using namespace _LEET_COUNT_OF_SMALLER_NUMBERS_AFTER_SELF;

int LEET_COUNT_OF_SMALLER_NUMBERS_AFTER_SELF()
{
    Solution solution;
    int input_array[] = { 5, 2, 6, 1 };
    vector<int> input(input_array, input_array + _countof(input_array));
    vector<int> result = solution.countSmaller(input);
    for (size_t i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

No comments :

Post a Comment