Ad
  • Default User Avatar

    You should stop once you witness failure of monotonicity, e.g. don't traverse the whole array if heights[0] > heights[1]. That way your average complexity will be even better than linear.