花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

By zxi on December 29, 2019

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

Each tree has at most 5000 nodes.
Each node’s value is between [-10^5, 10^5].

Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

C++

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

int i = 0;

int j = 0;

while (m.size() != t1.size() + t2.size()) {

if (j == t2.size()) m.push_back(t1[i++]);

else if (i == t1.size()) m.push_back(t2[j++]);

else m.push_back(t1[i] < t2[j] ? t1[i++] : t2[j++]);

}

return m;

}

};

C++/STL

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

std::merge(begin(t1), end(t1), begin(t2), end(t2), back_inserter(m));

return m;

}

};

花花酱 LeetCode 148. Sort List

By zxi on July 26, 2018

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution: Merge Sort

Top-down (recursion)

Time complexity: O(nlogn)

Space complexity: O(logn)

C++

// Author: Huahua

// Running time: 32 ms

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

fast = fast->next->next;

slow = slow->next;

}

ListNode* mid = slow->next;

slow->next = nullptr; // Break the list.

return merge(sortList(head), sortList(mid));

}

private:

ListNode* merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 6 ms

class Solution {

public ListNode sortList(ListNode head) {

if (head == null || head.next == null) return head;

ListNode slow = head;

ListNode fast = head.next;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

}

ListNode mid = slow.next;

slow.next = null;

return merge(sortList(head), sortList(mid));

}

private ListNode merge(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null && l2 != null) {

if (l1.val > l2.val) {

ListNode tmp = l1;

l1 = l2;

l2 = tmp;

}

tail.next = l1;

l1 = l1.next;

tail = tail.next;

}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

}

Python3

# Author: Huahua, 232 ms

class Solution:

def sortList(self, head):

def merge(l1, l2):

dummy = ListNode(0)

tail = dummy

while l1 and l2:

if l1.val > l2.val: l1, l2 = l2, l1

tail.next = l1

l1 = l1.next

tail = tail.next

tail.next = l1 if l1 else l2

return dummy.next

if not head or not head.next: return head

slow = head

fast = head.next

while fast and fast.next:

fast = fast.next.next

slow = slow.next

mid = slow.next

slow.next = None

return merge(self.sortList(head), self.sortList(mid))

bottom up

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

int len = 1;

ListNode* cur = head;

while (cur = cur->next) ++len;

ListNode dummy(0);

dummy.next = head;

ListNode* l;

ListNode* r;

ListNode* tail;

for (int n = 1; n < len; n <<= 1) {

cur = dummy.next; // partial sorted head

tail = &dummy;

while (cur) {

l = cur;

r = split(l, n);

cur = split(r, n);

auto merged = merge(l, r);

tail->next = merged.first;

tail = merged.second;

}

return dummy.next;

}

private:

// Splits the list into two parts, first n element and the rest.

// Returns the head of the rest.

ListNode* split(ListNode* head, int n) {

while (--n && head)

head = head->next;

ListNode* rest = head ? head->next : nullptr;

if (head) head->next = nullptr;

return rest;

}

// Merges two lists, returns the head and tail of the merged list.

pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

while (tail->next) tail = tail->next;

return {dummy.next, tail};

}

};

花花酱 LeetCode 775. Global and Local Inversions

By zxi on July 9, 2018

Problem

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

Solution1: Brute Force (TLE)

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: TLE (208/208 test cases passed)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

const int n = A.size();

int local = 0;

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

if (A[i] > A[i + 1]) ++local;

int global = 0;

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

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

if (A[i] > A[j] && ++global > local) return false;

return global == local;

}

};

Solution2: MergeSort

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 52 ms (<96.42%)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

const int n = A.size();

int local = 0;

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

if (A[i] > A[i + 1]) ++local;

tmp = vector<int>(n);

int global = mergeSort(A, 0, n - 1);

return global == local;

}

private:

vector<int> tmp;

int mergeSort(vector<int>& A, int l, int r) {

if (l >= r) return 0;

const int len = r - l + 1;

int m = (r - l) / 2 + l;

int inv = mergeSort(A, l, m) + mergeSort(A, m + 1, r);

int i = l;

int j = m + 1;

int k = 0;

while (i <= m && j <= r) {

if (A[i] <= A[j]) {

tmp[k++] = A[i++];

} else {

tmp[k++] = A[j++];

inv += m - i + 1;

}

while (i <= m) tmp[k++] = A[i++];

while (j <= r) tmp[k++] = A[j++];

std::copy(tmp.begin(), tmp.begin() + len, A.begin() + l);

return inv;

}

};

// Author: Huahua

// Running time: 208 ms

public class Solution {

public bool IsIdealPermutation(int[] A) {

var n = A.Length;

var localInv = 0;

for (var i = 1; i < n; ++i)

if (A[i] < A[i - 1]) ++localInv;

tmp = new int[n];

var globalInv = MergeSort(A, 0, n - 1);

return localInv == globalInv;

}

private int[] tmp;

private int MergeSort(int[] A, int l, int r) {

if (l >= r) return 0;

int m = (r - l) / 2 + l;

int inv = MergeSort(A, l, m) + MergeSort(A, m + 1, r);

int i = l;

int j = m + 1;

int k = 0;

while (i <= m && j <= r) {

if (A[i] <= A[j]) {

tmp[k++] = A[i++];

} else {

inv += m - i + 1;

tmp[k++] = A[j++];

}

while (i <= m) tmp[k++] = A[i++];

while (j <= r) tmp[k++] = A[j++];

Array.Copy(tmp, 0, A, l, k);

return inv;

}

Solution3: Input Property

Input is a permutation of [0, 1, …, N – 1]

Time Complexity: O(n)

Space Complexity: O(1)

// Author: Huahua

// Running time: 40 ms (<99.26%)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

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

if (abs(A[i] - i) > 1) return false;

return true;

}

};

Posts tagged as “mergesort”

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

Solution: Inorder traversal + Merge Sort

C++

C++/STL

花花酱 LeetCode 148. Sort List

Problem

Solution: Merge Sort

C++

Java

Python3

花花酱 LeetCode 775. Global and Local Inversions

Problem

Solution1: Brute Force (TLE)

Solution2: MergeSort

Solution3: Input Property