import java.util.Arrays;
class Main {
public static void main(String[] args) {
/**
* Problem: Move Zeroes
* Given an array, move all 0's to the end while maintaining the relative order of non-zero elements.
*
* Example:
*
* Input: [0, 1, 0, 3, 12]
* Output: [1, 3, 12, 0, 0]
*/
int[] input = {0, 1, 0, 3, 12};
// We can use two nested loops to iterate each element and comparing it with the
// next element to decide if we can move it to the next position because it is 0 or not.
// However, this is not the most efficient approach.
// Instead, we can use Two pointers approach with same direction.
// Basicaslly, we can set a slow index in the first element to start the comparison
// The fast element will traverse the rest of the elements of the array.
// We can switch the elements if the element at soft position is 0 and
// the element at fast position is not 0
// In this case, we can move slow position one step (slow++)
System.out.println(Arrays.toString(moveZeroes(input)));
/**
* 🧪 Test Your Code with These Cases:
* [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]
* [1, 0, 0, 3, 12] → [1, 3, 12, 0, 0]
* [0, 0, 1] → [1, 0, 0]
* [1, 2, 3] → [1, 2, 3] (no zeros)
* [0, 0, 0] → [0, 0, 0] (all zeros)
*/
input = new int[]{1, 0, 0, 3, 12};
System.out.println(Arrays.toString(moveZeroes(input)));
input = new int[]{0, 0, 1};
System.out.println(Arrays.toString(moveZeroes(input)));
input = new int[]{1, 2, 3};
System.out.println(Arrays.toString(moveZeroes(input)));
input = new int[]{0, 0, 0};
System.out.println(Arrays.toString(moveZeroes(input)));
input = new int[]{};
System.out.println(Arrays.toString(moveZeroes(input)));
input = null;
System.out.println(Arrays.toString(moveZeroes(input)));
}
private static int[] moveZeroes(int[] input) {
if (input == null || input.length == 0) {
return input;
}
int slow = 0; // Space O(1)
for (int fast = 0; fast < input.length; fast++) { // Time O(n)
if (input[fast] != 0) {
// switch elements
int temp = input[fast];
input[fast] = input[slow];
input[slow] = temp;
slow++;
}
}
// Time complexity O(n)
// Space complexity U(1)
return input;
}
}
