Monday, May 29, 2017

A Longest SubArray Problem

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft
Tags: data structures, constructive, math

Here is another interesting problem that I found as a subproblem while solving a difficult problem: you are given an array $A$, and you have to build up array $inc$ such that $inc[i]$ represents the length of  longest good subarray(LGD) starting from $i$. We call a subarray $(L, R)$ good if its first element($A_L$) $\ge 1$, its second element($A_{L+1}$) is $\ge 2$, ...., its last element is $\ge (R-L+1)$.

Eg: If the array given is $A = \{1,2,3,3,3\}$ ,
then the output will be $inc = \{3, 3, 3, 2, 1\}$.

Eg: If the array given is $A = \{4,2,3,5,9\}$ ,
then the output will be $inc = \{5, 4, 3, 2, 1\}$.

After a lot of thinking for about an hour, I had the following simple O(n) solution:

Let $LGS_i$ mean the longest good subarray starting from index $i$.
Let's modify our array $A$ as $A[i] = A[i] - i$,  then:
1. $LGS_0$ will continue to stretch till the maximum index $j$ such that $A[k]\ge 1$ for $k \le j$.  
2. $LGS_1$ will continue to stretch till the maximum index $j$  such that $A[k]\ge 0$ for $k \le j$.
3. $LGS_2$ will continue to stretch till the maximum index $j$  such that $A[k]\ge -1$ for $k \le j$.

Since at every step, the lower bound is always decreasing by 1, we can use one pointer to find the farthest ending point of good subarrays for all indices in $O(n)$.  Note that we are able to use 1 pointer technique because of the fact that ending point of $LGS_i$ will always be after the ending point of $LGS_{i-1}$.

Check the code for the implementation of above idea.

No comments:

Post a Comment

Cracking the Google Interview | Software Engineer reveals tips & secrets

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain micr...