Sort Colors

class Solution {
  public:
  void sortThreeColors(vector<int>& arr) {
    int zeroIndex = 0, currentIndex = 0;
    int twoIndex = arr.size() - 1;

    while (currentIndex <= twoIndex) {
      if (arr[currentIndex] == 0) {
        swap(arr[currentIndex++], arr[zeroIndex++]);
      }
      else if (arr[currentIndex] == 2) {
        swap(arr[currentIndex], arr[twoIndex--]);
      }
      else currentIndex++;
    }
  }
};

The "Sort Colors" problem involves sorting an array consisting only of the integers 0, 1, and 2. Representing colors, the goal is to sort them such that the same colors are together and in the order 0, 1, then 2. The provided C++ solution uses a three-pointer approach to achieve this in a single pass through the array. Here’s a breakdown of the solution:

• Initialize three pointers:
  • zeroIndex begins at the start of the array.
  • currentIndex starts at the beginning as well and is used to traverse the array.
  • twoIndex starts from the end of the array.
• Iterate over the array with the currentIndex:
  • When a 0 is encountered, swap it with the element at zeroIndex and increment both zeroIndex and currentIndex.
  • When a 2 is encountered, swap it with the element at twoIndex and decrement twoIndex.
  • If a 1 is encountered, simply increment currentIndex.
• Continue this process until currentIndex surpasses twoIndex.

This method efficiently sorts the elements with optimal time complexity, making it an ideal solution. Follow the implementation pattern meticulously to maintain the intended logic and functionality of the algorithm.

class Solution {
    public void sortThreeColors(int[] colors) {
        int low = 0, mid = 0;
        int high = colors.length - 1;
        int temp;
        while (mid <= high) {
            if (colors[mid] == 0) {
                temp = colors[low];
                colors[low++] = colors[mid];
                colors[mid++] = temp;
            } else if (colors[mid] == 2) {
                temp = colors[mid];
                colors[mid] = colors[high];
                colors[high--] = temp;
            } else mid++;
        }
    }
}

This solution addresses the problem of sorting an array of colors, represented by integers, using the Dutch National Flag algorithm. The array contains three different types of integers (0, 1, and 2), each integer representing a different color. The goal is to sort the array so that all 0s are at the beginning, followed by all 1s, and then all 2s at the end.

To solve this, the given Java code employs three pointers: low, mid, and high:

• low: Tracks the position for the next 0.
• mid: Scans through the array.
• high: Tracks the position for the next 2.

The process continues as long as mid is less than or equal to high, iterating through these steps:

1. If colors[mid] is 0, it swaps it with colors[low] and increments both low and mid.
2. If colors[mid] is 2, it swaps it with colors[high] and decrements high, but does not move mid because the new element at mid needs to be evaluated.
3. If colors[mid] is 1, just increments mid.

This efficient method ensures the array is sorted in a single traversal, making it time-efficient, with a time complexity of O(n), where n is the number of elements in the array.

void sortThreeColors(int* array, int arraySize) {
    int first = 0, middle = 0;
    int last = arraySize - 1;
    while (middle <= last) {
        if (array[middle] == 0) {
            int tmp = array[first];
            array[first++] = array[middle];
            array[middle++] = tmp;
        } else if (array[middle] == 2) {
            int tmp = array[middle];
            array[middle] = array[last];
            array[last--] = tmp;
        } else {
            middle++;
        }
    }
}

The provided C code defines a function sortThreeColors designed to sort an integer array that contains only the integers 0, 1, and 2. This sorting procedure aligns with the Dutch National Flag problem, where the objective is to sort the colors represented by the numbers 0 (red), 1 (white), and 2 (blue).

The function takes two parameters:

• int* array: a pointer to the array of integers
• int arraySize: the size of the array

Within the function:

• Initialize three pointers or indices: first, middle, and last.
  • first is set to 0.
  • middle is also set to 0.
  • last starts at arraySize - 1.
• Use a while loop to process elements in the array as long as middle is less than or equal to last.
• Inside the loop:
  • If the current element (array[middle]) is 0:
    • Swap this element with the element at first.
    • Increment both first and middle.
  • If the current element is 2:
    • Swap it with the element at last.
    • Decrement last without incrementing middle, as the swapped element needs re-evaluation.
  • If the element is 1, simply increment middle to continue the sorting process.

The swapping ensures that all 0s are moved to the beginning, all 1s remain in the middle, and all 2s get pushed to the end of the array. This algorithm efficiently categorizes and organizes the elements with a single pass through the array and therefore operates with a time complexity of O(n) and a space complexity of O(1), as it only rearranges elements in place without using any additional storage.

var rearrangeColors = function (colors) {
    let left = 0,
        center = 0;
    let right = colors.length - 1;
    while (center <= right) {
        if (colors[center] == 0) {
            [colors[center++], colors[left++]] = [colors[left], colors[center]];
        } else if (colors[center] == 2) {
            [colors[center], colors[right--]] = [colors[right], colors[center]];
        } else center++;
    }
};

The given JavaScript solution employs the Dutch National Flag algorithm to sort an array of integers (presumably representing colors), where each number (0, 1, or 2) corresponds to a different color. The code organizes the array so that all 0s come first, followed by all 1s, and all 2s last, without using additional storage.

In the solution:

• Initialize three pointers: left, center, and right. left points to the current position for the next 0, center scans through the array, and right points to the current position for the next 2.
• Iterate using the center pointer. For each element:
  • If the element is 0, swap it to the position pointed to by left. Increment both left and center.
  • If the element is 2, swap it with the element at the position pointed to by right. Decrement right.
  • If the element is 1, simply move to the next element by incrementing center.

By the end:

• All elements before left are 0s.
• Elements between left and right are 1s.
• Elements from right to the end are 2s.

This implementation provides an efficient way to sort the colors in-place with a worst-case time complexity of O(n) and a constant space complexity. It's well-suited for scenarios requiring minimal space usage and swift processing, such as color classification in graphical applications or organizing data before further processing.

class Solution:
    def sortSegments(self, array: List[int]) -> None:
        left = index = 0
        right = len(array) - 1

        while index <= right:
            if array[index] == 0:
                array[left], array[index] = array[index], array[left]
                left += 1
                index += 1
            elif array[index] == 2:
                array[index], array[right] = array[right], array[index]
                right -= 1
            else:
                index += 1

The provided solution in Python uses the Dutch National Flag sorting algorithm to solve the problem of sorting an array that consists of only three different elements: 0s, 1s, and 2s. The function sorts the elements in-place using three pointers: left, index, and right.

• left pointer keeps track of the position where the next 0 should be placed.
• index pointer is used to inspect each element in the list.
• right pointer determines where the next 2 should be placed.

The process follows:

1. Initialize left and index at the start of the list (0) and right at the end of the list.
2. Iterate through the array with the index pointer until it surpasses the right pointer.
3. If the element at the index is 0, swap it with the element at the left. Then, increment both the left and index.
4. If the element at the index is 2, swap it with the element at the right and decrement the right.
5. If the element is 1, simply increment the index.

Through the implementation of this algorithm, the array becomes sorted such that all 0s are in the beginning followed by all 1s and all 2s at the end. The algorithm efficiently sorts the array in O(n) time complexity, where n is the number of elements in the array, and does so in constant space, O(1), as it is an in-place sorting method.