Top 100
Sort Colors
- Problem
- LC 75
- File
- top100_LC75SortColors.java
- Path
- pkg5leetcode/top100/top100_LC75SortColors.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC75SortColors.java
- Approach
- Dutch national flag three pointers for 0,1,2 regions.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Sort Colors | LC 755 * APPROACH: Dutch national flag three pointers for 0,1,2 regions.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class top100_LC75SortColors {9 static void sortColors(int[] nums) {10 int lo = 0, hi = nums.length - 1, i = 0;11 while (i <= hi) {12 if (nums[i] == 0) swap(nums, lo++, i++);13 else if (nums[i] == 2) swap(nums, i, hi--);14 else i++;15 }16 }17 18 static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }19 20 public static void main(String[] args) {21 int[] a = {2, 0, 2, 1, 1, 0};22 sortColors(a);23 check(java.util.Arrays.equals(a, new int[]{0, 0, 1, 1, 2, 2}), "case1");24 int[] b = {2, 0, 1};25 sortColors(b);26 check(java.util.Arrays.equals(b, new int[]{0, 1, 2}), "case2");27 System.out.println("all tests passed");28 }29 30 static void check(boolean cond, String name) {31 if (!cond) throw new AssertionError("FAILED: " + name);32 System.out.println(" PASS " + name);33 }34}