Wednesday, February 18, 2015

Maximum length of subarray with non-zero elements

Given an array of of size N, How do we find the longest sub-array with all non-zero elements?

For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}.

This problem is from Codechef. Follow this link to solve this problem in your own.

The solution is simple. The array contains non zero segments of numbers separated by one or more zeros. While traversing the elements, use two variables current_len, and max_len to track the length of the current segment and maximum segment length seen so far.

Here is the Python implementation of the above. This runs in O(n) time.