Given an array filled with char elements, find the max length of continuous white space

Problem

Given array filled with char elements, can you suggest a most efficient way to find the max length of continuous white space?

Solution

Scan the array left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it's higher, it becomes the new max. Set the count back to zero, continue scanning.

Time complexity - O(n)
This is O(n) and you can't really do better because you have to touch each element at least once.

But of-course we can optimize it. Consider the answer given here, we can follow following solution:

Scan the array from left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it's higher, it becomes the new max. Skip forwards this max number in the array - if it is not whitespace you know the interval cannot contain the max whitespace. Otherwise search backwards to where whitespace started - find that set your count and continue from where you had previously skipped to.
I believe worst case performance of this would be O(n) and best case would be O(sqrt(n)) for the case where there is a sqrt(n) start of whitespace followed by non-whitespace on every skip point (causing repeated skipping to the end of the array).
 

 

References

• http://stackoverflow.com/questions/5373461/a-question-from-morgan-stanleys-interview