tiiooo's blog

By tiiooo, history, 2 months ago, In English

Given an array and a 2d matrix. You have to find if the array is present in the matrix or not.To do so, you can start from any point in the matrix and go in 4 directions that is if you are at (i,j) you can go to (i+1,j), (i-1,j), (i,j+1), (i,j-1).

Return the starting and ending pairs of indices if the array exists otherwise return false.

Suppose the given array is [ 1, 10, 22, 47, 33, 10] and the matrix is as given below..then as we can see the array exists in the matrix and the starting and ending points respectively are: (2,2) and (3,4) [ 0-based indexing]

What will be the efficient solution ,i mean what will be the time complexity ?

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this may be solvable by DP.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    nah its graph theory

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yeah, that is correct.

    Let $$$A$$$ be the matrix and $$$B$$$ be the array. Now, the DP states can be defined as follows: $$$\mathrm{dp}[i][j][k]$$$ is true if the array $$$B[0] \ldots B[k]$$$ exists in the matrix and ends at the cell $$$(i, j)$$$. The DP table can be calculated like this: $$$\mathrm{dp}[i][j][k]$$$ should be true only if $$$A[i][j] = B[k]$$$ and $$$\mathrm{dp}[\cdot][\cdot][k - 1]$$$ is true for some neighbor of $$$(i, j)$$$.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      what about dp[.][.][k-1] was true for some neighbour but current (i,j) was already used in making it true for that neighbour. e.g. array is [1, 2, 3, 2, 4] and matrix is [[5 4],[1 2],[6 3]]

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

           (take matrix from above example if image doesn't load) for this matrix A and array B [1, 2, 3, 2, 4]. dp[2][1][2] would be true. Also A[1][1]==B[3] and (2,1) is a neighbour of (1,1), sp dp[1][1][3] will also become true which is not right. Am I missing something?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Why is dp[1][1][3] being true not correct?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              dp[1][1][3] being true is correct if same element in the matrix can be taken twice to form the array

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                Yeah, I see no constraint in the statement that forbids us from taking the same element twice so I'm going to assume that it is allowed.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give detailed constraints of the problem? If the array length is small enough, then I can just use a simple brute-force solution.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

dfs from every (i,j) looks like the only solution

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    One issue there is if the array is filled with 1s except for maybe the bottom right corner is a 2, and the array is also filled with 1s except the last element is 2 then you have an exponential number of paths with only 1s to get through before you confirm that one of them ends in a 2. Obviously that particular case can be hardcoded or something but in general dfs doesn't work when a graph can have an exponential number of paths, which is true in this grid.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My intuition is a BFS-ish approach where you start with a list of locations in the matrix equal to the first element in the array and for each element of the array you take the list of locations equal to the previous element and if there's an adjacent location equal to the current element add it to a new list. Then the answer would just be whether the list is non-empty. Complexity would be (elements in matrix) * (elements in array) but the approach fails if you're not allowed to go back to a square you've gone to previously.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess you can do dfs storing current cell, and position in array (dfs(x, y, pos)). Then you can save whether you was in that cell with current position in array, so complexity will be matrix size * array size, because so will visit each cell at most N (size of array) times.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is acmicpc india online round 2018 grid question, if we can revisit then it's as mentioned by its-fft else is brute force, also on Leetcode there is similar question with string and trie.