Recently I was asked a question. Given an array of sorted integers, count the number of unique absolute numbers without using any additional space. Here is what I came up with. Comment if you have a better approach. I believe the complexity of this function is O(n).
private static int countAbsoluteNumbers(int[] array) { Integer lastNumberFromLeft = null;
int count = 0;
int innerIndex = array.length - 1;
for (int i = 0; i < innerIndex + 1; ++i) { if (lastNumberFromLeft == null
|| Math.abs(array[i]) != Math.abs(lastNumberFromLeft)) { if (array[i] < 0) { lastNumberFromLeft = array[i];
}
else {
lastNumberFromLeft = - array[i];
}
++count;
Integer lastNumberFromRight = null;
for (; innerIndex > i ;--innerIndex) { if (Math.abs(array[innerIndex]) > Math.abs(lastNumberFromLeft) ) { if ((lastNumberFromRight == null)
|| (lastNumberFromRight != null
&& Math.abs(array[innerIndex]) != lastNumberFromRight)) { ++count;
}
lastNumberFromRight = array[innerIndex];
}
else if (Math.abs(array[innerIndex]) != Math.abs(lastNumberFromLeft)) {
break;
}
}
}
}
return count;
}
