LeetCode 1008: Construct Binary Search Tree from Preorder Traversal
A clear explanation of reconstructing a BST from its preorder traversal using value range bounds.
Tag
Divide-and-Conquer
27 notes
LeetCode 241: Different Ways to Add Parentheses
A clear explanation of generating all possible results from different parenthesizations using divide and conquer recursion.
LeetCode 109: Convert Sorted List to Binary Search Tree
A clear explanation of converting a sorted linked list into a height-balanced binary search tree using slow and fast pointers.
LeetCode 108: Convert Sorted Array to Binary Search Tree
A clear explanation of building a height-balanced binary search tree from a sorted array using divide and conquer.
LeetCode 23: Merge k Sorted Lists
A detailed explanation of merging k sorted linked lists using a min heap.
LeetCode 912: Sort an Array
A clear explanation of sorting an array without built-in sorting using merge sort.
LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal
A clear explanation of reconstructing a binary tree from preorder and postorder traversals using recursion and index ranges.
LeetCode 932: Beautiful Array
A clear explanation of solving Beautiful Array using divide and conquer with odd and even transformations.
LeetCode 761: Special Binary String
A clear explanation of making a special binary string lexicographically largest using recursive decomposition and sorting.
LeetCode 654: Maximum Binary Tree
A clear explanation of constructing a maximum binary tree recursively using divide and conquer.
LeetCode 493: Reverse Pairs
A clear explanation of counting pairs where nums[i] is greater than twice nums[j] using merge sort.
LeetCode 427: Construct Quad Tree
Build a quad tree from a binary square grid using recursive divide and conquer.
LeetCode 395: Longest Substring with At Least K Repeating Characters
A clear explanation of finding the longest substring where every character appears at least k times using divide and conquer.
LeetCode 327: Count of Range Sum
A clear explanation of Count of Range Sum using prefix sums and merge sort counting.
LeetCode 215: Kth Largest Element in an Array
A clear explanation of finding the kth largest element using sorting, a min-heap, and Quickselect.
LeetCode 169: Majority Element
A clear explanation of finding the element that appears more than half the time using Boyer-Moore voting.
LeetCode 148: Sort List
Sort a singly linked list in ascending order using merge sort with fast and slow pointers.
LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal
A clear explanation of rebuilding a binary tree from inorder and postorder traversals using recursion and an index map.
7. Divide and Conquer Sorting
Divide-and-conquer sorts: merge sort variants, quicksort family, heapsort, and comparison-based sorting networks.
Quicksort
Divide and conquer sorting algorithm that partitions the array around a pivot and recursively sorts both sides.
Top Down Merge Sort
Recursive merge sort that splits the array from the top and merges sorted halves.
Merge Sort
Divide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.
Sorted Matrix Search
Search a matrix sorted by rows and columns using divide and conquer.
Two Dimensional Peak Finding
Find a peak element in a 2D grid using divide and conquer.
6.5 Quick Sort
Partition around a pivot so smaller elements go left and larger go right, then recursively sort each partition in expected O(n log n) time.
6.4 Merge Sort
Divide the input into halves, recursively sort each half, then merge them — combining local order into global order in O(n log n) time.
1.14 Divide and Conquer
Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers.