You should be able to achieve O(n) time.