Question explanation!


#1

Analysis

This problem can be solved in O(n) time.

We can always assign a neighbor with 1 more if the neighbor has higher a rating value. However, to get the minimum total number, we should always start adding 1s in the ascending order. We can solve this problem by scanning the array from both sides. First, scan the array from left to right, and assign values for all the ascending pairs. Then scan from right to left and assign values to descending pairs.

This problem is similar to Trapping Rain Water.


#2

Thanks worked like a charm!!!


#3

Thanks, it worked!!! solution in 12 min


#4

Thanks :slight_smile: Quick and easy explanation :slight_smile:


#5

Yes the above method worked but can’t really get a feel for it! :frowning: