Katkat
Back

Sort Three Categories In Place

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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]