###
**Problem Discussed Today:**

**Interview Problem ( From LeetCode )**

No editorial will be provided for the Interview Problem.

**Editorial**

**Idea:**

Otherwise, all the segments that Adel can choose will have sum < than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Solution Link: Solution

**Idea:**

For each window $(x,y$ dirty water may reach it through windows $(x-1,y-1$ or $(x-1,y)$ or $(x-1,y+1)$.

For each window $(x,y)$ let’s denote by $d{p}_{x,y}=t$ the latest moment $t$ such that some window $(p,q)$ was cleaned at moment $t$ and the dirty water reached $(x,y)$ from $(p,q)$.We previously stated that dirty water may reach $(x,y$ only from its neighbors. Quite frankly:

$t=d{p}_{x,y}=max(d{p}_{x-1,y-1},d{p}_{x-1,y},d{p}_{x-1,y+1})$

Because these are the only possible ways such that the dirty water may reach $(x,y)$.

Now that we have found $t$ for our window $(x,y)$. If $t$ is later than $A_{x,y}$ then it will be dirty by the end of the process, otherwise it will be clean.

After determining the answer for $(x,y)$ (clean/dirty) we should update $dp_{x,y}$:

$d{p}_{x,y}=max(d{p}_{x,y},{A}_{x,y})$

Because $d{p}_{x,y}$ denotes some moment where dirty water reaches $(x,y)$ and it will be propagated to windows below $(x,y)$. At the moment, $A_{x,y}$ the window will be cleaned and dirty water will start flowing, so we must update $d{p}_{x,y}$ such that $A_{x,y}$ would be propagated as well.

Solution Link: Solution

**an error or want to discuss your approach**, then please feel free to drop in the comment section.

## Comments

## Post a Comment