Why a really tiny modification in code can lead to great runtime difference?


  • 0

    Here is my original solution

        public static int removeElement2(int[] nums, int val) {
            int j = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == val) continue;
                nums[j] = nums[i];
                j++;
            }
            return j;
        }
    

    But all I did was replace the last two lines in the loop to

    nums[j++] = nums[i];
    

    But the amount of people I beat fell from 62% to only 4%, although the runtime only fell from 1ms to 0ms.

    But Is there even differences between the two versions at runtime?


  • -1

    @jeremylinlin You're just too much into the beating stuff, of course you should care for the cleanness and tidiness of your code but please pay more attention to the algorithm itself. Have fun!


  • 0

    @jeremylinlin How great was the runtime difference? Maybe it was just 0.499 ms vs 0.501 ms? And how often did you submit each version?


  • 0

    @ManuelP Since we are not able to see how great the real difference is between 1ms and 0ms, I guess checking the "beating" statistics is the only way to check the runtime efficiency. But I have tried to submit three times respectively. Same results :(


  • 1

    @jeremylinlin I submitted each three times as well now, alternatingly, and got these results:

    separate:   0 ms, beat 62.57%
    integrated: 1 ms, beat  3.96%
    separate:   1 ms, beat  3.96%
    integrated: 0 ms, beat 62.57%
    separate:   0 ms, beat 62.57%
    integrated: 1 ms, beat  3.96%
    

    So doing j++ separately didn't always get 0 ms and doing it integratedly didn't always get 1 ms. Furthermore, the beat percentages for 0 ms were always the same 62.57% and the beat percentages for 1 ms were always the same 3.96%. So yeah, that rather clearly suggests what one might suspect anyway, that the beat percentages are calculated from the integral ms values and thus don't tell you any more than those do.


  • 0

    @ManuelP Thanks! That was helpful :)


Log in to reply
 

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