CODEWITHSUNDEEP
algorithmsearchmatrix
Daniel
Daniel

Reputation: 87

Search for a sequence in a 2D array (visit each entry only once)

This is a problem from the book "Elements of Programming Interviews" (17.5). The problem is:

When A is a matrix and S is an array of integers, we say S occurs in A if you can start from some entry in A and traverse adjacent entries in A in the order prescribed by S. Adjacent entries are top, bottom, left and right ones.

For example, if A =

[1 2 3

3 4 5

5 6 7]

S = [1 3 4 6]

Then S is in A, because A[0][0] = 1, A[1][0] = 3, A[1][1] = 4, A[2][1] = 6

But if S = [1 2 3 4] then S is not in A.

I understand how to solve the problem using recursion if it is acceptable to visit an entry in A more than once.

But how can I solve the problem efficiently, if there is an additional constraint that each entry can be visited at most once?

Upvotes: 2

Views: 2304

Answers (2)

Pedro Lopes
Pedro Lopes

Reputation: 2883

If visit is to be interpreted as "not visiting the cell in a given sequence", this is, the cell can be visited multiple times during the algorithm, then the best solution I can conjure has exponential time complexity I believe.

The gist of it to keep track of the visited cells along a given path:

from typing import Set, Tuple

def is_pattern_contained_in_grid(grid, S):
    def traverse(x, y, s_idx, visited: Set[Tuple[int,int]]):
        if (s_idx == len(S)):
            return True

        if ((x, y) in visited
            or not( x >= 0 and y >= 0 and x < n and y < m)
            or grid[x][y] != S[s_idx]):
            return False

        for adj_x, adj_y in ((x + 1, y),
                        (x - 1, y),
                        (x, y + 1),
                        (x, y - 1)):
            if (traverse(adj_x, adj_y, s_idx + 1, visited.union({(x,y)}))):
                return True

        return False


    if (not S):
        return True

    n = len(grid)
    m = len(grid[0])
    for i in range(n*m):
        x = i % n
        y = i // n
        if (traverse(x, y, 0, set())):
            return True

    return False

# Some examples
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,7],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,5,6]))

Upvotes: 0

shole
shole

Reputation: 4094

It is straight forward Depth First Search (DFS) problem.

Here is the outline of the algorithm:

  1. Find all elements which is equal to S[0] (first number in the sequence)
  2. For all elements found in step 1 which is not visited, do a DFS, marked node as visited. Only visit adjancent node iff it is not visited AND it is the next number in the sequence

Each node is visited at most once in step 2. For example, a tough case is like

S = [1,2,3,4]

A = [1,2,1]
    [2,3,2]
    [3,2,1]

This case there is no answer, and all nodes are visited exactly once:

// After first DFS starting at [0,0],  1 = visited, 0 = not visited
V = [1,1,0]
    [1,1,0]
    [1,0,0]
// After second DFS starting at [0,2], 1 = visited, 0 = not visited
V = [1,1,1]
    [1,1,1]
    [1,0,0]
// After third DFS starting at [2,2], 1 = visited, 0 = not visited
V = [1,1,1]
    [1,1,1]
    [1,1,1]
// Done, complexity = O(N*M) where the matrix is of size N X M

Here is a sample code written in C++: http://ideone.com/ganX9Z

Upvotes: 1

Related Questions