Katkat
Back

Sort an RGB Record Collection In Place

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to partition an array into three distinct groups (Red, Green, Blue) in a single pass using constant extra space, which is a classic application of the Dutch National Flag algorithm.

Problem Statement

You are given an array records representing a collection of items, where each item is assigned a color code: 0 for Red, 1 for Green, and 2 for Blue. Implement an algorithm to sort these items in-place such that all items of the same color are grouped together in the order: Red, Green, Blue.

The sorting must be performed in a single pass over the array, using only constant extra space.

Function Signature

def sort_rgb(records: list[int]) -> None:
    # Modifies records in-place
    pass

Constraints

  • The input array records contains only the integers 0, 1, and 2.
  • Time complexity: O(n), where n is the length of the array.
  • Space complexity: O(1).

Examples

Example 1: Input: records = [2, 0, 1, 2, 1, 0] Output: [0, 0, 1, 1, 2, 2]

Example 2: Input: records = [1, 2, 0] Output: [0, 1, 2]

Edge Cases

  • Empty array: [] should remain [].
  • Array with a single element: [0] or [2] should remain unchanged.
  • Array already sorted: [0, 0, 1, 1, 2, 2] should remain unchanged.
  • Array with only one color: [1, 1, 1] should remain unchanged.

Hints

Hint 1

Maintain three pointers: one for the end of the Red section, one for the current element being processed, and one for the start of the Blue section.

Hint 2

Initialize the Red pointer at the beginning and the Blue pointer at the end of the array; the current pointer starts at the beginning.

Hint 3

When encountering a 0, swap it with the Red pointer's position and increment both; when encountering a 2, swap it with the Blue pointer's position and decrement the Blue pointer.

Follow-up questions

  • How would you modify your approach if there were four colors instead of three?
  • What would be the impact on time complexity if the colors were represented by objects with different weights instead of integers?
  • How does the stability of this sorting algorithm compare to a standard QuickSort partition step?