HackerRank Grid Search challenge

Question

I’ve written an answer for The Grid Search challenge on HackerRank. Please let me know of any improvements that can be made to my implementation (specifically if there's any way to make the algorithm more efficient. I'd like to make this algorithm optimal).

P.S: My implementation is a brute force algorithm, and I reckon that there's a much better way of solving this problem. But, as the grid is unsorted, I'm not exactly sure what that better method would be.

Problem statement (as written on HackerRank):

Given a 2D array of digits, try to find the location of a given 2D pattern of digits.

Answer:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        try(BufferedReader input = new BufferedReader(new InputStreamReader(System.in))){
            int numTestCases = Integer.parseInt(input.readLine());
            assert numTestCases >= 1 && numTestCases <= 5;
            int[][] grid;
            int[][] pattern;

            for(int t = 0; t < numTestCases; t++) {
                grid = solution.buildArray(input);
                pattern = solution.buildArray(input);
                // Gotta STDOUT in HackerRank for problem to be graded.
                System.out.println(solution.findPattern(grid, pattern));
            }
        }catch(IOException e){
            e.printStackTrace();
        }
    }

    /**
     * Determines whether pattern exists in grid.
     *
     * @param grid       2D array of digits
     * @param pattern    the 2D sequence of digits to be found in grid
     * @return "YES" if grid contains pattern. "NO" if not.
     */
    public String findPattern(int[][] grid, int[][] pattern){
        // R, C, r, & c are the same letters used in the problem
        for(int R = 0; R < grid.length - pattern.length + 1; R++){
            for(int C = 0; C < grid[0].length - pattern[0].length + 1; C++){
                outerLoop:
                for(int r = 0; r < pattern.length; r++){
                    for(int c = 0; c < pattern[0].length; c++){
                        if(grid[R + r][C + c] != pattern[r][c]){
                            break outerLoop;
                        }
                    }
                    if(r == pattern.length - 1){
                        return "YES";
                    }
                }
            }
        }
        return "NO";
    }

    /**
     * Builds and returns an array built according to data received from STDIN.
     *
     * @param input    STDIN stream
     * @return a 2D primitive array containing 0-9 digits
     * @throws IOException
     */
    public int[][] buildArray(BufferedReader input) throws IOException {
        String[] sizeParameters = input.readLine().split(" ");
        int rows = Integer.parseInt(sizeParameters[0]);
        int columns = Integer.parseInt(sizeParameters[1]);
        int[][] array = new int[rows][columns];

        for(int i = 0; i < rows; i++){
            String rowOfNumbers = input.readLine();
            for(int j = 0; j < columns; j++){
                array[i][j] = Character.getNumericValue(rowOfNumbers.charAt(j));
            }
        }

        return array;
    }

}

Answer 1

Code organization

This is usually a cause for concern:

Solution solution = new Solution();

Programming contests do not generally require much object design. And in this particular case, instance methods just obfuscate reading. Make them public static. And if it gets so big that you need to divvy it up, do it properly, then.

This is usually a cause for concern, too:

    }catch(IOException e){
        e.printStackTrace();
    }

Just throw the exception, if you cannot do anything with it. And some automated judges show you the STDERR but not STDOUT, so you may be wasting your chance to see whether something went wrong or you returned wrong answer, and what went wrong. (Just knowing if your program has thrown an exception is good. If the automated judge does not support exception but supports process exit codes, you do a System.exit if an exception thrown.)

Performance

Some contests test your code with just small and large data sets, which means you need to find and algorithm with good average complexity. Some contest, such as ACM, tests the code also with the known worst case scenarios of the best known algorithms that could be used to solve the problem. In that case you need to find good worst case complexity.

Some contests have inputs to weed out naive implementations as your current one. One such case would be 1000X1000 grid of 1s, and 500X500 pattern of 1s with a 2 in the bottom right corner. Against such a case you can try an algorithm like :

• Scan the pattern, find the row with most diversity (e.g. with the most elements which have a different value to its right)
• for each row in the grid do a KMP substring search.
• for each match compare the rest of the pattern in the grid, using the row and column offset of the match.

Which, I believe, will have a complexity : O(R(C+c) + m(rc)), where m is the number of the matches for the pattern row used; which can still be bad for large m. In that case you can do a search for a pattern column in parallel (real or simulated).

Answer 2

Before starting with

for (int r = 0; r < pattern.length; r++) {

You can add one more check:

if (grid[R + r][C + c] == pattern[r][c]) {
    //only then start comparing
}

By doing this check, you can avoid unnecessary iterations of the inner for loops(the ones which compare the pattern)