1

I am doing a BFS on a matrix and using a Set to hold the values that I have seen before. I created the class Tuple with the values row and column. The issue I am running into is that the seen Set will add repeated points on the matrix because it is a different Tuple object with the same points. I have solved this problem before with just recursion but I am more interested in playing around with stacks and queues to solve problems like this. I have am not sure if I have to iterate through each Tuple but that sounds time inefficient. This code below does run but I am trying to optimize the solution by not having to add unnecessary points. Any advice would be SUPER appreciated. This is the flood fill problem https://leetcode.com/problems/flood-fill/

public  int[][] floodFillQueue(int[][] array, int startRow, int startColumn, int newColor){

    Queue<Tuple> queue = new LinkedList<>();
    Set<Tuple> seen = new HashSet<>();
    Tuple startPoint = new Tuple(startRow, startColumn);
    queue.add(startPoint);
    int startColor = array[startRow][startColumn];
    
    while(!queue.isEmpty()){

        
        Tuple current = queue.poll();
        if(array[current.row][current.column] == startColor){
            array[current.row][current.column] = newColor;
        }
        List<Tuple> neighbors = findNeighbors(array, current);
        for(int i = 0; i < neighbors.size(); i++){
            if(array[neighbors.get(i).row][neighbors.get(i).column] == startColor && !seen.contains(neighbors.get(i))){
                queue.add(neighbors.get(i));
            }
        }
    }

    return array;
hcam93
  • 11
  • 2
  • Hello, did you override `hashCode` and `equals` methods in your Tuple class so that Tuple instances could be properly stored in Set/used as a key in Map? – Nowhere Man Sep 27 '20 at 11:07
  • No, I didn't do that. I didn't know I had to do that in order to properly store in a Set. – hcam93 Sep 29 '20 at 21:40
  • 1
    This ended up being the solution! Thank you so much for your help! – hcam93 Sep 30 '20 at 16:08

0 Answers0