Help: why my code is slow and exceed time limit?


  • 0
    P

    I need some help.....

    I used a SimpleEntry data type to store <sum of the numbers, index>. and then do a sort for the list<SimpleEntry>. Then I used a two pointers to do count for numbers within range.

    The answer is correct. And I did a count of total operations. For the question that I get time limit exceed issue, my count of operations with the below code is 100X less than the brute force method. However, the time required to conduct the operations is, surprisingly, the same as the brute force method. Could any one help me understand why that happens? Is it because the SimpleEntry is slow? or my code has problem in using the SimpleEntry class?

    Thanks a lot!!

    public static int countRangeSum1(int[] nums, int lower, int upper){
    	
    	if (nums==null || nums.length==0){return 0;}
    	
    	List<SimpleEntry<Integer,Integer>> sums = new ArrayList<>(nums.length);
    	
    	
    	for (int i=0;i< nums.length;i++){
    		totalCal++;
    		if (i==0) sums.add(new SimpleEntry<Integer,Integer>(nums[i],i));
    		else sums.add(new SimpleEntry<Integer,Integer>(sums.get(i-1).getKey() + nums[i],i));
    	}
    	
    	Collections.sort(sums, new Comparator<SimpleEntry<Integer,Integer>>(){
    		public int compare(SimpleEntry<Integer,Integer> e1, SimpleEntry<Integer,Integer> e2){
    			return Integer.compare(e1.getKey(), e2.getKey());
    		}
    	});
    	
    	// two pointers
    	int p1 = 0;
    	int p2 = 1;
    	int count = 0;
    	
    	for (int i = 0; i < sums.size() && p1 < sums.size() && p2 < sums.size(); i++){
    		
    		if (sums.get(i).getKey() <= upper && sums.get(i).getKey() >= lower) count ++;
    		// locate lower boundary
    		while (p1 < i && p1 < sums.size() && sums.get(i).getKey() - sums.get(p1).getKey() > upper){
    			p1 ++;
    		}
    		p2 = p1;
    		// locate higher boundary, and do count
    		while (p2 < sums.size() && sums.get(i).getKey() - sums.get(p2).getKey() <= upper && sums.get(i).getKey() - sums.get(p2).getKey() >= lower){
    			if (sums.get(i).getValue() > sums.get(p2).getValue()) count++;
    			p2++;
    		}
    	}
    	
    	return count;
    	
    }

Log in to reply
 

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