online advertising

Saturday, April 2, 2016

LeetCode OJ - The Skyline Problem

Problem: 

Please find the problem here.

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: 

Please find the problem here.

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"

// https://leetcode.com/problems/word-ladder/

#include "LEET_WORD_LADDER.h"
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>

using namespace std;

namespace _LEET_WORD_LADDER
{
    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;
        }
    };
}

using namespace _LEET_WORD_LADDER;

int LEET_WORD_LADDER()
{
    Solution s;
    unordered_set<string> words;
    words.insert("a");
    words.insert("b");
    words.insert("c");
    cout << s.ladderLength("a", "c", words) << endl;
    return 0;
}