花花酱 LeetCode 164. Maximum Gap

By zxi on December 10, 2017

https://leetcode.com/problems/maximum-gap/description/

Problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

题目大意:

给你一个没有排序的正整数数组。输出排序后，相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。

Example:

Input: [5, 0, 4, 2, 12, 10]

Output: 5

Explanation:

Sorted: [0, 2, 4, 5, 10, 12]

max gap is 10 – 5 = 5

Idea:

Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.

桶排序。用n个桶来存放数字。对于每个桶，只跟踪存储最大值和最小值。

max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.

max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶（如果有）必须为空。

max gap = b[j].min – b[i].min

Time complexity: O(n)

时间复杂度: O(n)

Space complexity: O(n)

空间复杂度: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maximumGap(vector<int>& nums) {

const int n = nums.size();

if (n <= 1) return 0;

const auto mm = minmax_element(nums.begin(), nums.end());

const int range = *mm.second - *mm.first;

const int bin_size = range / n + 1;

vector<int> min_vals(n, INT_MAX);

vector<int> max_vals(n, INT_MIN);

for (const int num : nums) {

const int index = (num - *mm.first) / bin_size;

min_vals[index] = min(min_vals[index], num);

max_vals[index] = max(max_vals[index], num);

}

int max_gap = 0;

int prev_max = max_vals[0];

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

if (min_vals[i] != INT_MAX) {

max_gap = max(max_gap, min_vals[i] - prev_max);

prev_max = max_vals[i];

}

return max_gap;

}

};

花花酱 LeetCode 530. Minimum Absolute Difference in BST

By zxi on December 9, 2017

Link

Problem:

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

Output:

Explanation:

The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

Idea:

Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).

Solution:

C++ O(n) space

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

std::vector<int> sorted;

inorder(root, sorted);

int min_diff = sorted.back();

for (int i = 1; i < sorted.size(); ++i)

min_diff = min(min_diff, sorted[i] - sorted[i - 1]);

return min_diff;

}

private:

void inorder(TreeNode* root, std::vector<int>& sorted) {

if (!root) return;

inorder(root->left, sorted);

sorted.push_back(root->val);

inorder(root->right, sorted);

}

};

C++ O(h) space

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

min_diff_ = INT_MAX;

prev_ = nullptr;

inorder(root);

return min_diff_;

}

private:

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev_) min_diff_ = min(min_diff_, root->val - *prev_);

prev_ = &root->val;

inorder(root->right);

}

int* prev_;

int min_diff_;

};

Java

// Author: Huahua

// Runtime: 16 ms

class Solution {

public int getMinimumDifference(TreeNode root) {

prev_ = null;

min_diff_ = Integer.MAX_VALUE;

inorder(root);

return min_diff_;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

if (prev_ != null) min_diff_ = Math.min(min_diff_, root.val - prev_);

prev_ = root.val;

inorder(root.right);

}

private Integer prev_;

private int min_diff_;

}

Python

"""

Author: Huahua

Runtime: 92 ms

"""

class Solution(object):

def getMinimumDifference(self, root):

def inorder(root):

if not root: return

inorder(root.left)

if self.prev is not None: self.min_diff = min(self.min_diff, root.val - self.prev)

self.prev = root.val

inorder(root.right)

self.prev = None

self.min_diff = float('inf')

inorder(root)

return self.min_diff

Related Problems:

[解题报告] LeetCode 98. Validate Binary Search Tree

花花酱 LeetCode 732. My Calendar III

By zxi on December 6, 2017

Problem:

link: https://leetcode.com/problems/my-calendar-iii/description/

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

The number of calls to MyCalendarThree.book per test case will be at most 400.
In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].

Idea:

Similar to LeetCode 731 My Calendar II Use an ordered / tree map to track the number of event at current time.

For a new book event, increase the number of events at start, decrease the number of events at end.

Scan the timeline to find the maximum number of events.

Solution 1: Count Boundaries

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 116 ms

class MyCalendarThree {

public:

MyCalendarThree() {}

int book(int start, int end) {

++deltas_[start];

--deltas_[end];

int ans = 0;

int curr = 0;

for (const auto& kv : deltas_)

ans = max(ans, curr += kv.second);

return ans;

}

private:

map<int, int> deltas_;

};

Solution 2

C++

// Author: Huahua

// Runtime: 66 ms

class MyCalendarThree {

public:

MyCalendarThree() {

counts_[INT_MIN] = 0;

counts_[INT_MAX] = 0;

max_count_ = 0;

}

int book(int start, int end) {

auto l = prev(counts_.upper_bound(start)); // l->first < start

auto r = counts_.lower_bound(end); // r->first >= end

for (auto curr = l, next = curr; curr != r; curr = next) {

++next;

if (next->first > end)

counts_[end] = curr->second;

if (curr->first <= start && next->first > start)

max_count_ = max(max_count_, counts_[start] = curr->second + 1);

else

max_count_ = max(max_count_, ++curr->second);

}

return max_count_;

}

private:

map<int, int> counts_;

int max_count_;

};

Solution 3: Segment Tree

C++

// Author: Huahua

// Runtime: 63 ms (<95.65%)

class MyCalendarThree {

public:

MyCalendarThree(): max_count_(0) {

root_.reset(new Node(0, 100000000, 0));

}

int book(int start, int end) {

Add(start, end, root_.get());

return max_count_;

}

private:

struct Node {

Node(int l, int r, int count):l(l), m(-1), r(r), count(count){}

int l;

int m;

int r;

int count;

std::unique_ptr<Node> left;

std::unique_ptr<Node> right;

};

void Add(int start, int end, Node* root) {

if (root->m != -1) {

if (end <= root->m)

Add(start, end, root->left.get());

else if(start >= root->m)

Add(start, end, root->right.get());

else {

Add(start, root->m, root->left.get());

Add(root->m, end, root->right.get());

}

return;

}

if (start == root->l && end == root->r)

max_count_ = max(max_count_, ++root->count);

else if (start == root->l) {

root->m = end;

root->left.reset(new Node(start, root->m, root->count + 1));

root->right.reset(new Node(root->m, root->r, root->count));

max_count_ = max(max_count_, root->count + 1);

} else if(end == root->r) {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count + 1));

max_count_ = max(max_count_, root->count + 1);

} else {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count));

Add(start, end, root->right.get());

}

std::unique_ptr<Node> root_;

int max_count_;

};

Python3

"""

Author: Huahua

Runtime: 436 ms (<88.88%)

"""

class Node:

def __init__(self, l, r, count):

self.l = l

self.m = -1

self.r = r

self.count = count

self.left = None

self.right = None

class MyCalendarThree:

def __init__(self):

self.root = Node(0, 10**9, 0)

self.max = 0

def book(self, start, end):

self.add(start, end, self.root)

return self.max

def add(self, start, end, root):

if root.m != -1:

if end <= root.m: self.add(start, end, root.left)

elif start >= root.m: self.add(start, end, root.right)

else:

self.add(start, root.m, root.left)

self.add(root.m, end, root.right)

return

if start == root.l and end == root.r:

root.count += 1

self.max = max(self.max, root.count)

elif start == root.l:

root.m = end

root.left = Node(start, root.m, root.count + 1)

root.right = Node(root.m, root.r, root.count)

self.max = max(self.max, root.count + 1)

elif end == root.r:

root.m = start;

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count + 1)

self.max = max(self.max, root.count + 1)

else:

root.m = start

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count)

self.add(start, end, root.right)

Related Problems:

花花酱 LeetCode 740. Delete and Earn

By zxi on December 5, 2017

Problem:

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete everyelement equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]

Output: 6

Explanation:

Delete 4 to earn 4 points, consequently 3 is also deleted.

Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]

Output: 9

Explanation:

Delete 3 to earn 3 points, deleting both 2's and the 4.

Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.

9 total points are earned.

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

Idea:

Reduce the problem to House Robber Problem

Key observations: If we take nums[i]

We can safely take all of its copies.
We can’t take any of copies of nums[i – 1] and nums[i + 1]

This problem is reduced to 198 House Robber.

Houses[i] has all the copies of num whose value is i.

[3 4 2] -> [0 2 3 4], rob([0 2 3 4]) = 6

[2, 2, 3, 3, 3, 4] -> [0 2*2 3*3 4], rob([0 2*2 3*3 4]) = 9

Time complexity: O(n+r) reduction + O(r) solving rob = O(n + r)

Space complexity: O(r)

r = max(nums) – min(nums) + 1

Time complexity: O(n + r)

Space complexity: O(r)

Solution:

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int deleteAndEarn(vector<int>& nums) {

if (nums.empty()) return 0;

const auto range = minmax_element(nums.begin(), nums.end());

const int l = *(range.first);

const int r = *(range.second);

vector<int> points(r - l + 1, 0);

for (const int num : nums)

points[num - l] += num;

return rob(points);

}

private:

// From LeetCode 198. House Robber

int rob(const vector<int>& nums) {

int dp2 = 0;

int dp1 = 0;

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

int dp = max(dp2 + nums[i], dp1);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

Related Problem:

花花酱 LeetCode 198. House Robber

花花酱 LeetCode 198. House Robber

By zxi on December 5, 2017

Problem:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Idea:

Time complexity: O(n)

Space complexity: O(n) -> O(1)

Solution:

C++ / Recursion + Memorization

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

int rob(vector<int>& nums) {

const int n = nums.size();

m_ = vector<int>(n, -1);

return rob(nums, n - 1);

}

private:

int rob(const vector<int>& nums, int i) {

if (i < 0) return 0;

if (m_[i] >= 0) return m_[i];

return m_[i] = max(rob(nums, i - 2) + nums[i],

rob(nums, i - 1));

}

vector<int> m_;

};

C++ / DP

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int rob(vector<int>& nums) {

if (nums.empty()) return 0;

vector<int> dp(nums.size(), 0);

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

dp[i] = max((i > 1 ? dp[i - 2] : 0) + nums[i],

(i > 0 ? dp[i - 1] : 0));

return dp.back();

}

};

C++ / O(1) Space

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int rob(vector<int>& nums) {

if (nums.empty()) return 0;

int dp2 = 0;

int dp1 = 0;

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

int dp = max(dp2 + nums[i], dp1);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

Huahua's Tech Road

花花酱 LeetCode 164. Maximum Gap

花花酱 LeetCode 530. Minimum Absolute Difference in BST

花花酱 LeetCode 732. My Calendar III

Solution 1: Count Boundaries

C++

Solution 2

C++

Solution 3: Segment Tree

C++

Python3

花花酱 LeetCode 740. Delete and Earn

花花酱 LeetCode 198. House Robber