online advertising

Saturday, March 19, 2016

LeetCode OJ - Minimum Height Trees

Problem: 

Please find the problem here.

Analysis:

As a disclaimer, I cheated. I knew people are talking about an $ O(n) $ algorithm. So I focused my energy thinking about a linear algorithm and therefore I found it.

A simple 'brute force' solution is to do a BFS starting from every possible root and record the heights, that will allow us to pick the right node. This is a $ O(n^2) $ algorithm.

The question here is, how do I use a one pass algorithm to know all the heights?

Solution:

Turn out one pass is not enough for me, I used two passes. Let me describe how it works.

At first, I thought I would use BFS because that will give me the shortest path. Turn out, as the given graph is a tree, doing DFS will also the same shortest path tree (after all, there is only one path between any pair), and DFS give me more flexibility with message passing, so I chose DFS.

Imagine in a every node, we have a sign post saying the longest path we have following the direction, then we can simply read the answer by going through each node and take the maximum out of the sign post values, our goal is to compute the sign post values.

In a DFS, the sign post value can be readily computed for all but the parent path. Just record for each child what was the height of the subtree and that's all. This is the first pass in the code.

In the second pass, we compute the cost for the parent path. For that purpose, we do another pass DFS. For the root node, it has no parent and therefore it is easy to imagine a fake parent -1 with cost 0 for it. For all other node B with parent node A, the parent cost for node B is the maximum of all neighbors (including parent) of A with B itself excluded.

If we keep the full sign post, then we will need to do an actual maximum computation when we want to extract the result. Note that we only need a few operations for the sign post.

Add a cost pointing to a particular direction.
Find the maximum over all directions.
Find the maximum over all directions except one particular direction.

This is easily implemented with just keeping track of the maximum, the maximum direction, and the second maximum. That is our summary class in the code.

Without further ado, this is the code:

Code:

#include "stdafx.h"

// https://leetcode.com/problems/minimum-height-trees/

#include "LEET_MINIMUM_HEIGHT_TREES.h"
#include <list>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

namespace _LEET_MINIMUM_HEIGHT_TREES
{
    class Solution {
    private:
        class summary
        {
        public:
            int max;
            int max_id;
            int second_max;
            summary()
            {
                max = second_max = 0;
                max_id = -1;
            }

            void add(int id, int cost)
            {
                if (cost > max)
                {
                    second_max = max;
                    max = cost;
                    max_id = id;
                }
                else if (cost > second_max)
                {
                    second_max = cost;
                }
            }

            int get_max()
            {
                return this->max;
            }

            int get_max_but_id(int id)
            {
                if (id == this->max_id)
                {
                    return this->second_max;
                }
                else
                {
                    return this->max;
                }
            }
        };
    public:
        void first_pass(int parent, int node, vector<vector<int>>& adjacency_list, vector<summary>& summaries)
        {
            for (size_t i = 0; i < adjacency_list[node].size(); i++)
            {
                int neighbor = adjacency_list[node][i];
                if (neighbor != parent)
                {
                    first_pass(node, neighbor, adjacency_list, summaries);
                    summaries[node].add(neighbor, 1 + summaries[neighbor].get_max());
                }
            }
        }

        void second_pass(int parent, int node, int parent_cost, vector<vector<int>>& adjacency_list, vector<summary>& summaries)
        {
            summaries[node].add(parent, parent_cost);
            for (size_t i = 0; i < adjacency_list[node].size(); i++)
            {
                int neighbor = adjacency_list[node][i];
                if (neighbor != parent)
                {
                    second_pass(node, neighbor, 1 + summaries[node].get_max_but_id(neighbor), adjacency_list, summaries);
                }
            }
        }

        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges)
        {
            vector<vector<int>> adjacency_list(n);
            vector<summary> summaries(n);
            for (size_t e = 0; e < edges.size(); e++)
            {
                adjacency_list[edges[e].first].push_back(edges[e].second);
                adjacency_list[edges[e].second].push_back(edges[e].first);
            }

            first_pass(-1, 0, adjacency_list, summaries);
            second_pass(-1, 0, 0, adjacency_list, summaries);

            vector<int> result;
            int min_max = 100000;
            for (int i = 0; i < n; i++)
            {
                min_max = min(min_max, summaries[i].get_max());
            }
            for (int i = 0; i < n; i++)
            {
                if (summaries[i].get_max() == min_max)
                {
                    result.push_back(i);
                }
            }
            return result;
        }
    };
};

using namespace _LEET_MINIMUM_HEIGHT_TREES;

int LEET_MINIMUM_HEIGHT_TREES()
{
    Solution solution;
    vector<pair<int, int>> edges;

    edges.push_back(pair<int, int>(0, 1));
    edges.push_back(pair<int, int>(1, 3));
    edges.push_back(pair<int, int>(1, 4));
    edges.push_back(pair<int, int>(0, 2));
    edges.push_back(pair<int, int>(4, 5));

    solution.findMinHeightTrees(6, edges);
    return 0;
}

No comments :

Post a Comment