Generalized to k color one pass solution (JAVA)

  • 1

    Need to move forward all pointers with higher index when a color was met.

    public class Solution {
        public void sortColors(int[] A) {
            int k = 3;
            int p[] = new int[k];
            for(int i = 0;i < A.length;i++){
                int t = A[i];
                for(int j = k-1; j >= t;j--)
                    A[p[j]++] = j;

  • 0

    Brilliant idea, although may not be as fast as two-pass.

  • 0

    This is like the idea behind insertion sort. It may not be fast enough.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.