Microsoft

48 articles

dsa17 min read

Move Zeroes — The Write Pointer Pattern Every Interview Tests [Microsoft, Amazon]

LeetCode 283 is the gateway to the two-pointer partition pattern used across dozens of harder problems. Learn why it appears in almost every Microsoft and Amazon phone screen, master the write-pointer mental model with a step-by-step dry run, and understand when to swap vs. overwrite — with Python and JavaScript solutions fully annotated.

Read →
dsa12 min read

Merge Sorted Array — Why Merging From the Back Is the Elegant O(1) Solution

Most candidates try to merge nums1 and nums2 from the front and run into a subtle overwrite bug. Learn why starting from the back is the key insight, how three pointers keep the logic clean, and how this same trick powers the merge step in Merge Sort. Full Python and JavaScript solutions included.

Read →
dsa18 min read

Maximum Product Subarray — Why Kadane's Fails and How to Fix It [Google, Amazon, Microsoft]

LeetCode 152 looks like a simple extension of Maximum Sum Subarray — until you hit negative numbers. A negative times a negative is positive, which means the current minimum can instantly become the new maximum. Learn why tracking BOTH cur_max and cur_min is the essential insight, how zeros act as hard resets, the four bugs every candidate makes, and step-by-step dry runs on key examples. Python and JavaScript solutions from O(n²) brute force to the elegant O(n) DP approach.

Read →
dsa14 min read

Sort Colors [Medium] — Dutch National Flag Algorithm Explained

Master Dijkstra's Dutch National Flag algorithm to sort 0s, 1s, and 2s in a single pass with O(1) space. Understand the three-pointer invariants, the critical bug most candidates make, and how this pattern unlocks a family of partition problems.

Read →
dsa17 min read

First Missing Positive [Hard] — The Definitive Index-Marking Guide [Amazon, Google, Microsoft]

LeetCode 41 is a landmark Hard problem because both obvious approaches — hash set and sorting — are explicitly banned by the constraints. Learn the mathematical insight that bounds the answer to [1, n+1], then master two O(n) time, O(1) space techniques: index marking via sign negation and cyclic sort placement, with a full visual dry run, bug catalogue, and FAANG follow-ups.

Read →
dsa17 min read

Largest Rectangle in Histogram [Hard] — Monotonic Stack Deep Dive [Amazon, Google]

Master LeetCode 84 the right way. Learn exactly why bars are popped from the monotonic stack, how to calculate left/right boundaries without bugs, the sentinel-values trick that eliminates edge cases, and a step-by-step dry run on [2,1,5,6,2,3] — plus how this pattern extends directly to Maximal Rectangle (LC 85).

Read →