Move all zeros to an end
Second largest element of an array
fgdf
[0][56][4][0][12][9][0][3][6]
[6][56][4][3][12][9][0][0][0]
public static void allZerosAtEnd(int[] arr) {
int zeroCount = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
swap(arr.length - 1 - zeroCount, i);
zeroCount++;
}
}
}
[0][56][4][0][12][9][0][3][6]
i = 0 --^ ^-- len - zeroCount -1
zeroCount = 0
[6][56][4][0][12][9][0][3][0]
i = 0 --^ ^-- len - zeroCount -1
zeroCount = 1
[6][56][4][0][12][9][0][3][0]
i = 1 --^ ^-- len - zeroCount -1
zeroCount = 1
[6][56][4][0][12][9][0][3][0]
i = 3 --^ ^-- len - zeroCount -1
zeroCount = 1
[6][56][4][3][12][9][0][0][0]
i = 3 --^ ^-- len - zeroCount -1
zeroCount = 2
[6][56][4][3][12][9][0][0][0]
i = 6 --^ ^-- len - zeroCount -1
zeroCount = 3
[6][56][4][3][12][9][0][0][0]
len - zeroCount -1 --^ ^-- i = 7
zeroCount = 3
public static void allZerosAtEnd(int[] arr) {
int zeroCount = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0 && i < arr.length - zeroCount - 1) {
swap(arr.length - 1 - zeroCount, i);
zeroCount++;
}
}
}
[0] [1] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [9]
i = 0 --^ ^-- len - zeroCount -1
zeroCount = 0
[9] [1] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [0]
i = 0 --^ ^-- len - zeroCount -1
zeroCount = 1
[9] [1] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [0]
i = 5 --^ ^-- len - zeroCount -1
zeroCount = 1
Most suitable approach
public static void allZerosAtEnd(int[] arr) {
int nonZeroIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
swap(i, nonZeroIndex);
nonZeroIndex++;
}
}
}
[0] [1] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [9]
nonZeroIndex --^ ^-- i = 0
[0] [1] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [9]
nonZeroIndex --^ ^-- i = 1
[1] [0] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [9]
nonZeroIndex --^ ^-- i = 1
[1] [0] [9] [8] [4] [0] [0] [2] [7] [0] [6] [0] [9]
nonZeroIndex --^ ^-- i = 2
[1] [9] [0] [8] [4] [0] [0] [2] [7] [0] [6] [0] [9]
nonZeroIndex --^ ^-- i = 2
