Блог пользователя uttaran_das

Can anyone help me understand why this solution for the problem LeetCode 3629 is giving TLE?
Автор uttaran_das, история, 9 месяцев назад, По-английски

Problem link: Minimum jumps to reach end via prime teleportation

My solution:

class Solution {
    public int minJumps(int[] nums) {
        int maxVal = 1000_000;
        int[] spf = new int[maxVal + 1];
        for (int i = 2; i <= maxVal; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                for (long j = (long) i * i; j <= maxVal; j += i) {
                    if (spf[(int) j] == 0) {
                        spf[(int) j] = i;
                    }
                }
            }
        }
        int n = nums.length;
        HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int temp = nums[i];
            while (temp > 1) {
                int p = spf[temp];
                if (!hm.containsKey(p))
                    hm.put(p, new ArrayList<>());
                hm.get(p).add(i);
                while (temp % p == 0)
                    temp /= p;
            }
        }
        Queue<Integer> q = new LinkedList<>();
        boolean[] visitedPrime = new boolean[maxVal + 1];
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[0] = 0;

        q.add(0);

        while (!q.isEmpty()) {
            int u = q.poll(), c = dist[u];

            if (u == n - 1)
                return c;

            if (u - 1 >= 0 && dist[u - 1] == -1) {
                dist[u - 1] = c + 1;
                q.add(u - 1);
            }
            if (u + 1 < n && dist[u + 1] == -1) {
                dist[u + 1] = c + 1;
                q.add(u + 1);
            }

            if (spf[nums[u]] == nums[u] && !visitedPrime[nums[u]]) {
                visitedPrime[nums[u]] = true;
                for (int idx : hm.getOrDefault(nums[u], new ArrayList<>()))
                    if (idx != u && dist[idx] == -1) {
                        dist[idx] = c + 1;
                        q.add(idx);
                    }
            }
        }

        return -1;
    }
}
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

First for loop itself is going to the order of 10^9, you don’t need to go to that order, for all prime numbers p <= 1000 , there will be edge from p to 2*p … until 1000000,if there no edge to an index means it’s a prime number . There are 168 prime less than 1000, that should avoid TLE. The problem boils down to finding prime numbers up to 10^6 , you don’t need store the edges in adjacency list, you can generate them on the fly.

→ Ответить
  • »
    »
    9 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Isn't sieve O(n log log n)? That makes the loop 5*10^7 at most. Should be good enough to pass.

    → Ответить
    • »
      »
      »
      9 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      It isn't about primes or something, my code fails because say in a dense graph where all numbers in list are equal there would be n**2 edges. That won't be sufficient to traverse through DFS or BFS.

      → Ответить
      • »
        »
        »
        »
        9 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Not sure if you are talking about my code or your code. But if you are talking about my code, for this case I use the visitedPrime flag array.

        → Ответить
        • »
          »
          »
          »
          »
          9 месяцев назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится

          I was talking about my code. You can not precompute which edges to connect s it would be O(n**2). Do it on the go and a BFS suffices. Just quit the loop when the node n-1 is visited. Here is CPP code


          #define p pair<int,int>
#define pb push_back

class Solution {
public:
    int mini=INT_MAX;
    vector<int> visited;
    int n;
    vector<int> nums;
    unordered_map<int,vector<int>> pos;
    
    void bfs(int x, int l){
        queue<p> qu;
        qu.push({x,l});
        bool done=false;
        while (qu.size()){
            p pa=qu.front();
            qu.pop();
            x=pa.first;
            l=pa.second;
            if (x==n-1){
                mini=l;
                break;
            }
            vector<int> adj;
            if (x!=0) adj.pb(x-1);
            if (x!=n-1) adj.pb(x+1);
           
            if (pos.count(nums[x])){
                for (int j:pos[nums[x]]){
                    if (j!=x) adj.pb(j);
                }
            }
            for (int i:adj){
                if (visited[i]) continue;
                visited[i]=1;
                if (i==n-1) {
                    mini=l+1;
                    done=true;
                    break;
                }
                qu.push({i,l+1});
            }
            if (done) break;
        }
        
        
    }
    int minJumps(vector<int>& num) {
        int x;
        nums=num;
        n=nums.size();

        for (int i=0; i<n; i++){
            x=nums[i];
            while (x!=1){
                bool flag=false;
                for (int j=2; j*j<=x; j++){
                    if (x%j==0){
                        pos[j].pb(i);
                        while (x%j==0) x/=j;
                        flag=true;
                        break;
                    }
                }
                if (!flag) break;
            }
            if (x!=1) pos[x].pb(i);
        }
        
        visited=vector<int>(n,0);
        visited[0]=1;
        bfs(0,0);
        
        return mini;
    }
};
          → Ответить
      • »
        »
        »
        »
        9 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Where is your solution? BFS got accepted for me


        func minJumps(nums []int) int {
    n := len(nums)
    
    maxV := 0
    for _, v := range nums {
        if v > maxV {
            maxV = v
        }
    }
    spf := make([]int, maxV+1)
    for i := 2; i <= maxV; i++ {
        if spf[i] == 0 {
            for j := i; j <= maxV; j += i {
                if spf[j] == 0 {
                    spf[j] = i
                }
            }
        }
    }

    isPrime := make([]bool, maxV+1)
    for i := 2; i <= maxV; i++ {
        isPrime[i] = (spf[i] == i)
    }

    tele := make(map[int][]int)
    for j, v := range nums {
        seen := map[int]bool{}
        for x := v; x > 1; x /= spf[x] {
            p := spf[x]
            if !seen[p] {
                tele[p] = append(tele[p], j)
                seen[p] = true
            }
        }
    }

    dist := make([]int, n)
    for i := range dist {
        dist[i] = -1
    }
    dist[0] = 0
    queue := make([]int, 0, n)
    queue = append(queue, 0)

    for qi := 0; qi < len(queue); qi++ {
        i := queue[qi]
        d := dist[i]
        if i == n-1 {
            return d
        }

        for _, ni := range []int{i - 1, i + 1} {
            if ni >= 0 && ni < n && dist[ni] == -1 {
                dist[ni] = d + 1
                queue = append(queue, ni)
            }
        }

        v := nums[i]
        if v >= 2 && isPrime[v] {
            for _, j := range tele[v] {
                if dist[j] == -1 {
                    dist[j] = d + 1
                    queue = append(queue, j)
                }
            }
            delete(tele, v)
        }
    }

    return -1
}
        → Ответить
  • »
    »
    9 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    This is taking 0.1 seconds 


    public class PrimeSieve {
    public static List<Integer> sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }

        return primes;
    }

    public static void main(String[] args) {
        int limit = 1_000_000;
        List<Integer> primes = sieve(limit);
        System.out.println("Total primes up to " + limit + ": " + primes.size());
        // Uncomment below to print all primes
        // System.out.println(primes);
    }
}
    → Ответить
»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

There is not much wrong with your solution, on Leetcode time limit is combined for all test cases but you calculating primes up to 1000000 even for small test cases

→ Ответить