Posts published in “Tree”

花花酱 LeetCode 684. Redundant Connection

By zxi on September 28, 2017

https://leetcode.com/problems/redundant-connection/description/

Problem:

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

Input: [[1,2], [1,3], [2,3]]

Output: [2,3]

Explanation: The given undirected graph will be like this:

/ \

2 - 3

Example 2:

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output: [1,4]

Explanation: The given undirected graph will be like this:

5 - 1 - 2

| |

4 - 3

Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Idea:
DFS / Union-Find

Solutions:

C++ / DFS

// Author: Huahua

// Time Complexity: O(n^2)

// Running Time: 22 ms

class Solution {

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

unordered_map<int, vector<int>> graph;

for (const auto& edge : edges) {

int u = edge[0];

int v = edge[1];

unordered_set<int> visited;

if (hasPath(u, v, graph, visited))

return edge;

graph[u].push_back(v);

graph[v].push_back(u);

}

return {};

}

private:

bool hasPath(int curr,

int goal,

const unordered_map<int, vector<int>>& graph,

unordered_set<int>& visited) {

if (curr == goal) return true;

visited.insert(curr);

if (!graph.count(curr) || !graph.count(goal)) return false;

for (int next : graph.at(curr)) {

if (visited.count(next)) continue;

if (hasPath(next, goal, graph, visited)) return true;

}

return false;

}

};

C++ / Union Find

// Author: Huahua

// Running time: 6 ms

class UnionFindSet {

public:

UnionFindSet(int n) {

ranks_ = vector<int>(n + 1, 0);

parents_ = vector<int>(n + 1, 0);

for (int i = 0; i < parents_.size(); ++i)

parents_[i] = i;

}

// Merge sets that contains u and v.

// Return true if merged, false if u and v are already in one set.

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

// Meger low rank tree into high rank tree

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pv] += 1;

}

return true;

}

// Get the root of u.

int Find(int u) {

// Compress the path during traversal

if (u != parents_[u])

parents_[u] = Find(parents_[u]);

return parents_[u];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

class Solution {

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

UnionFindSet s(edges.size());

for(const auto& edge: edges)

if (!s.Union(edge[0], edge[1]))

return edge;

return {};

}

};

Java / Union Find

// Author: Huahua

// Runtime: 6 ms

class Solution {

class UnionFindSet {

private int[] parents_;

private int[] ranks_;

public UnionFindSet(int n) {

parents_ = new int[n + 1];

ranks_ = new int[n + 1];

for (int i = 0; i < parents_.length; ++i) {

parents_[i] = i;

ranks_[i] = 1;

}

public boolean Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

public int Find(int u) {

while (parents_[u] != u) {

parents_[u] = parents_[parents_[u]];

u = parents_[u];

}

return u;

}

public int[] findRedundantConnection(int[][] edges) {

UnionFindSet s = new UnionFindSet(edges.length);

for (int[] edge : edges)

if (!s.Union(edge[0], edge[1]))

return edge;

return null;

}

Python: Union Find

"""

Author: Huahua

Running Time: 66 ms

"""

class Solution:

def findRedundantConnection(self, edges):

p = [0]*(len(edges) + 1)

s = [1]*(len(edges) + 1)

def find(u):

while p[u] != u:

p[u] = p[p[u]]

u = p[u]

return u

for u, v in edges:

if p[u] == 0: p[u] = u

if p[v] == 0: p[v] = v

pu, pv = find(u), find(v)

if pu == pv: return [u, v]

if s[pv] > s[pu]: u, v = v, u

p[pv] = pu

s[pu] += s[pv]

return []

Python / Union Find V2

"""

Author: Huahua

Runtime: 59 ms (<92.42%)

"""

class UnionFindSet:

def __init__(self, n):

self._parents = [i for i in range(n + 1)]

self._ranks = [1 for i in range(n + 1)]

def find(self, u):

while u != self._parents[u]:

self._parents[u] = self._parents[self._parents[u]]

u = self._parents[u]

return u

def union(self, u, v):

pu, pv = self.find(u), self.find(v)

if pu == pv: return False

if self._ranks[pu] < self._ranks[pv]:

self._parents[pu] = pv

elif self._ranks[pu] > self._ranks[pv]:

self._parents[pv] = pu

else:

self._parents[pv] = pu

self._ranks[pu] += 1

return True

class Solution:

def findRedundantConnection(self, edges):

s = UnionFindSet(len(edges))

for edge in edges:

if not s.union(edge[0], edge[1]): return edge

return None

ndSet(len(edges))

for edge in edges:

if not s.union(edge[0], edge[1]): return edge

return None

花花酱 LeetCode 218. The Skyline Problem

By zxi on September 22, 2017

Problem:

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

The number of buildings in any input list is guaranteed to be in the range [0, 10000].
The input list is already sorted in ascending order by the left x position Li.
The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Idea:

Sweep line

Time Complexity:

O(nlogn)

Space Complexity:

O(n)

Solution1: Heap

C++

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

// events, x, h, id, type (1=entering, -1=leaving)

vector<Event> events;

int id = 0;

for (const auto& b : buildings) {

events.push_back(Event{id, b[0], b[2], 1});

events.push_back(Event{id, b[1], b[2], -1});

++id;

}

// Sort events by x

sort(events.begin(), events.end());

// Init the heap

MaxHeap heap(buildings.size());

vector<pair<int, int>> ans;

// Process all the events

for (const auto& event: events) {

int x = event.x;

int h = event.h;

int id = event.id;

int type = event.type;

if (type == 1) {

if (h > heap.Max())

ans.emplace_back(x, h);

heap.Add(h, id);

} else {

heap.Remove(id);

if (h > heap.Max())

ans.emplace_back(x, heap.Max());

}

return ans;

}

private:

struct Event {

int id;

int x;

int h;

int type;

// sort by x+, type-, h,

bool operator<(const Event& e) const {

if (x == e.x)

// Entering event h from large to small

// Leaving event h from small to large

return type * h > e.type * e.h;

return x < e.x;

}

};

class MaxHeap {

public:

MaxHeap(int max_items):

idx_(max_items, -1), vals_(max_items), size_(0) {}

// Add an item into the heap. O(log(n))

void Add(int key, int id) {

idx_[id] = size_;

vals_[size_] = {key, id};

++size_;

HeapifyUp(idx_[id]);

}

// Remove an item. O(log(n))

void Remove(int id) {

int idx_to_evict = idx_[id];

// swap with the last element

SwapNode(idx_to_evict, size_ - 1);

--size_;

HeapifyDown(idx_to_evict);

}

bool Empty() const {

return size_ == 0;

}

// Return the max of heap

int Max() const {

return Empty() ? 0 : vals_.front().first;

}

private:

void SwapNode(int i, int j) {

if (i == j) return;

std::swap(idx_[vals_[i].second], idx_[vals_[j].second]);

std::swap(vals_[i], vals_[j]);

}

void HeapifyUp(int i) {

while (i != 0) {

int p = (i - 1) / 2;

if (vals_[i].first <= vals_[p].first)

return;

SwapNode(i, p);

i = p;

}

// Make the heap valid again. O(log(n))

void HeapifyDown(int i) {

while (true) {

int c1 = i*2 + 1;

int c2 = i*2 + 2;

// No child

if (c1 >= size_) return;

// Get the index of the max child

int c = (c2 < size_

&& vals_[c2].first > vals_[c1].first ) ? c2 : c1;

// If key[c] is greater than key[i], swap them and

// continue to HeapifyDown(c)

if (vals_[c].first <= vals_[i].first)

return;

SwapNode(c, i);

i = c;

}

// {key, id}

vector<pair<int,int>> vals_;

// Index of the i-th item in vals_

vector<int> idx_;

int size_;

};

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

// Author: Huahua

// Running time: 91 ms (beats 79.1%)

class Solution {

private MaxHeap heap;

public List<int[]> getSkyline(int[][] buildings) {

int n = buildings.length;

// {x, h, id}

ArrayList<int[]> es = new ArrayList<int[]>();

for (int i = 0; i < n; ++i) {

es.add(new int[]{ buildings[i][0], buildings[i][2], i});

es.add(new int[]{ buildings[i][1], -buildings[i][2], i});

}

es.sort((e1, e2) -> {

return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0]; });

List<int[]> ans = new ArrayList<int[]>();

heap = new MaxHeap(n);

for (int[] e : es) {

int x = e[0];

int h = e[1];

int id = e[2];

Boolean entering = h > 0;

h = Math.abs(h);

if (entering) {

if (h > heap.max())

ans.add(new int[]{x, h});

heap.add(h, id);

} else {

heap.remove(id);

if (h > heap.max())

ans.add(new int[]{x, heap.max()});

}

return ans;

}

private class MaxHeap {

// (key, id)

private List<int[]> nodes;

// idx[i] = index of building[i] in nodes

private int[] idx;

public MaxHeap(int size) {

idx = new int[size];

nodes = new ArrayList<int[]>();

}

public void add(int key, int id) {

idx[id] = nodes.size();

nodes.add(new int[]{key, id});

heapifyUp(idx[id]);

}

public void remove(int id) {

int idx_to_evict = idx[id];

swapNode(idx_to_evict, nodes.size() - 1);

idx[id] = -1;

nodes.remove(nodes.size() - 1);

heapifyUp(idx_to_evict);

heapifyDown(idx_to_evict);

}

public Boolean empty() {

return nodes.isEmpty();

}

public int max() {

return empty() ? 0 : nodes.get(0)[0];

}

private void heapifyUp(int i) {

while (i != 0) {

int p = (i - 1) / 2;

if (nodes.get(i)[0] <= nodes.get(p)[0])

return;

swapNode(i, p);

i = p;

}

private void swapNode(int i, int j) {

int tmpIdx = idx[nodes.get(i)[1]];

idx[nodes.get(i)[1]] = idx[nodes.get(j)[1]];

idx[nodes.get(j)[1]] = tmpIdx;

int[] tmpNode = nodes.get(i);

nodes.set(i, nodes.get(j));

nodes.set(j, tmpNode);

}

private void heapifyDown(int i) {

while (true) {

int c1 = i*2 + 1;

int c2 = i*2 + 2;

if (c1 >= nodes.size()) return;

int c = (c2 < nodes.size()

&& nodes.get(c2)[0] > nodes.get(c1)[0]) ? c2 : c1;

if (nodes.get(c)[0] <= nodes.get(i)[0])

return;

swapNode(c, i);

i = c;

}

Solution 2: Multiset

C++

// Author: Huahua

// Time Complexity: O(nlogn)

// Space Complexity: O(n)

// Running Time: 22 ms

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

typedef pair<int, int> Event;

// events, x, h

vector<Event> es;

hs_.clear();

for (const auto& b : buildings) {

es.emplace_back(b[0], b[2]);

es.emplace_back(b[1], -b[2]);

}

// Sort events by x

sort(es.begin(), es.end(), [](const Event& e1, const Event& e2){

if (e1.first == e2.first) return e1.second > e2.second;

return e1.first < e2.first;

});

vector<pair<int, int>> ans;

// Process all the events

for (const auto& e: es) {

int x = e.first;

bool entering = e.second > 0;

int h = abs(e.second);

if (entering) {

if (h > this->maxHeight())

ans.emplace_back(x, h);

hs_.insert(h);

} else {

hs_.erase(hs_.equal_range(h).first);

if (h > this->maxHeight())

ans.emplace_back(x, this->maxHeight());

}

return ans;

}

private:

int maxHeight() const {

if (hs_.empty()) return 0;

return *hs_.rbegin();

}

multiset<int> hs_;

};

花花酱 LeetCode 677. Map Sum Pairs

By zxi on September 18, 2017

https://leetcode.com/problems/map-sum-pairs/description/

Problem:

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null

Input: sum("ap"), Output: 3

Input: insert("app", 2), Output: Null

Input: sum("ap"), Output: 5

Idea:

Prefix tree

Solution 1

// Author: Huahua

// Running time: 3 ms

class MapSum {

public:

/** Initialize your data structure here. */

MapSum() {}

void insert(const string& key, int val) {

int inc = val;

if (vals_.count(key)) {

inc -= vals_[key];

}

vals_[key] = val;

for (int i = 1; i <= key.length(); ++i)

sums_[key.substr(0,i)] += inc;

}

int sum(const string& prefix) {

return sums_[prefix];

}

private:

unordered_map<string, int> vals_;

unordered_map<string, int> sums_;

};

Solution 2:

class MapSum {

public:

/** Initialize your data structure here. */

MapSum() {}

void insert(string key, int val) {

int inc = val - vals_[key];

Trie* p = &root;

for (const char c : key) {

if (!p->children[c])

p->children[c] = new Trie();

p->children[c]->sum += inc;

p = p->children[c];

}

vals_[key] = val;

}

int sum(string prefix) {

Trie* p = &root;

for (const char c : prefix) {

if (!p->children[c]) return 0;

p = p->children[c];

}

return p->sum;

}

private:

struct Trie {

Trie():children(128, nullptr), sum(0){}

~Trie() {

for (auto child : children)

if (child) delete child;

children.clear();

}

vector<Trie*> children;

int sum;

};

Trie root; // dummy root

unordered_map<string, int> vals_; // key -> val

};

with std::unique_ptr

// Author: Huahua

// Running time: 5 ms

class MapSum {

public:

/** Initialize your data structure here. */

MapSum(): root_(new Trie()) {}

void insert(string key, int val) {

int inc = val - vals_[key];

Trie* p = root_.get();

for (const char c : key) {

if (!p->children[c])

p->children[c] = new Trie();

p->children[c]->sum += inc;

p = p->children[c];

}

vals_[key] = val;

}

int sum(string prefix) {

Trie* p = root_.get();

for (const char c : prefix) {

if (!p->children[c]) return 0;

p = p->children[c];

}

return p->sum;

}

private:

struct Trie {

Trie():children(128, nullptr), sum(0){}

~Trie() {

for (auto child : children)

if (child) {

delete child;

child = nullptr;

}

children.clear();

}

vector<Trie*> children;

int sum;

};

std::unique_ptr<Trie> root_;

unordered_map<string, int> vals_; // key -> val

};

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

By zxi on September 17, 2017

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

/ \

2 3

/ \

4 5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Idea:

Recursion

Time Complexity O(n)

Solution 1: ASCII

C++

// Author: Huahua

// Running time: 39 ms

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

void serialize(TreeNode* root, ostringstream& out) {

if (!root) {

out << "# ";

return;

}

out << root->val << " ";

serialize(root->left, out);

serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

string val;

in >> val;

if (val == "#") return nullptr;

TreeNode* root = new TreeNode(stoi(val));

root->left = deserialize(in);

root->right = deserialize(in);

return root;

}

};

Solution 2: Binary

C++

// Author: Huahua

// Running time: 23 ms (beat 98.07%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, ostringstream& out) {

char status = 0;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

out.write(&status, sizeof(char));

if (!root) return;

out.write(reinterpret_cast<char*>(&(root->val)), sizeof(root->val));

if (root->left) serialize(root->left, out);

if (root->right) serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

char status;

in.read(&status, sizeof(char));

if (!status & ROOT) return nullptr;

auto root = new TreeNode(0);

in.read(reinterpret_cast<char*>(&root->val), sizeof(root->val));

root->left = (status & LEFT) ? deserialize(in) : nullptr;

root->right = (status & RIGHT) ? deserialize(in) : nullptr;

return root;

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

C++ (string)

// Author: Huahua

// Running time: 23 ms (<98.13%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

string s;

serialize(root, s);

return s;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

int pos = 0;

return deserialize(data, pos);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, string& s) {

char status = ROOT_NULL;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

s.push_back(status);

if (!root) return;

s.append(reinterpret_cast<char*>(&root->val), sizeof(root->val));

if (root->left) serialize(root->left, s);

if (root->right) serialize(root->right, s);

}

TreeNode* deserialize(const string& s, int& pos) {

char status = s[pos++];

if (!status) return nullptr;

TreeNode* root = new TreeNode(0);

memcpy(&root->val, s.data() + pos, sizeof(root->val));

pos += sizeof(root->val);

root->left = (status & LEFT) ? deserialize(s, pos) : nullptr;

root->right = (status & RIGHT) ? deserialize(s, pos) : nullptr;

return root;

}

};

Posts published in “Tree”

花花酱 LeetCode 684. Redundant Connection

花花酱 LeetCode 218. The Skyline Problem

Solution1: Heap

C++

Java

Solution 2: Multiset

C++

花花酱 LeetCode 677. Map Sum Pairs

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)