## Saturday, April 2, 2016

### LeetCode OJ - The Skyline Problem

Problem:

Analysis:

We need to be able to know at all time how high is the tallest building right now, so naturally we would like to do it with a priority queue. We scan from left to right and maintain a priority queue at all time, then we will be able report the result.

Solution:

In order to quickly scan from left to right, we sort the 'events'. An event is when thing changes, so for this problem, it is entering a building and leaving a building. We insert the building's height into a priority queue when we enter and remove it when we are done.

The sorting itself take $O(n \log n)$ time, each event is processed exactly once and take $O(\log n)$ time, so the overall complexity is $O(n \log n)$.

There is a couple challenges to the implementation:

1.) Sometimes multiple events happen in the same 'x', so we need to process all events in the same x before we consider to output, and

2.) C++/C# does not come with an implementation of a priority queue, so we have to implement one from scratch.

But it is already my many number of times implementing a priority queue, so it isn't really a big deal. The trick I used is to keep also a backward index from building to heap node index to make removal quick.

The code is almost too long for the judge to accept, I really hate this constraint ...

Code:

#include "stdafx.h"

// https://leetcode.com/problems/the-skyline-problem/

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

using namespace std;

namespace _LEET_THE_SKYLINE_PROBLEM
{
class Solution
{
private:
class event_comparer
{
public:
event_comparer(vector<vector<int>>& buildings) : m_buildings(buildings) {}
bool operator() (pair<int, bool> i, pair<int, bool> j)
{
int ix = i.second ? this->m_buildings[i.first][0] : this->m_buildings[i.first][1];
int jx = j.second ? this->m_buildings[j.first][0] : this->m_buildings[j.first][1];
return ix < jx;
}
private:
vector<vector<int>>& m_buildings;
};

class status
{
public:
status(vector<vector<int>>& buildings) : m_buildings(buildings), m_heap_size(0)
{
this->m_heap.resize(buildings.size());
this->m_building_heap_index.resize(buildings.size());
}

void insert(int building_index)
{
this->m_heap[this->m_heap_size] = building_index;
this->m_building_heap_index[building_index] = this->m_heap_size;
this->m_heap_size++;
this->bubble_up(this->m_heap_size - 1);
}

void remove(int building_index)
{
int heap_index = this->m_building_heap_index[building_index];
int last_building = this->m_heap[this->m_heap_size - 1];

this->m_heap_size--;

if (building_index == last_building)
{
return;
}

this->m_heap[heap_index] = last_building;
this->m_building_heap_index[last_building] = heap_index;

if (this->m_heap_size > 0)
{
this->bubble_down(heap_index);
}
}

void bubble_up(int current_index)
{
if (current_index == 0)
{
return;
}

int parent_index = (current_index + 1) / 2 - 1;
int current_building = this->m_heap[current_index];
int parent_building = this->m_heap[parent_index];
int current_building_height = this->m_buildings[current_building][2];
int parent_building_height = this->m_buildings[parent_building][2];
if (current_building_height > parent_building_height)
{
swap(this->m_heap[current_index], this->m_heap[parent_index]);
swap(this->m_building_heap_index[current_building], this->m_building_heap_index[parent_building]);
this->bubble_up(parent_index);
}
}

void bubble_down(int current_index)
{
int right_child_index = (current_index + 1) * 2;
int left_child_index = right_child_index - 1;

int current_building = this->m_heap[current_index];
int current_building_height = this->m_buildings[current_building][2];

int max_index = current_index;
int max_building = current_building;
int max_height = current_building_height;
if (left_child_index < this->m_heap_size)
{
int left_building = this->m_heap[left_child_index];
int left_building_height = this->m_buildings[left_building][2];
if (left_building_height > max_height)
{
max_index = left_child_index;
max_building = left_building;
max_height = left_building_height;
}
}
if (right_child_index < this->m_heap_size)
{
int right_building = this->m_heap[right_child_index];
int right_building_height = this->m_buildings[right_building][2];
if (right_building_height > max_height)
{
max_index = right_child_index;
max_building = right_building;
max_height = right_building_height;
}
}
if (max_index != current_index)
{
swap(this->m_heap[current_index], this->m_heap[max_index]);
swap(this->m_building_heap_index[current_building], this->m_building_heap_index[max_building]);
this->bubble_down(max_index);
}
}

int height()
{
if (this->m_heap_size > 0)
{
int max_building = this->m_heap[0];
return this->m_buildings[max_building][2];
}
else
{
return 0;
}
}

private:
vector<vector<int>>& m_buildings;
int m_heap_size;
vector<int> m_heap;
vector<int> m_building_heap_index;
};

public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings)
{
vector<pair<int, int>> result;

// Step 1: Model each vertical line as an event
vector<pair<int, bool>> events(buildings.size() * 2); // (building_number, isGoingUp)
for (size_t i = 0; i < buildings.size(); i++)
{
events[i * 2] = pair<int, bool>(i, true);
events[i * 2 + 1] = pair<int, bool>(i, false);
}

// Step 2: Sort the events by x-coordinates
event_comparer my_event_comparer(buildings);
sort(events.begin(), events.end(), my_event_comparer);

// Step 3: Process the event and maintain the status by a heap
status my_status(buildings);
int event_index = 0;
int last_height = 0;
while (true) // make sure we process all events
{
if (event_index == events.size())
{
break;
}
bool processed_one_event = false;
int last_event_x = 1 << 31;

while (true) // make sure we process all events with the same x
{
if (event_index == events.size())
{
break;
}
// Decoding the event
pair<int, bool> event = events[event_index];
int event_building = event.first;
bool event_is_going_up = event.second;
int event_x = event_is_going_up ? buildings[event_building][0] : buildings[event_building][1];
int event_y = buildings[event_building][2];

if (processed_one_event && event_x != last_event_x)
{
break;
}
processed_one_event = true;
last_event_x = event_x;

if (event_is_going_up)
{
my_status.insert(event_building);
}
else
{
my_status.remove(event_building);
}

event_index++;
}

// Did we changed altitude? If so update the skyline
if (my_status.height() != last_height)
{
result.push_back(pair<int, int>(last_event_x, my_status.height()));
last_height = my_status.height();
}
}

return result;
}
};
};

using namespace _LEET_THE_SKYLINE_PROBLEM;

int LEET_THE_SKYLINE_PROBLEM()
{
Solution solution;
vector<vector<int>> buildings(5);
buildings[0].push_back(2);  buildings[0].push_back(9);  buildings[0].push_back(10);
buildings[1].push_back(3);  buildings[1].push_back(7);  buildings[1].push_back(15);
buildings[2].push_back(5);  buildings[2].push_back(12); buildings[2].push_back(12);
buildings[3].push_back(15); buildings[3].push_back(20); buildings[3].push_back(10);
buildings[4].push_back(19); buildings[4].push_back(24); buildings[4].push_back(8);

vector<pair<int, int>> result = solution.getSkyline(buildings);
for (size_t i = 0; i < result.size(); i++)
{
cout << result[i].first << ", " << result[i].second << endl;
}

return 0;
}

### LeetCode OJ - Word Ladder

Problem:

Analysis:

This is a simple graph search, nothing much to talk about except one trick that I owe Zhicheng. In order to build the graph to search, one naturally need to consider every pair of words to see if they're connected, that will lead to an $O(n^2)$ algorithm, but ...

Solution:

We can do that in $O(n + m)$ where $m$ is the actual number of links (assuming the length of the word is a constant). The key idea is put the words in a hash table, and then checking each possible children of a word by varying one letter at a time. For each node we will probe the hash table 26 x length of word times, but that is just a constant, so we will find all children in constant time, skipping the graph construction.

Code:

#include "stdafx.h"

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>

using namespace std;

{
class Solution
{
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList)
{
int n = 0;
unordered_map<string, int> wordMap;
vector<string> strings;

for (unordered_set<string>::iterator wi = wordList.begin(); wi != wordList.end(); wi++)
{
strings.push_back(*wi);
wordMap.insert(pair<string, int>(*wi, n++));
}

wordMap.erase(beginWord);
wordMap.erase(endWord);
wordMap.insert(pair<string, int>(beginWord, n));
wordMap.insert(pair<string, int>(endWord, n + 1));
strings.push_back(beginWord);
strings.push_back(endWord);

queue<int> bfs_queue;

vector<bool> enqueued(n + 2);
vector<int> lengths(n + 2);
for (int i = 0; i < n; i++)
{
enqueued[i] = false;
lengths[i] = 0;
}

lengths[n] = 1;
enqueued[n] = true;
bfs_queue.push(n);

while (bfs_queue.size() > 0)
{
int current_id = bfs_queue.front();
bfs_queue.pop();
string current = strings[current_id];
int length = lengths[current_id];

for (int c = 0; c < current.length(); c++)
{
char backup = current[c];
for (char a = 'a'; a <= 'z'; a++)
{
current[c] = a;
unordered_map<string, int>::iterator probe = wordMap.find(current);
if (probe != wordMap.end())
{
int neighbor_id = probe->second;
if (neighbor_id == (n + 1))
{
return length + 1;
}
if (!enqueued[neighbor_id])
{
lengths[neighbor_id] = length + 1;
enqueued[neighbor_id] = true;
bfs_queue.push(neighbor_id);
}
}
}
current[c] = backup;
}
}

return 0;
}
};
}

}