75. Sort Colors

Sorting Colors in Python: A Step-by-Step Guide

Sorting Colors in Python: A Step-by-Step Guide

In this blog post, we'll dive into a common problem known as the "Dutch National Flag problem." The goal is to sort an array containing three distinct integers representing colors. Specifically, we'll sort an array of colors where 0, 1, and 2 represent red, white, and blue, respectively. We'll use a simple counting approach to achieve this.

Problem Statement

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.

The Solution

We'll use a dictionary to count the occurrences of each color and then overwrite the original array based on these counts.

Step-by-Step Explanation

Step 1: Initialize a Dictionary with Counts

We start by initializing a dictionary using dict.fromkeys([0, 1, 2], 0) to store the count of each color.

count = dict.fromkeys([0, 1, 2], 0)

Step 2: Count the Occurrences of Each Color

Next, we iterate through the input array nums and update the dictionary with the count of each color.

n = len(nums)
for i in range(n):
    count[nums[i]] += 1

Step 3: Extract the Counts

After counting the occurrences, we extract the counts of 0s, 1s, and 2s from the dictionary for easier access.

count_0 = count[0]
count_1 = count[1]
count_2 = count[2]

Step 4: Overwrite the Array

Now, we iterate through the array again and overwrite it with the sorted order of colors.

for i in range(n):
    if i < count_0:
        nums[i] = 0
    elif i < count_0 + count_1:
        nums[i] = 1
    else:
        nums[i] = 2

Full Code

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        count = dict.fromkeys([0, 1, 2], 0)
        n = len(nums)
        for i in range(n):
            count[nums[i]] += 1
        count_0 = count[0]
        count_1 = count[1]
        count_2 = count[2]
        for i in range(n):
            if i < count_0:
                nums[i] = 0
            elif i < count_0 + count_1:
                nums[i] = 1
            else:
                nums[i] = 2

Complexity Analysis

  • Time Complexity: O(n) – Counting occurrences takes O(n) time, and overwriting the array also takes O(n) time.
  • Space Complexity: O(1) – The extra space used for the dictionary is constant.

Conclusion

This approach ensures an efficient solution with linear time complexity and constant space complexity. By counting the occurrences of each color and then overwriting the array, we achieve the desired order of red, white, and blue colors.

Additional Resources

For an alternative approach, check out this LeetCode solution by Bikash Kumar.

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more