Why would BFS method in Java be TLE?


  • 0
    L

    I used the idea from this post. But it exceeds time limit. Does anyone have an idea about this?

    public class Solution {
        public int numSquares(int n) {
    	    Queue<Integer> list = new LinkedList<>();
            list.add(n);
            int count = 0;
            while(!list.isEmpty()) {
                count++;
                int size = list.size();
                while(size > 0) {
                    int cur = list.poll();
                    for (int i = 1; i * i <= n; i++) {
                        if (cur == i * i) return count;
                        if (cur < i * i) break;
                        list.add(cur - i * i);
                    }
                    size--;
                }
            }
            return count;
        }
    }
    

  • 0
    N

    @Lingyao said in Why would BFS method in Java be TLE?:

    I used the idea from this post. But it exceeds time limit. Does anyone have an idea about this?

    I think that is because within the loop, you check i from 1 all the way to i * i <= n, which makes it slower since intuitively you should check from the last, i.e. i * i <= n all the to the beginning.


Log in to reply
 

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