How does line 5244 have 3 connected component?

#1

I understud the sample case of 3,3,3 that all are same so all are 1 connected component.But in 5244 how come there are 3 connected components? its just two 4’s that are same so there should be only 1 component right?

#2

hello @pranjalarora98

yeah two 4’s are 1 components and 5 n 2 are other two components so total 3 components.

#3

And 1 thing how are they performing recolouring?

#4

Like 4 5 2 2 1 3 5 5 this is there so its said that first choose 5 and then?How did recolouring take place

#5

@pranjalarora98

ordering is upto u , u can pick any in any order.

4 5 2 2 1 3 5 5

if i pick this 5 and changed it to 6 then the complete component connected with this 5 will turn to 6.
so after recoloring it will be
4 5 2 2 1 3 6 6

#6

Can it be done by defining dp[i] that will store minimum turns to make items from 0index to i of same colour? And then how will i make relation can u just give some small hint or intution.

#7

2dp is needed.
try to think of recursive solution first

#8

So something like dp[i][j]= no of steps required to colour from i index to j index?

#9

yeah something like that.
also u can remove the consecutive same elements before after applying dp becuase they will not have any effect on answer.

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.