Monday, September 17, 2018

Unique Absolute Numbers

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;
}

No comments:

Post a Comment