Given start, end and an array arr of n numbers. At each step, start is multiplied with any number in the array and then mod operation with 100000 is done to get the new start.

Your task is to find the minimum steps in which end can be achieved starting from start. If it is not possible to reach end, then return -1.

n<=1e4, arr[i]<=1e4, start, end<1e5

Expected Time & Space Complexity : O(1e5)

class Solution {
  public:
    int minimumMultiplications(vector<int>& v, int s, int d) {
        int n = v.size();
        int MOD = 1e5;
        queue<pair<int,int>>q; q.push({s,0});
        vector<int>vis(1e5); vis[s]=1;
        while(!q.empty()){
            auto elem = q.front(); q.pop();
            int i = elem.first; int res = elem.second;
            if(i==d) return res;
            for(int j=0;j<n;j++){
                int val = (i*v[j])%MOD;
                if(!vis[val]) {
                    vis[val] = 1;
                    q.push({val,res+1});
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
    
        vector<vector<int>> dp(n, vector<int>(m, INT_MAX - 100000));
        
        // First pass: Top-left to bottom-right
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
                    if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
                }
            }
        }
        
        // Second pass: Bottom-right to top-left
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                if (i < n - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
                if (j < m - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
            }
        }
        
        return dp;
    }
};

Why does it work ? I understood a little by doing some dry runs but still not able to get the complete feel. If you know any other similar problem, please do share it.

I also want to know if there exists more unique/different dp traversals like these to solve particular problems. Eg. maybe a clockwise and anticlockwise traversal.

I also couldn't write the memoized recursive solution, If you can help me with that, that'd be of great help.

I have a fear of "What if it requires some ideas that i'm unaware of". I'm pretty good at applying known/slightly modified ideas, I have scored 99.9 %ile in my country's university entrance test by just applying the know ideas. I can think of new ideas but they must be somewhat similar to the previous ones.

In the past one month, my peak went ~ +200. My goal is to get better, even though I haven't given any contests on this (my main) acc, I started with a new account and achieved 1590 rating last contest. I want to get to the master level.

English is not my first language, Sorry If I was not clear in explaining my situation. Sorry for any grammatical mistakes.