Big difference between these two lines?


  • 0
    N

    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];
            }
            return total;
        }

  • 1
    G

    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.


  • 0
    N

    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.


  • 0
    N

    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 :)


Log in to reply
 

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