0

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]

enter image description here

One of the techinque to solve this would be to run DFS from each cell in the matrix and check if the array exists or not but that method will be O(n^4) (because there might be n^2 iteration in each DFS run).

Is my Time complexity analysis correct? Also can we do better than this?

code_it
  • 131
  • 7

1 Answers1

0

This is the most optimize solution for this issue...

let print = console.log

print("Result:", contain([1, 10, 22, 47, 33, 10], [
    [1, 2, 3, 5, 8],
    [6, 5, 10, 22, 47],
    [20, 21, 1, 54, 33],
    [45, 8, 6, 5, 10]
]));

function* findPoint(firstItem, matrix) {
    for (let y = 0; y < matrix.length; y++)
        for (let x = 0; x < matrix[y].length; x++)
            if (firstItem == matrix[y][x])
                yield [y, x]
}

function contain(path, matrix) {
    let startPoint = path.shift(), lastIndex = path.length - 1;
    main_loop: for (let [y, x] of findPoint(startPoint, matrix)) {
        print("find point:", startPoint, "coordinate:", [y, x]);
        loop: for (let i = 0; i < path.length; i++) {
            let point = path[i];
            // calculate sibling point: 
            for (let [_y, _x, dir] of [[y - 1, x, "up"], [y + 1, x, "down"], [y, x - 1, "left"], [y, x + 1, "right"]]) {
                // get item from matrix using point
                if (matrix[_y]?.[_x] != point) continue
                print("next point:", point, "Direction:", dir)
                if (lastIndex == i) return true
                y = _y, x = _x;
                // if sibling point matched, then update point and continue `root` loop
                continue loop;
            }
            print('point:', point, `didn't matched any sibling`);
            continue main_loop;
        }
    }
    return false
}

Time complexity is linear: O(n),

Nur
  • 2,361
  • 2
  • 16
  • 34