algoadvance

Leetcode 75. Sort Colors

Problem Statement

The problem is to sort an array containing only the integers 0, 1, and 2. This is often referred to as the “Dutch National Flag” problem. You are required to sort the array in-place and in linear time.

Clarifying Questions

  1. Q: Can we use built-in sorting functions to solve this problem?
    • A: No, the problem specifically asks for an in-place solution with linear time complexity.
  2. Q: Are there any constraints on the size of the array?
    • A: The size constraints are typical for interview problems, so you can assume the array will fit in memory.
  3. Q: Is the input array mutable?
    • A: Yes, since the problem specifies sorting in-place.

Strategy

To solve this problem in linear time and constant space, we can use the three-way partitioning approach (Dutch National Flag Algorithm). The approach involves maintaining three pointers to partition the array into three sections: one for 0s, one for 1s, and one for 2s.

  1. Initialization:
    • Define three pointers: low, mid, and high.
    • low is used to place 0s.
    • mid is used to iterate through the array.
    • high is used to place 2s.
  2. Procedure:
    • Traverse the array with the mid pointer.
    • When encountering a 0: swap it with the value at the low pointer, then increment both low and mid.
    • When encountering a 1: simply move to the next element by incrementing mid.
    • When encountering a 2: swap it with the value at the high pointer, then decrement high.
  3. Termination:
    • The process continues until mid surpasses high.

Code

Here is the Java implementation:

public class Solution {
    public void sortColors(int[] nums) {
        // Pointers for the current front (low), current (mid), and back (high) positions
        int low = 0, mid = 0, high = nums.length - 1;

        // Traverse the array from start to end
        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap nums[mid] with nums[low] and increment both pointers
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // Move mid pointer to the next element
                mid++;
            } else if (nums[mid] == 2) {
                // Swap nums[mid] with nums[high] and decrement high pointer
                swap(nums, mid, high);
                high--;
            }
        }
    }

    // Helper method to swap elements in an array
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        sol.sortColors(nums);

        // Output the sorted array
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

The time complexity of this algorithm is O(n) because it processes each element of the array exactly once.

The space complexity is O(1) because it only uses a few additional variables (pointers) and does not require any extra space that scales with the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI