## Saturday, October 8, 2016

### LeetCode OJ - Queue Reconstruction by Height

Problem:

Analysis:

The key idea for this one is that we know everyone is taller than the shortest one. So when the shortest one say there are 4 men taller in front of him, it is obvious that he is in the fifth position.

The next shortest one come by, we know that the previous man is shorter than him, so when he say there are 10 men taller than him in front, we know we need to count 10 spaces in front of him before assigning him the position right after.

There is a simple special case. If two men are of the same height, simply assign the one with more spaces in front first.

Solution:

Sorting is fast enough, the key problem is how to do the position assignment fast enough without running the list to find spaces. The key idea is to use a segment tree for the 0-1 array for the assignment. If a space is assigned, it is 0, otherwise it is 1. We know we can update the array and compute the sum fast, but actually we can also use the tree to find an index that achieve a certain sum fast as well. That is how I achieved $O(n \log n)$ time for this problem.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/queue-reconstruction-by-height/

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

using namespace std;

namespace _LEET_QUEUE_RECONSTRUCTION_BY_HEIGHT
{
class Solution
{
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people)
{
if (people.size() < 2)
{
return people;
}
int n = people.size();
for (int i = 0; i < n; i++)
{
people[i].second = n - people[i].second;
}
sort(people.begin(), people.end());
for (int i = 0; i < n; i++)
{
people[i].second = n - people[i].second;
}
Node* tree = build_tree(0, n);

vector<pair<int, int>> result;
result.resize(n);
for (int i = 0; i < n; i++)
{
int position = place_in_tree(tree, people[i].second);
#ifdef LOG
cout << "Searching for " << people[i].first << ", " << people[i].second << endl;
cout << "===================" << endl;
print(tree, 0);
cout << "===================" << endl;
cout << position << endl;
#endif
result[position] = people[i];
}

return result;
}
private:
struct Node
{
Node* left;
Node* right;
int begin;
int sum;
};
#ifdef LOG
void print(Node* tree, int indent)
{
if (tree == nullptr) { return; }
for (int i = 0; i < indent; i++) { cout << " "; } cout << tree->sum << (tree->left == nullptr ? "*" : "") << endl;
print(tree->left, indent + 2);
print(tree->right, indent + 2);
}
#endif
int place_in_tree(Node* tree, int position)
{
tree->sum--;
if (tree->left == NULL)
{
if (position != 0) { throw 1; }
return tree->begin;
}
else
{
if (position < tree->left->sum)
{
return place_in_tree(tree->left, position);
}
else
{
return place_in_tree(tree->right, position - tree->left->sum);
}
}
}
Node* build_tree(int start, int end)
{
Node* result = new Node();
result->begin = start;
if (start + 1 == end)
{
result->left = result->right = nullptr;
result->sum = 1;
}
else
{
int mid = start + (end - start) / 2;
result->left = build_tree(start, mid);
result->right = build_tree(mid, end);
result->sum = result->left->sum + result->right->sum;
}
return result;
}
};
};

using namespace _LEET_QUEUE_RECONSTRUCTION_BY_HEIGHT;

int LEET_QUEUE_RECONSTRUCTION_BY_HEIGHT()
{
vector<pair<int, int>> example;
// [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
example.push_back(make_pair(7, 0));
example.push_back(make_pair(4, 4));
example.push_back(make_pair(7, 1));
example.push_back(make_pair(5, 0));
example.push_back(make_pair(6, 1));
example.push_back(make_pair(5, 2));
Solution solution;
}