TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
orbs
where each element is an integer representing the color of a magical orb (0 for red, 1 for white, and 2 for blue).orbs
, but with the orbs arranged so that all orbs of the same color are adjacent and ordered as red (0), white (1), and blue (2).Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use the Dutch National Flag algorithm, which efficiently sorts the list in a single pass by maintaining three pointers for the low (red), mid (white), and high (blue) regions.
1. Initialize three pointers: `low` at the start of the list, `mid` at the start of the list, and `high` at the end of the list.
2. Iterate through the list with the `mid` pointer:
1. If `orbs[mid]` is `0` (red):
- Swap `orbs[mid]` with `orbs[low]`.
- Increment both `low` and `mid`.
2. If `orbs[mid]` is `1` (white):
- Increment `mid`.
3. If `orbs[mid]` is `2` (blue):
- Swap `orbs[mid]` with `orbs[high]`.
- Decrement `high`.
3. Continue this process until `mid` is greater than `high`.
4. The list `orbs` will now be arranged in the order red, white, and blue.
⚠️ Common Mistakes
def arrange_magical_orbs(orbs):
low, mid, high = 0, 0, len(orbs) - 1
while mid <= high:
if orbs[mid] == 0: # Red orb
orbs[low], orbs[mid] = orbs[mid], orbs[low]
low += 1
mid += 1
elif orbs[mid] == 1: # White orb
mid += 1
else: # Blue orb
orbs[mid], orbs[high] = orbs[high], orbs[mid]
high -= 1
# Example usage
orbs1 = [2, 0, 2, 1, 1, 0]
arrange_magical_orbs(orbs1)
print(orbs1) # Output: [0, 0, 1, 1, 2, 2]
orbs2 = [2, 0, 1]
arrange_magical_orbs(orbs2)
print(orbs2) # Output: [0, 1, 2]