Coding Interview Questions | Sort Colors

January 29th, 2024

Sort Colors Problem Introduction:

This summary will talk about my solution to the sort colors problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent,
with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

How do you solve the Sort Colors Problem in O(n) time complexity?

Solution:

const fillArray = (
  nums: number[],
  startIdx: number,
  endIdx: number,
  value: number
) => {
  for (let idx = startIdx; idx < endIdx; idx++) {
    nums[idx] = value;
  }
};

/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
  const numCountMap = new Map<number, number>();

  for (const num of nums) {
    const count = numCountMap.get(num);

    numCountMap.set(num, count ? count + 1 : 1);
  }

  let startIdx = 0;
  for (const value of [0, 1, 2]) {
    const valCount = numCountMap.get(value);

    fillArray(nums, startIdx, valCount ? startIdx + valCount : startIdx, value);
    startIdx = valCount ? startIdx + valCount : startIdx;
  }
}

Sort Colors Solution Summary:

Below is a breakdown of the key aspects of the provided solution for the “Sort Colors” problem seen above:

1. Counting Occurrences: The algorithm uses a Map called numCountMap to count the occurrences of each color (0, 1, and 2) in the nums array.

2. Filling Array: A helper function fillArray is defined to fill a portion of the nums array with a specified value, based on the start and end indices.

3. Iterating Through Colors: The algorithm iterates through each color (0, 1, and 2) and retrieves the count of occurrences from numCountMap.

4. Updating Array In-Place: For each color, it uses the fillArray function to update the nums array in-place, filling the corresponding range with the current color.

Complexities

1. Time Complexity: The time complexity of the solution is determined by the iteration through the nums array to count occurrences and the subsequent iteration through the colors. It is influenced by the length of the nums array, denoted as O(n), where n is the length of nums.

2. Space Complexity: The space complexity is O(k) as the algorithm uses a Map to store the count of each color, where k is the number of colors.

Bonus Solution: How do you solve the Sort Colors Problem using a multi-pointer approach?

function sortColors(nums: number[]): void {
  let low = 0;
  let high = nums.length - 1;
  let current = 0;

  while (current <= high) {
    if (nums[current] === 0) {
      // Swap current with low, increment both pointers
      [nums[current], nums[low]] = [nums[low], nums[current]];
      low++;
      current++;
    } else if (nums[current] === 2) {
      // Swap current with high, decrement high pointer
      [nums[current], nums[high]] = [nums[high], nums[current]];
      high--;
    } else {
      // No swap needed for 1, move to the next element
      current++;
    }
  }
}