Segregate red, blue, and black balls
Filed under Adobe
Free read 1 of 3Identify the mapping of colors to numeric values or distinct categories.
The question
Given an array containing balls of three distinct colors (represented as red, blue, and black), sort or segregate them in-place so that balls of the same color are grouped together.
Constraints
- 1 <= array length <= 10^5
- In-place sorting preferred with O(N) time complexity.
Examples
- Input
- arr = ["blue", "red", "black", "red", "blue"]
- Output
- ["black", "blue", "blue", "red", "red"]
- Why
- All matching color balls are grouped together.
Approach
Identify the mapping of colors to numeric values or distinct categories.
Count the occurrences of each color and overwrite the array. Requires two passes.
Use the Dutch National Flag algorithm with three pointers (low, mid, high) to segregate the elements in a single pass.
Arrays with missing colors or containing a single element.
Solution
O(N) time, O(1) space
def sort_three_colors(arr):
# Assuming 0: black, 1: blue, 2: red
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
return arr
Tips
- What they are testing: Test with an already sorted array, an array with only one color, and a reverse-sorted array.
- Common mistake: Using a comparison sort resulting in O(N log N) instead of the Dutch National Flag algorithm in O(N).
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.