Sort first or already sorted [mp]

Micro pattern¶

Description¶

Sort input or exploit existing order so local comparisons replace broader searches.

Problems¶

Exploit already sorted input¶

Use monotonic values to eliminate candidates efficiently.

• 26. Remove Duplicates from Sorted Array (Top Easy)
• 240. Search a 2D Matrix II (Top Medium)
• 378. Kth Smallest Element in a Sorted Matrix (Top Hard)
• 4. Median of Two Sorted Arrays (Top Hard)
• 35. Search Insert Position (Google Prep)

Sort before scanning or arranging¶

Create an order that makes relevant candidates adjacent or local choices safe.

• 15. 3Sum (Top Medium)
• 56. Merge Intervals (Top Medium)
• 179. Largest Number (Top Hard)
• 324. Wiggle Sort II (Top Hard)
• 406. Queue Reconstruction by Height (Top Hard)
• 218. The Skyline Problem (Top Hard)
• 315. Count of Smaller Numbers After Self (Top Hard)
• 646. Maximum Length of Pair Chain (Dynamic Programming)
• 354. Russian Doll Envelopes (Dynamic Programming)