### 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).

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**

## 0 comments:

## Post a Comment