# Big difference between these two lines?

• I got below code accepted, let me explain a little. I use a int[] candy and go through ratings to set values for candy, candy[i] will be 1 if ratings[i] equals to ratings[i - 1], candy[i] will be candy[i - 1] + 1 if ratings[i] is bigger than ratings[i - 1], in the process I maintain a variable to track the last top rating so that in the case ratings[i] < ratings[i - 1], I can check backwards to make sure higher ratings get more candy until I reach last top rating.

My question is that, see in the inner for loop, I first use candy[j] = candy[j + 1] + 1; and got TLE, but got accepted if I use candy[j]++;

Is former line of code so slower than the latter one?

``````    public int candy(int[] ratings) {
int len = ratings.length;
if (len <= 1) return len;

int[] candy = new int[len];
candy[0] = 1;

int lastTop = 0;
for (int i = 1; i < len; i++){
if (ratings[i] == ratings[i - 1]){
candy[i] = 1;
lastTop = i;
}
if (ratings[i] > ratings[i - 1]){
candy[i] = candy[i - 1] + 1;
lastTop = i;
}
else  {
candy[i] = 1;
for (int j = i - 1; j >= lastTop; j--){
if (candy[j] <= candy[j + 1]){
//candy[j] = candy[j + 1] + 1;      //TLE !
candy[j]++;                         //but this passes
}
else {
break;
}
}
}
}

int total = 0;
for (int i = 0; i < len; i++){
total += candy[i];
}
}``````

• Is this not O(N^2) solution . I am not an expert , please excuse me if i am wrong. My analysis is if i take an example which is like : 10,9,8,7,6,5. The outer for loop goes from i= 1: end and for every i, j goes from i to start. So I guess it is O(n^2) solution.

• ah, right, I asked this a couple months ago, thanks for your reply. You are right, it is N^2 solution in the worst case, I managed to improve this solution to do backwards tracking only once for each descending section, so it became 2N in worst case and it ACed with reduced run time.

Also, I guess the original question was caused by some randomness, efficiency of the two lines are probably the same. I am closing this.

• since I am here, I want to thank leetcode for helping me get a great job. I was visiting leetcode everyday when I was preparing for interview. Now I am not, but I sure would come back visit once a while :)

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