cswork / libraryOpen practice workspace

Coding questions · Microsoft

Sort Three Categories In Place

This question evaluates proficiency in in-place array manipulation, constant-space algorithms, and linear-time partitioning techniques. Commonly asked in Coding & Algorithms interviews to assess algorithmic efficiency, pointer/index management, and reasoning about invariants, it focuses on practical application of algorithmic concepts rather than purely theoretical understanding.

You are given an array items containing only the values 0, 1, and 2, where each value represents a category. Rearrange the array in-place so that all 0s come first, followed by all 1s, then all 2s.

Requirements:

  • Modify the input array in-place.
  • Use O(1) extra space.
  • Aim for a single-pass O(n) solution.

Example:

Input:  items = [2, 0, 2, 1, 1, 0]
Output: items = [0, 0, 1, 1, 2, 2]

Sort Three Categories In Place

Constraints

  • 0 <= len(items) <= 10^5
  • Each element in items is one of: 0, 1, 2
  • The solution must use O(1) extra space

Hints

  1. Try maintaining three regions in the array: one for 0s, one for unknown values, and one for 2s.
  2. When you see a 2, swap it toward the end, but do not immediately move past the new value swapped into the current position.