Posts tagged as “BST”

花花酱 LeetCode 915. Partition Array into Disjoint Intervals

By zxi on September 30, 2018

Problem

Given an array A, partition it into two (contiguous) subarrays left and right so that:

Every element in left is less than or equal to every element in right.
left and right are non-empty.
left has the smallest possible size.

Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.

Example 1:

Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Note:

2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

Solution 1: BST

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua, 100 ms

class Solution {

public:

int partitionDisjoint(vector<int>& A) {

multiset<int> s(begin(A) + 1, end(A));

int left_max = A[0];

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

if (*begin(s) >= left_max) return i;

s.erase(s.equal_range(A[i]).first);

left_max = max(left_max, A[i]);

}

return -1;

}

};

Solution 2: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 28 ms

class Solution {

public:

int partitionDisjoint(vector<int>& A) {

int left_max = A[0];

int cur_max = A[0];

int left_len = 1;

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

if (A[i] < left_max) {

left_max = cur_max;

left_len = i + 1;

} else {

cur_max = max(cur_max, A[i]);

}

return left_len;

}

};

花花酱 LeetCode 855. Exam Room

By zxi on July 29, 2018

Problem

In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. (Also, if no one is in the room, then the student sits at seat number 0.)

Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room. It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.

Note:

1 <= N <= 10^9
ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

Solution: BST

Use a BST (ordered set) to track the current seatings.

Time Complexity:

init: O(1)

seat: O(P)

leave: O(logP)

Space complexity: O(P)

// Author: Huahua

// Running time: 24 ms

class ExamRoom {

public:

ExamRoom(int N): N_(N) {}

int seat() {

int p = 0;

int max_dist = s_.empty() ? 0 : *s_.begin();

auto left = s_.begin();

auto right = left;

while (left != s_.end()) {

++right;

int l = *left;

int r = right != s_.end() ? *right : (2 * (N_ - 1) - *left);

int d = (r - l) / 2;

if (d > max_dist) {

max_dist = d;

p = l + d;

}

left = right;

}

s_.insert(p);

return p;

}

void leave(int p) {

s_.erase(p);

}

private:

const int N_;

set<int> s_;

};

花花酱 LeetCode 701. Insert into a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:

/ \

2 7

/ \

1 3

And the value to insert: 5

You can return this binary search tree:

/ \

2 7

/ \ /

1 3 5

This tree is also valid:

/ \

2 7

/ \

1 3

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

TreeNode* insertIntoBST(TreeNode* root, int val) {

if (root == nullptr) return new TreeNode(val);

if (val > root->val)

root->right = insertIntoBST(root->right, val);

else

root->left = insertIntoBST(root->left, val);

return root;

}

};

花花酱 LeetCode 703. Kth Largest Element in a Stream

By zxi on July 12, 2018

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

Solution: BST / Min Heap

Time complexity: O(nlogk)

Space complexity: O(k)

C++ / BST

// Author: Huahua

// Running time: 32 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.insert(val);

if (s_.size() > k_)

s_.erase(s_.begin());

return *s_.begin();

}

private:

const int k_;

multiset<int> s_;

};

C++ / Min Heap

// Author: Huahua

// Running time: 28 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.push(val);

if (s_.size() > k_)

s_.pop();

return s_.top();

}

private:

const int k_;

priority_queue<int, vector<int>, greater<int>> s_; // min heap

};

花花酱 LeetCode 700. Search in a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

TreeNode* searchBST(TreeNode* root, int val) {

if (root == nullptr) return nullptr;

if (val == root->val)

return root;

else if (val > root->val)

return searchBST(root->right, val);

return searchBST(root->left, val);

}

};