Arrange Magical Orbs - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is a list orbs where each element is an integer representing the color of a magical orb (0 for red, 1 for white, and 2 for blue).
• Q: What is the output?
  • A: The output is the same list 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).
• Q: Are there any constraints on how the arrangement should be performed?
  • A: Yes, the arrangement must be done in-place without using any built-in sorting functions.

P-lan

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

• Failing to correctly update the pointers, leading to infinite loops or incorrect ordering.
• Forgetting that the algorithm must be performed in-place.

I-mplement

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]