# Simple two pass O(n) time and O(1) space solution in Java

• Approach:
Here the array contains 3 numbers 0,1 and 2, each representing a color. Since we have exactly 3 colors in our sample space, all we need to do is to count the number of occurrences of each color in the first pass and refill the array with numbers based on the counts in the next pass.
Eg: MyArray = [1,0,2,2,0,1]
In the first pass, we make note of the number of occurrences of each color ( or number ) in the array. In our case, each number exists exactly twice in the array.
So in the second pass, we fill the array with colors in order as per the number of occurrence of each color. Hence we fill the array as
2 0's, 2 1's followed by 2 2's since each number occurs twice in the array.

``````class Solution {
public void sortColors(int[] nums) {
int zero_count = 0,one_count=0;
for(int i:nums){
if(i==0)
zero_count++;
else if(i==1)
one_count++;
else
continue;
}
for(int i=0;i<nums.length;i++){
if(zero_count-- > 0)
nums[i]=0;
else if(one_count-- > 0)
nums[i]=1;
else
nums[i]=2;
}
}
}
``````

• ``````class Solution {
public void sortColors(int[] nums) {
int [] c = new int[3];
// store counts for respective index
for(int n:nums) {
c[n] =c[n] + 1;
}
//track offset
int k=0;
for(int i=0; i<c.length; i++) {
for(int j=0; j< c[i]; j++) {
// overwrite location from offset
nums[k+j] = i;
}
// set new offset
k += c[i];
}
}
}
``````

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