How to prove the correctness?


  • 1
    Z

    There is a O(n) solution, which scans the ratings[] twice. I have detailed algorithm and kind of proof in my blog here. However, I do think it is a proof... May be we can prove the correctness by contradiction. Anyway, I describe my solution briefly as follows.

    Let M[i] be the number of candies the i-th child has, M[i] is 1 at least. Additinally, it should meet two requirements:

    1. LEFT. For i > 0, M[i] > M[i-1] if ratings[i] > ratings[i-1].

    2. RIGHT. For i < n-1, M[i] > M[i+1] if ratings[i] > ratins[i+1].

    To get the minimum sum of M[], we change the two requirements as:

    1. LEFT. For i > 0, M[i] = M[i-1] + 1 if ratings[i] > ratings[i-1].

    2. RIGHT. For i < n-1, M[i] = M[i+1] + 1 if ratings[i] > ratins[i+1].

    Then, the algorithm starts from i = 0 to n-2 for the first pass and compute M[] only following LEFT. Then in the second pass, starts from i = n-2 to 0 and update M[] following RIGHT and LEFT.

    Anyone has idea to prove that the algorithm would give the correct answer? or we do not need to prove since it is naturally correct?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.