# Sort Colors II in Java : a little error in the output, but can not find out why

• My output is [1, 2, 2, 4, 3], not right. It should be [1, 2, 2, 3, 4]. But I can't find the error in my code. Could anyone help me find out the error of algorithm ? Thank you. My entire code is copied below. It can be implemented.

The completer Question is :

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

Example: Given colors=[3, 2, 2, 1, 4enter code here], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

Requirements: A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?

``````import java.util.Arrays;

public class SortColorsII {
public static void sortColors2(int[] colors, int k) {
int count = 0;
int start = 0;
int end = colors.length-1;
while (count <= k) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

for (int i = start; i < end; i++) {
min = Math.min(min, colors[i]);
max = Math.max(max, colors[i]);
}
int left = start;
int right = end;
int cur = left;
while(cur <= right) {
if (colors[cur] == min) {
swap(left, cur, colors);
cur++;
left++;
} else if(colors[cur] == max) {
swap(cur, right, colors);
right--;
} else {
cur++;
}
}
count += 2;
start = left;
end = right;
}
}

private static void swap(int left, int right, int[] colors) {
int tmp = colors[left];
colors[left] = colors[right];
colors[right] = tmp;
}
public static void main(String[] args){
int[] colors = new int[]{3, 2, 2, 1, 4};
int k = 4;
sortColors2(colors,  k);
String res = Arrays.toString(colors);
System.out.println(res);
}

}``````

• I found my error. The minimum/maximum search excludes the last element. Change to use an inclusive upper bound:

``for (int i = start; i <= end; i++) ``

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