How do I analyze the time complexity of my method(TLE)?


  • 0
    L

    This problem is very similar to 322 Coin Change. So I come up with the following method. But I am not sure why it exceeds time limit and I don't know how to analyze the time complexity. Can someone help me with it?

    public int numSquares(int n) {
           int[] nums = new int[(int) Math.sqrt(n)];
           for(int i = 0; i < nums.length; i++) nums[i] = (i + 1) * (i + 1); // make coins array
           return coinExchange(nums, nums.length - 1, n);
    }
    
    private int coinChange(int[] coins, int i, int total) {
    	if (total == 0) return 0;
    	if (i < 0) return -1;
    	int min = Integer.MAX_VALUE;
    	int count = 0;
    	int cur;
    	while(total - count * coins[i] >= 0) {
    	     cur = coinChange(coins, i - 1, total - count * coins[i]);
    	     if (cur >= 0 && count + cur < min) min = count + cur;
    	     count++;
            }
    	return min;
    }
    

Log in to reply
 

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