How to solve two dimensional growth grid problem?

Question

I was doing an assessment for job interview. One of the 3 problems that I had to solve in an hour was finding the maximal value in a grid where you traverse it and add 1 to the elements based on the coordinates given. I spent a little to much time on the second problem and only ended up with about 20 minutes for this one. I didn't finish it in time so it's bugging me.

I just want to make sure that the solution to the problem as I remember it is optimized.

The input is a String array of two int values and the dimension of the grid.

To illustrate, if the coordinates given are (3,2) (2,2) (1,3) then

[1][1][0]     
[1][1][0]     
[1][1][0]     

[1][1][0]     
[2][2][0]     
[2][2][0]     

[1][1][0]
[2][2][0]
[3][3][1]

and so on...

I believe the required result was the maximal value that is not in (1,1) and the number of times it exists in the grid.

This is the the solution I came up with. Is there any way to optimize it?

public static List<Integer> twoDimensions(String[] coordinates, int n) {

    List<Integer> maxAndCount = new ArrayList<Integer>();
    int[][] grid = new int[n][n];
    int arrLength = coordinates.length;
    int max = Integer.MIN_VALUE;
    int count = 1;

    for (int i = 0; i < arrLength; i++) {

        String[] coors = coordinates[i].split(" ");
        int row = Integer.parseInt(coors[0]);
        int column = Integer.parseInt(coors[1]);

        for (int j = 0; j < row; j++) {
            for (int k = 0; k < column; k++) {

                grid[j][k] += 1;
                System.out.println("grid (" + j + "," + k + "): " + grid[j][k]);

                if (!(j == 0 & k == 0) && grid[j][k] > max) {

                    max = grid[j][k];
                    count = 1;

                } else if (grid[j][k] == max) {

                    count++;

                }
            }
        }
    }

    maxAndCount.add(max);
    maxAndCount.add(count);

    return maxAndCount;
}

public static void main(String[] args) {

    String[] coors = { "1 3", "2 4", "4 1", "3 2" };
    System.out.println("The Max and count Are:" + twoDimensions(coors, 4).toString());
}

Answer 1

Other solution for exercise is. ([email protected])

public static long countMax(List<String> upRight) {
    // Write your code here
    int xl = 1;
    int yl = 1;

    xl = Integer.parseInt(upRight.get(1).split(" ")[0]);
    yl = Integer.parseInt(upRight.get(1).split(" ")[1]);

    for (int i=0; i<upRight.size(); i++){
        if (xl > Integer.parseInt(upRight.get((int) i).split(" ")[0]) ) xl = Integer.parseInt(upRight.get((int) i).split(" ")[0]);
        if (yl > Integer.parseInt(upRight.get((int) i).split(" ")[1])) yl = Integer.parseInt(upRight.get((int) i).split(" ")[1]);
    }

    return (yl * xl);
}

Answer 2

This fails a few test cases I can think of, the value of XL should be on Index 0 not 1

Answer 3

Answer of erik fails for few test cases, just change int to long for xl and yl and boom... all test cases passed.

Answer 4

public static long twoDimensions(List<String> list, int n) {
    long res = 0;
    int rowCount =0,colCount=0;
    for(int i=0;i<n;i++)
    {
        int row = list.get(i).charAt(0) - 48;
        int col = list.get(i).charAt(2) - 48;
        if(row > rowCount)
            rowCount = row;
        if(col >colCount)
            colCount = col;
    }
    int tempArr[][] = new int[rowCount+1][colCount+1];
    for(int i = 0;i<n;i++)
    {
        int row = list.get(i).charAt(0) - 48;
        int col = list.get(i).charAt(2) - 48;
        for(int j=row;j>=1;j--)
        {
            int m = j;
        for(int k=1;k<=col;k++)
        {
            tempArr[m][k]= tempArr[m][k]+1;
            if(tempArr[m][k]>res)
                res = tempArr[m][k];
        }
        }
        System.out.println("for row: "+row+" col: "+col);
        for(int j = 0;j<=rowCount;j++)
        {
            for(int k=0;k<=colCount;k++)
            {
                System.out.print(""+tempArr[j][k]);
            }
            System.out.println("");
        }
        System.out.println("");
    }
    return res;
    }