Notes and typical questions for Divide & Conquer related questions
Placeholder
LC 21. Merge Two Sorted Lists
Optimal Answerarrow-up-right. TC: O(m+n)O(m+n)O(m+n), SC: O(1)O(1)O(1)
LC 148. Sort List
Approach 1 with recursive merge sort: Answerarrow-up-right. TC: O(n∗logn)O(n*logn)O(n∗logn), SC: O(logn)O(logn)O(logn)
👍 🔴 Approach 2 with iterative idea and SC O(1): https://leetcode.com/problems/sort-list/solutions/46712/bottom-to-upnot-recurring-with-o1-space-anpva/comments/151523/arrow-up-right
⚪ LC 427. Construct Quad Tree
Optimal Answerarrow-up-right.
TC: O(4log2N)=O(Nlog24)=O(N2)O(4^{log_2{N}}) = O(N^{log_24}) = O(N^2)O(4log2N)=O(Nlog24)=O(N2)
SC: O(log2N)O(log_2N)O(log2N)
LC 108. Convert Sorted Array to Binary Search Tree
Optimal Answerarrow-up-right. TC: O(n)O(n)O(n), SC: O(log(n))O(log(n))O(log(n))
Last updated 3 months ago