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