How does LeetCode calculate solution speed?


  • 0
    J

    How does LeetCode calculate the speed of solutions? Out of curiosity I ran the top 3 solutions locally and it turns out the brute force approach was the fastest:

    import java.util.Map;
    
    public class Test {
    
    	public static void main(String[] args) {
    		int[] nums = new int[10000000];
    		for (int i = 0; i < nums.length; i++) {
    			nums[i] = i + 1;
    		}
    		long start = System.currentTimeMillis();
    		twoSumBrute(nums, 99999);
    		long end = System.currentTimeMillis();
    		System.out.println("twoSumBrute: " + String.valueOf(end - start));
    
    		start = System.currentTimeMillis();
    		twoSumTwoHash(nums, 99999);
    		end = System.currentTimeMillis();
    		System.out.println("twoSumTwoHash: " + String.valueOf(end - start));
    
    		start = System.currentTimeMillis();
    		twoSumSingleHash(nums, 99999);
    		end = System.currentTimeMillis();
    		System.out.println("twoSumSingleHash: " + String.valueOf(end - start));
    	}
    
    	public static int[] twoSumBrute(int[] nums, int target) {
    		for (int i = 0; i < nums.length; i++) {
    			for (int j = i + 1; j < nums.length; j++) {
    				if (nums[j] == target - nums[i]) {
    					return new int[] { i, j };
    				}
    			}
    		}
    		throw new IllegalArgumentException("No two sum solution");
    	}
    
    	public static int[] twoSumTwoHash(int[] nums, int target) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int i = 0; i < nums.length; i++) {
    			map.put(nums[i], i);
    		}
    		for (int i = 0; i < nums.length; i++) {
    			int complement = target - nums[i];
    			if (map.containsKey(complement) && map.get(complement) != i) {
    				return new int[] { i, map.get(complement) };
    			}
    		}
    		throw new IllegalArgumentException("No two sum solution");
    	}
    
    	public static int[] twoSumSingleHash(int[] nums, int target) {
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int i = 0; i < nums.length; i++) {
    			int complement = target - nums[i];
    			if (map.containsKey(complement)) {
    				return new int[] { map.get(complement), i };
    			}
    			map.put(nums[i], i);
    		}
    		throw new IllegalArgumentException("No two sum solution");
    	}
    
    }
    

    twoSumBrute: 2
    twoSumTwoHash: 6140
    twoSumSingleHash: 10


Log in to reply
 

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