Divide and Conquer Topics
Master essential Divide and Conquer problems and patterns frequently asked in interviews.
- 01 Kth Largest Element in an Array Using Quickselect(Modified QuickSort)
- 02 Maximum SubArray Find the maximum sum in the left and right half, and the subarray crossing the midpoint.
- 03 Count Inversions Find number of them in left and right halves, and between the two halves while merging using Modified Merge Sort
- 04 Median of two sorted lists Using Binary Search logic to come up with the right partition point
- 05 Closest pair of points on plane Find closest pair in left and right halves and around narrow strip of point around dividing line
WONDERING, HOW DOES IT COVER PATTERNS?
These problems cover the most
important Divide and conquer patterns for interviews:
Kth Largest Element →
Quickselect, a partition-based selection algorithm
Maximum SubArray →
3-step analysis(solution in left, right or crossing around the
center)
CountInversions →
Designing Modified MergeSort with divideandconquer during the merge
step
Median of 2 sorted lists →
Designing Advanced Binary Search using Divide and Conquer
Closest pair of points on plane →
Using Divide and Conquer with complex "strip" combine step in a
geometrical setting
Together, they ensure you understand
partition-based selection, three-case analysis, modifying Merge Sort,
advanced binary searching using DAC, and applying DAC in geometric
contexts
in Divide and Conquer problems.