Posts tagged as “BST”

花花酱 LeetCode 530. Minimum Absolute Difference in BST

By zxi on December 9, 2017

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 98. Validate Binary Search Tree

By zxi on November 11, 2017

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

/ \

1 3

Binary tree [2,1,3], return true.

Example 2:

/ \

2 3

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, LLONG_MIN, LLONG_MAX);

}

private:

bool isValidBST(TreeNode* root, long min_val, long max_val) {

if (!root) return true;

if (root->val <= min_val || root->val >= max_val)

return false;

return isValidBST(root->left, min_val, root->val)

&& isValidBST(root->right, root->val, max_val);

}

};

C++/nullable

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, nullptr, nullptr);

}

private:

bool isValidBST(TreeNode* root, int* min_val, int* max_val) {

if (!root) return true;

if ((min_val && root->val <= *min_val)

||(max_val && root->val >= *max_val))

return false;

return isValidBST(root->left, min_val, &root->val)

&& isValidBST(root->right, &root->val, max_val);

}

};

Java/nullable

// Author: Huahua

// Running time: 1 ms

class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, null, null);

}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {

if (root == null) return true;

if ((min != null && root.val <= min)

||(max != null && root.val >= max))

return false;

return isValidBST(root.left, min, root.val)

&& isValidBST(root.right, root.val, max);

}

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isValidBST(TreeNode* root) {

prev_ = nullptr;

return inOrder(root);

}

private:

TreeNode* prev_;

bool inOrder(TreeNode* root) {

if (!root) return true;

if (!inOrder(root->left)) return false;

if (prev_ && root->val <= prev_->val) return false;

prev_ = root;

return inOrder(root->right);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private TreeNode prev;

public boolean isValidBST(TreeNode root) {

prev = null;

return inOrder(root);

}

private boolean inOrder(TreeNode root) {

if (root == null) return true;

if (!inOrder(root.left)) return false;

if (prev != null && root.val <= prev.val) return false;

prev = root;

return inOrder(root.right);

}

Solution 2: BST

C++

// Author: Huahua

// Runtime: 228 ms

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

set<int> xs;

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

int x = flowers[i];

auto r = xs.insert(x).first;

auto l = r;

if (++r != xs.end() && *r == x + k + 1) return i + 1;

if (l != xs.begin() && *(--l) == x - k - 1) return i + 1;

}

return -1;

}

};

Solution 3: Buckets

C++

// Author: Huahua

// Runtime: 196 ms (better than 94%)

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

++k;

int bs = (n + k - 1) / k;

vector<int> lows(bs, INT_MAX);

vector<int> highs(bs, INT_MIN);

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

int x = flowers[i];

int p = x / k;

if (x < lows[p]) {

lows[p] = x;

if (p > 0 && highs[p - 1] == x - k) return i + 1;

}

if (x > highs[p]) {

highs[p] = x;

if (p < bs - 1 && lows[p + 1] == x + k) return i + 1;

}

return -1;

}

};

Solution 1: TLE with latest test cases

C++

// Author: Huahua

// Runtime: 192 ms (better than 97.85%)

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

std::unique_ptr<char[]> f(new char[n+1]);

memset(f.get(), 0, (n + 1)*sizeof(char));

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

if (IsValid(flowers[i], k, n, f.get()))

return i + 1;

return -1;

}

private:

bool IsValid(int x, int k, int n, char* f) {

f[x] = 1;

if (x + k + 1 <= n && f[x + k + 1]) {

bool valid = true;

for (int i = 1; i <= k; ++i)

if (f[x + i]) {

valid = false;

break;

}

if (valid) return true;

}

if (x - k - 1 > 0 && f[x - k - 1]) {

for (int i = 1; i <= k; ++i)

if (f[x - i]) return false;

return true;

}

return false;

}

};

Java

// Author: Huahua

// Runtime: 17 ms

class Solution {

public int kEmptySlots(int[] flowers, int k) {

int n = flowers.length;

if (n == 0 || k >= n) return -1;

int[] f = new int[n + 1];

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

if (IsValid(flowers[i], k, n, f))

return i + 1;

return -1;

}

private boolean IsValid(int x, int k, int n, int[] f) {

f[x] = 1;

if (x + k + 1 <= n && f[x + k + 1] == 1) {

boolean valid = true;

for (int i = 1; i <= k; ++i)

if (f[x + i] == 1) {

valid = false;

break;

}

if (valid) return true;

}

if (x - k - 1 > 0 && f[x - k - 1] == 1) {

for (int i = 1; i <= k; ++i)

if (f[x - i] == 1) return false;

return true;

}

return false;

}

Python

"""

Author: Huahua

Runtime: 398 ms

"""

class Solution:

def kEmptySlots(self, flowers, k):

n = len(flowers)

f = [0] * (n + 1)

i = 0

def isValid(x, k, n, f):

f[x] = 1

if x + k + 1 <= n and f[x + k + 1] == 1:

valid = True

for i in range(k):

if f[x + i + 1] == 1:

valid = False

break

if valid: return True

if x - k - 1 > 0 and f[x - k - 1] == 1:

for i in range(k):

if f[x - i - 1] == 1:

return False

return True

return False

for x in flowers:

i += 1

if isValid(x, k, n, f): return i

return -1

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

By zxi on September 12, 2017

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) – Add a integer number from the data stream to the data structure.
double findMedian() – Return the median of all elements so far.

For example:

addNum(1)

addNum(2)

findMedian() = 1.5

addNum(3)

findMedian() = 2

Idea:

Min/Max heap
Balanced binary search tree

Time Complexity:

add(num): O(logn)

findMedian(): O(logn)

Solution1:

// Author: Huahua

// Running Time: 152 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder() {}

// l_.size() >= r_.size()

void addNum(int num) {

if (l_.empty() || num <= l_.top()) {

l_.push(num);

} else {

r_.push(num);

}

// Step 2: Balence left/right

if (l_.size() < r_.size()) {

l_.push(r_.top());

r_.pop();

} else if (l_.size() - r_.size() == 2) {

r_.push(l_.top());

l_.pop();

}

double findMedian() {

if (l_.size() > r_.size()) {

return static_cast<double>(l_.top());

} else {

return (static_cast<double>(l_.top()) + r_.top()) / 2;

}

private:

priority_queue<int, vector<int>, less<int>> l_; // max-heap

priority_queue<int, vector<int>, greater<int>> r_; // min-heap

};

Solution 2:

// Author: Huahua

// Running time: 172 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder(): l_(m_.cend()), r_(m_.cend()) {}

// O(logn)

void addNum(int num) {

if (m_.empty()) {

l_ = r_ = m_.insert(num);

return;

}

m_.insert(num);

const size_t n = m_.size();

if (n & 1) {

// odd number

if (num >= *r_) {

l_ = r_;

} else {

// num < *r_, l_ could be invalidated

l_ = --r_;

}

} else {

if (num >= *r_)

++r_;

else

--l_;

}

// O(1)

double findMedian() {

return (static_cast<double>(*l_) + *r_) / 2;

}

private:

multiset<int> m_;

multiset<int>::const_iterator l_; // current left median

multiset<int>::const_iterator r_; // current right median

};

Related Problems

Posts tagged as “BST”

花花酱 LeetCode 530. Minimum Absolute Difference in BST

花花酱 LeetCode 98. Validate Binary Search Tree

Solution 1

C++/long

C++/nullable

Java/nullable

Solution 2

C++

Java

Related Problem

花花酱 LeetCode 683. K Empty Slots

Solution 2: BST

C++

Solution 3: Buckets

C++

Solution 1: TLE with latest test cases

C++

Java

Python

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