[Algorithm] Making List Values Equal(Array/C++)

Problem Link: https://binarysearch.com/problems/Making-List-Values-Equal

Hello! Today’s we’ll be looking at an array question. Although it’s an “easy” question, it might be quite tricky to approach. As we can select multiple elements and increment them by 1 at the same time, there’s one thing you need to catch

Since there is no “decrement”, we eventually have to make all the elements to the “maximum element”.

Let’s take an example. Consider [1,7,7,9]. Then we need to make 1,7,7 to 9. Notice that a straight-up solution would be to increment each element by [9-element]. However, as we can operate on multiple items at the same time, it wouldn’t be the optimal solution. Instead, we can traverse from the back and increment every left element by [max_element-cur_element]. As we increment, we subtract the difference from the target value. Also, as we can perform operations on multiple elements at the same time, we remove duplicates. Below is the dry-run of the example.

target(max element) = 9, cnt=0

1. 1 7 [9] -> increment by 9–9=0
2. 1 [7] 9 -> increment by 9–7=2(cnt=2), target = 9–2 = 7
   -> 1 9 9 but same as 3 9 9
3. [1] 9 9-> increment by 7–1=6(cnt=8)(but same as incrementing by 6+(previously incremented value=2) = 8, target = 7–6=1
   ->Final: 9 9 9

Implementation

Time Complexity: O(n)