3
\$\begingroup\$

I coded two answers to this challenge. The first one was a standard attempt, but after it timed out, I figured out the "trick" to solving the problem much more simply. However, I'd still appreciate comments and critiques on my first attempt, because there will be other problems that will need a long approach and I'd like to improve how I'd code the answer.

Challenge Julia is playing a game on an infinite 2-dimensional grid with the bottom left cell referenced as (1, 1). All the cells contain a value of zero initially. The game consists of n steps. In each step, Julia is given two integers a and b. The value of each of the cells in the coordinate (u, v) satisfying 1 ≤ u ≤ a and 1 ≤ v ≤ b, is increased by 1. After n such steps, if x is the largest number in any cell on the board, how many instances of x are there on the board?

Complete the function countX that has one parameter, a string array, steps, denoting the values of a and b for each of steps of the game. The function should return the total number of occurrences of greatest integer x in the grid after n steps.

Sample Input and Output *
Input: [ '18 29', '32 17', '34 9', '38 15', '36 22', '7 14', '5 100' ]
Output: 2

First Attempt

function countX(stepArr){
    let board = []; //2 dimensional array
    let bigNum = 0;
    let bigNumCount = 0;        

    const stepArrCount = stepArr.length;

     for(let k = 0; k < stepArrCount; k++){
        const sArr = stepArr[k].split(" ");
        let s1 = sArr[0]; //vertical steps
        let s2 = sArr[1]; //horiz steps

        for(let i = 0; i < s1; i++){
            let stopCompare = false;
            for(let j = 0; j < s2; j++){
                if(board[i] !== undefined){
                    if(board[i][j] !== undefined){
                        board[i][j]++;
                    }
                    else{
                        board[i][j] = 1;
                    }
                }
                else{
                    board[i] = [];
                    board[i][j] = 1;
                }
                if((k + 1 === stepArrCount) && !stopCompare){
                    if(board[i][j] > bigNum){
                        bigNum = board[i][j];
                        bigNumCount = 1;
                    }
                    else if(board[i][j] === bigNum){
                        bigNumCount++;
                    }
                    else{
                        stopCompare = true;
                    }
                }
            }
        }
     }

    return bigNumCount;
}

Second Attempt

function countX(stepArr){
    let sArr = stepArr[0].split(" ");
    let smallColA = parseInt(sArr[0]);
    let smallColB  = parseInt(sArr[1]);

    if(sArr.length > 1){
        for(let i = 1; i < stepArr.length; i++){
            sArr = stepArr[i].split(" ");
            let s1 = parseInt(sArr[0]);
            let s2 = parseInt(sArr[1]);
            if(s1 < smallColA){
                smallColA = s1;
            }
            if(s2 < smallColB){
                smallColB = s2;
            }
        }
    }

    return smallColA * smallColB;

}

* Explanation of Input and Output (provided by challenger)
Assume that the following board corresponds to cells (i, j) where 1 ≤ i ≤ 4 and 1 ≤ j ≤ 7. At the beginning the board is in the following state:

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0 

After the first step we obtain:

0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 1 1 0 0 0 0
1 1 1 0 0 0 0 

After the second step we have:

0 0 0 0 0 0 0
1 1 1 1 1 1 1
2 2 2 1 1 1 1
2 2 2 1 1 1 1 

Finally, after the last step the board will look like this:

1 0 0 0 0 0 0
2 1 1 1 1 1 1
3 2 2 1 1 1 1
3 2 2 1 1 1 1 

So, the maximum number is 3 and there are exactly two cells which contain 3. Hence the answer is 2.

\$\endgroup\$
  • \$\begingroup\$ Why are the 2-vectors in the input sequence encoded as strings of digits instead of arrays of integers? Wouldn't it be simpler and more efficient to have [[18, 29], [32, 17], ...]? Ó.ò (not a criticism of the question but of the proposition of the challenge) \$\endgroup\$ – David Foerster Dec 4 '16 at 23:32
  • \$\begingroup\$ The sample output seems wrong, and the explanation for why it's right seems to be processing a completely different input to the one given. \$\endgroup\$ – Peter Taylor Dec 5 '16 at 19:38
  • \$\begingroup\$ @dmr - It would be great if you can explain your second solution. How multiplication of min values will get the desired result. \$\endgroup\$ – Hacker Mar 21 '18 at 12:57
2
\$\begingroup\$

The second solution

If the input array is empty, the program will crash with an exception.

It's recommended to specify the radix to parseInt calls:

let smallColA = parseInt(sArr[0], 10);

The if(sArr.length > 1){ condition is unnecessary, the loop condition naturally takes care of that.

Even better, no need to treat the first element specially, you can initialize smallColA and smallColB to Infinity. Not only it will be simpler, but in it will work even when the input array is empty.

The first (naive) solution

You could write this simpler:

if(board[i][j] !== undefined){
    board[i][j]++;
}
else{
    board[i][j] = 1;
}

... using a technique you already used in your other recent question:

board[i][j] = (board[i][j] || 0) + 1;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.