Divide & Conquer

Notes and typical questions for Divide & Conquer related questions

Notes

• Placeholder

Typical Questions

• LC 21. Merge Two Sorted Lists

  • Optimal Answer. TC: $O(m+n)$, SC: $O(1)$

• LC 148. Sort List

  • Approach 1 with recursive merge sort: Answer. TC: $O(n*logn)$, SC: $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/

• ⚪ LC 427. Construct Quad Tree

  • Optimal Answer.

  • TC: $O(4^{log_2{N}}) = O(N^{log_24}) = O(N^2)$

  • SC: $O(log_2N)$

• LC 108. Convert Sorted Array to Binary Search Tree

  • Optimal Answer. TC: $O(n)$, SC: $O(log(n))$