Given an array containing zeroes, ones and twos only. Write a function to sort the given array in O(n) time complexity.

One way to sort an array containing zeroes, ones, and twos in O(n) time complexity is by using a variation of the counting sort algorithm. The idea is to count the number of zeroes, ones, and twos in the array, and then use that information to reconstruct the sorted array. Here's an example of how you can implement this in Java:

void sortArray(int[] arr) {
    int[] count = {0, 0, 0}; // Count of 0s, 1s, and 2s

    // Count the number of 0s, 1s, and 2s in the array
    for (int i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

    int i = 0;
    // Place the 0s in the array
    while (count[0]-- > 0) {
        arr[i++] = 0;
    }
    // Place the 1s in the array
    while (count[1]-- > 0) {
        arr[i++] = 1;
    }
    // Place the 2s in the array
    while (count[2]-- > 0) {
        arr[i++] = 2;
    }
}

This algorithm has a time complexity of O(n) because it iterates over the array once to count the number of zeroes, ones, and twos, and then iterates over the array again to place the elements in the correct positions, for a total of 2*n = O(n) operations.

Alternatively, you can use three-pointers to sort the array in place. One pointer is for iterating the array and two pointers are for maintaining the position of 0s and 2s. Here is an example:

void sortArray(int[] arr) {
    int low = 0, high = arr.length - 1;
    for (int i = 0; i <= high;) {
        if (arr[i] == 0) {
            int temp = arr[low];
            arr[low] = arr[i];
            arr[i] = temp;
            low++;
            i++;
        } else if (arr[i] == 2) {
            int temp = arr[high];
            arr[high] = arr[i];
            arr[i] = temp;
            high--;
        } else {
            i++;
        }
    }
}

This also has a time complexity of O(n) because it iterates over the array once and does constant work for each iteration.