CODEWITHSUNDEEP
javascriptmatrixmultidimensional-arrayarea
zstefanova
zstefanova

Reputation: 1831

Javascript - Find largest area in a matrix

The task is: Find the largest area of identical numbers in a matrix.

The matrix is hardcoded and i have the following code so far. 

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<script type="text/javascript">
    /* ---- Function that prints a matrix and finds the largest area and its value  ---- */
            function LargestAreaMatrix() {

                var matrix = [[1,3,2,2,2,4],
                              [4,3,2,2,4,4],
                              [4,4,1,2,3,3],
                              [4,3,1,2,3,1],
                              [4,3,3,2,2,1]];

                var arrSize = matrix.length;
                var itemSize = matrix[0].length;
                var counter = {};

                for (var i = 0; i < arrSize; i++ ){
                    for (var j = 0; j < itemSize; j++) {
                                //if the current element is equal to the next element   
                                if (matrix[i][j] == matrix[i][j+1]) {
                                    //to the object "key" is assigned the current value of the matrix and the "value" is incrementing till the condition is true  
                                    counter[matrix[i][j]] = 1 + (counter[matrix[i][j]] || 0);
                                    console.log("Right neighbor: "+ matrix[i][j] + " - ij: " + i + " " + j);
                                } 
                                if (typeof(matrix[i+1]) != "undefined" ) {
                                    //if the current element is equal to the bottom element
                                    if (matrix[i][j] == matrix[i+1][j]) {
                                        // the value of the specific key is incrementing
                                        counter[matrix[i][j]] = 1 + (counter[matrix[i][j]] || 0);
                                        console.log("Down neighbor:  "+ matrix[i][j] + " - ij: " + i + " " + j);
                                    }
                                } else {
                                    console.log("Not a neighbor: "+ matrix[i][j] + " - ij: " + i + " " + j);
                                } 
                    }//end of for j
                }//end of for i


                console.log("Neighbors count: ");
                console.log(counter);   


                //Printing the array with an html table
                var table = '<table border="0">';
                for (var i = 0; i < matrix.length; i++) {
                    table += '<tr>';
                    for (var j = 0; j < matrix[i].length; j++) {
                        table += '<td>' + matrix[i][j] + '</td>';
                    }
                    table += '</tr>';
                }
                table += '</table>';

                document.getElementById('matrix').innerHTML = table;
            }
</script>
</head>
<body>
<p></p>
<p><a href="#" onClick="LargestAreaMatrix();">Largest Area Matrix</a></p>
<label name="matrix" id="matrix"> </label>
</body>
</html>

I made 2 loops for going through the matrix where i check for right and down neighbors. If there are any - i use an object to put the value of the matrix for a key, while the object value is incrementing with the count of the key. So in the end i have the count of the neighbors for every value.

My questions: For some reason, in the outside loop, where "i" hits 4 (the matrix size) both the second if and the else are executed. Why is this happening? Also - I am still trying to figure out how to make it count only the largest area, not all the neighbors for a specific value.

I will appreciate any help. Thanks!

Update:

So it turned out to be simpler than i thought it will be :) Here is the recursive function i made to count the size of each area: 

                function findNeighbors(row, col, item){
                if(row < 0 || col < 0 || row > (arrSize - 1) || col > (itemSize - 1)) {
                    return 0;
                }

                if(matrixZero[row][col] == 1) {
                    return 0;
                }

                if(item == matrix[row][col]){
                    matrixZero[row][col] = 1;
                    tempCount = 1 + (findNeighbors(row, col+1, matrix[row][col]) || 0) + (findNeighbors(row+1, col, matrix[row][col]) || 0) + (findNeighbors(row, col-1, matrix[row][col]) || 0) + (findNeighbors(row-1, col, matrix[row][col]) || 0);
                    return tempCount;
                }
            }

First i check if the current item is in the matrix range, if not - 0 is added to the tempCount value. Then i check if the item is already visited, if yes - 0 is added to the temp. Then if the item in neither visited, neither out of the matrix i check it as visited and add 1 to the temp and etc.

Then in a simple for I compare the tempCount value with the current max value and i switch them if temp is higher than max.

Thanks everyone for the help!

Upvotes: 2

Views: 2356

Answers (2)

Magus
Magus

Reputation: 15124

I don't think you code is doing something weird. But maybe you are not using the best logic for that. Here's a working function. If you are a beginner, you can read this code.

function LargestAreaMatrix() {

  var matrix = [[1,3,2,2,2,4],
                [4,3,2,2,4,4],
                [4,4,1,2,3,3],
                [4,3,1,2,3,1],
                [4,3,3,2,2,1]];

  var cache = {};

  function pulse(x, y) {
    var queue = [],
        visited = {},
        size = 0;

    // Current cell is the first element
    queue.push({
      'x' : x,
      'y' : y
    });
    visited[x + ' ' + y] = true;
    size = 1;

    function test(x, y, value) {
      if (!visited[x + ' ' + y] && y >= 0 && y < matrix.length && x >= 0 && x < matrix[y].length && matrix[y][x] == value) {
        queue.push({
          'x' : x,
          'y' : y
        });
        visited[x + ' ' + y] = true;
        size += 1;
      }
    }

    while (queue.length) {
      var cell = queue.pop(),
          value = matrix[cell.y][cell.x];

      // Add neighbors of the same value to the queue
      test(cell.x - 1, cell.y, value);
      test(cell.x + 1, cell.y, value);
      test(cell.x, cell.y - 1, value);
      test(cell.x, cell.y + 1, value);
    }

    // Cache the size for all visited cells for performances
    for (var key in visited) {
      cache[key] = size;
    }

    return size;
  }

  var max = 0;

  for (var y = 0; y < matrix.length; ++y) {
    for (var x = 0; x < matrix[y].length; ++x) {
      if (!cache[x + ' ' + y]) {
        var size = pulse(x, y);

        if (size > max) {
          max = size;
        }
      }
    }
  }

  console.log('Largest area size', max);
}

Upvotes: 2

meshlet
meshlet

Reputation: 1507

I ran your code and it's not that second if and else are executed, but first if and else part of second if statement.

So in the first if you discover that matrix(i,j) is right neighbour and then you go on testing for the down neighbour in the second if statement. However, as i = 4 at this point you're trying to access row i+1 has to produce undefined as there is no 6th row in the matrix. That's why both first if and else part of second if are hit. Something wrong with the logic I guess..

Upvotes: 1

Related Questions