Why does My O(N) Solution Exceed the Time Limit?


  • 0
    W

    Hi folks!

    My solution was as follows:

    1. Construct a multimap-like structure, which sort the rating values, and store all the child indices with the same rating. Specifically, I used TreeMap in Java.

    2. Calculate the number of candies for each child from the lowest rating to the highest rating and with the initial value of 1. Guarantee that each child must get more candies than the neighbor(s) with lower rating.

    3. Sum up the number of candies, and this step can be merged with the step 2.

    It seems that my algorithm requires scanning the ratings array once to construct the tree map, and then scan the tree map once to calculate the results. Thus, the time complexity should be O(N). However, it will exceed the time limit. Any idea?

    	public static int candy(int[] ratings) {
    	if (ratings.length == 0) return 0;
    	int[] candies = new int[ratings.length];
    	int count = 0;
    	// Key: rating value; Value: all the corresponding child indices
    	TreeMap<Integer, ArrayList<Integer>> tm = new TreeMap<Integer, ArrayList<Integer>>();
    	for (int i = 0; i < ratings.length; i++) {
    		if (!tm.containsKey(ratings[i])) {
    			ArrayList<Integer> list = new ArrayList<Integer>();
    			list.add(i);
    			tm.put(ratings[i], list);
    		} else {
    			ArrayList<Integer> list = tm.get(ratings[i]);
    			list.add(i);
    		}
    	}
    
    	// traverse the tree map by the rating level
    	Set<Integer> set = tm.keySet();
    	for (int rating : set) {
    		ArrayList<Integer> list = tm.get(rating);
    		for (int index : list) {
    			candies[index] = 1;
    			// check if the candies are more than the left neighbor
    			if (index - 1 > 0 && ratings[index] > ratings[index - 1]
    					&& candies[index] <= candies[index - 1]) {
    				candies[index] = candies[index - 1] + 1;
    			}
    			// check if the candies are more than the right neighbor
    			if (index + 1 < ratings.length
    					&& ratings[index] > ratings[index + 1]
    					&& candies[index] <= candies[index + 1]) {
    				candies[index] = candies[index + 1] + 1;
    			}
    			count += candies[index];
    		}
    	}
    	return count;
    }

  • 2
    S

    Once you think of this problem in a sorting way, you may get the wrong approach considering that almost all sorting methods take at least O(nlogn) time. I didn't really read your code, so it might be not that correct, but I should point it out that your iterating the n elements and building a map does not necessarily mean you can do it in O(n) because the elements in your map is sorted!!! A more clear approach is to build a PriorityQueue which is more suitable for this problem, but unfortunately, the time complexity is still O(nlogn), which seems to be that good. BTW, this problem can be solved in O(n) time complexity.


  • 0
    W

    You're right. I ignored that the insertion operation cost is O(logN) rather than O(1). Thanks for your insightful comment.


Log in to reply
 

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