Is the Runtime calculated for Javascript source code, correct?


  • 0
    Y

    I tried running 2 different solutions which I developed to this 3SUM problem, using Javascript code. And when I hit the "Run Code" button, it showed the Runtime as > 100ms.

    I thought the code is not optimal enough and so tried looking into the 3SUM discussions here to check any code that has the best runtime, and I found one which had 1ms!! I was so impressed and tried running that same JAVA code and as expected, it showed 1ms as runtime. Really good!!

    That being said, I just wrote the same java code logic into javascript and tried running it here. To my surprise, I saw its runtime as > 100ms for this one too!! For the same logical code which got 1ms in java.

    So I tried adding timers to all the 3 javascript solutions which I had in hand, and tried running here. To my surprise again, I got the runtime as roughly ~ 1ms, ~2ms, ~18ms.

    So I just have the question whether the runtime calculated and shown for Javascript source code is correct?

    Below are the source codes which I tried, and the respective Runtimes observed:

    1. Using multiple loops:

    Runtime shown by the Site : Runtime:120 ms

    Runtime shown by the Timer : threeSum Runtime: 1.968ms

     /** 
     * @param {number[]} nums
     * @return {number[][]}
     */
    var threeSum = function (nums) {
        console.time('threeSum Runtime');
        let tripletSize = 3
      let passedCombinations = []
      nums.forEach(function (e1, i1) {
        if (i1 <= nums.length - tripletSize) {
          nums.slice(i1 + 1, nums.length).forEach(function (e2, i2, a2) {
            if (i2 <= nums.length - tripletSize) {
              a2.slice(i2 + 1, nums.length).forEach(function (e3) {
                let passed = (e1 + e2 + e3) ? false : true
                if (passed) {
                  let nowPassedCombination = [e1, e2, e3].sort()
                  let nowPassedCombinationString = nowPassedCombination.toString()
                  let skipThisCombination = false
                  passedCombinations.forEach(function (alreadyPassedCombination) {
                    if (alreadyPassedCombination.toString() == nowPassedCombinationString) {
                      skipThisCombination = true
                      return false
                    }
                  })
                  if (!skipThisCombination) {
                    passedCombinations.push(nowPassedCombination)
                  }
                }
              });}
          });}
      })
      console.timeEnd('threeSum Runtime');
      return passedCombinations;
    }
    
    1. Using Recursion:

    Runtime shown by the Site : Runtime:104 ms

    Runtime shown by the Timer : threeSum Runtime: 16.268ms

    let passedCombinations = [];
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    console.time('threeSum Runtime');
    var threeSum = function (nums, _c1, _c2, _c3) {
      if((_c1>=0) && (_c2>=0) && (_c3>=0)){
        if(nums[_c1] + nums[_c2] + nums[_c3] === 0) {
    		let _pc = [nums[_c1],nums[_c2],nums[_c3]].sort();
    		let pushFlag = true;
    		passedCombinations.forEach(function(e){
    			if(e.toString() == _pc.toString()){
    				pushFlag = false;
    				return false;
    			}
    		});
    		if(pushFlag){
    			passedCombinations.push(_pc);	
    		}
        }
          if(_c3 == nums.length-1){
            if(_c2<nums.length-2){
              threeSum(nums,_c1,++_c2, _c2+1);
            }else if(_c1<nums.length-3){
              threeSum(nums,++_c1,_c1+1, _c1+2);
            }
          }else{
            threeSum(nums,_c1,_c2, _c3+1);
          }
      } else {
        threeSum(nums,0,1,2);
    	console.timeEnd('threeSum Runtime');
    	return passedCombinations;
      }
    }
    
    1. The Javascript version of Java based solution I found here with Runtime as 1ms:

    Runtime shown by the Site : Runtime:104 ms

    Runtime shown by the Timer : threeSum Runtime: 1.209ms

    /** @param {number[]} nums
     * @return {number[][]}
     */
    var threeSum = function (nums) {
        console.time('threeSum');
        let passedCombinations = [];
        let numbers = nums.sort();
        let i = 0;
        while(i<numbers.length-2){
            if(numbers[i]>0){
                return passedCombinations;
            }
            let j = i+1;
            let k=numbers.length-1;
            while(k>j){
                let sum = numbers[i] + numbers[j] + numbers[k];
    			if(sum === 0){
                    passedCombinations.push([numbers[i], numbers[j], numbers[k]]);
                }if(sum<=0){
    				while(numbers[j] == numbers[++j] && j<k);
    			}if(sum>=0){
    				while(numbers[k--] == numbers[k] && j<k);
    			}
            }
            while(numbers[i] == numbers[++i] && i<numbers.length-2);
        }
        console.timeEnd('threeSum');
    	return passedCombinations;
    };
    

    Original JAVA Code:

    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length < 3) return result;
        Arrays.sort(nums);
        int i = 0;
        while(i < nums.length - 2) {
            if(nums[i] > 0) break;
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0) result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                if(sum <= 0) while(nums[j] == nums[++j] && j < k);
                if(sum >= 0) while(nums[k--] == nums[k] && j < k);
            }
            while(nums[i] == nums[++i] && i < nums.length - 2);
        }
        return result;
    }
    

    }


Log in to reply
 

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