My solution to explore the space in O(n)


  • 0
    L

    My algorithm to find all the captured regions is divided into two steps, and is linear to the size of the problem.

    1). Go through the board to find all the 'O' cells and put them into a set, called space set. The elements in space set would be enumerated later in the second step. Once we enumerate all these elements, the algorithm is done.

    2). Pick an element from the space set, starting from this element, we explore in four directions, i.e. up, down, left and right to find all the connected 'O' cells. If any of these connected 'O' cells is located on the borders of the board, then these 'O' cells are not captured. While exploring, remove the elements from the space set. Once the set is empty, there is no more space to explore.

    Note: the reason why I keep the space set and do it in two rounds, is because the regions can be isolated from each other, the space set allows us to find the space quickly, and have the algorithm terminated in linear time.

    public void solve(char[][] board) {
    	if(board == null || board.length == 0){
    		return;
    	}
    	
    	HashSet<Integer> Oset = new HashSet<Integer>();
    	int rowSize = board.length;
    	int columnSize = board[0].length;
    	
    	// Identify 'O' and put them into a set
    	for(int i=0; i<board.length; i++){
    		for(int j=0; j<board[i].length; j++){
    			if(board[i][j] == 'O'){
    				Oset.add(i*columnSize + j);
    			}
    		}
    	}
    	
    	// Explore the space
    	while(true){
        	Iterator<Integer> iter = Oset.iterator();
        	if(!iter.hasNext()){
        		break;
        	}
        	
    		int k = iter.next();
    		LinkedList<Integer> explorer = new LinkedList<Integer>();
    		explorer.add(k);
    		LinkedList<Integer> space = new LinkedList<Integer>(); 
    		
    		boolean isCaptured = true;
    		while(! explorer.isEmpty()){
    			int p = explorer.poll();
    			Oset.remove(p);
    			space.add(p);
    			
    			// reach the boundary, therefore no capture. 
    			if(p % columnSize == 0  ||
    			   p % columnSize == columnSize-1 ||
    			   p / columnSize == 0 ||
    			   p / columnSize == rowSize-1 ){
    				isCaptured = false;
    			}
    			
    			
    			// check the next element on the left
    			if(Oset.contains(p-1)){
    				explorer.add(p-1);
    				Oset.remove(p-1);
    			}
    			
    			// check the next element on the right
    			if(Oset.contains(p+1)){
    				explorer.add(p+1);
    				Oset.remove(p+1);
    			}
    
    			// check the element on the previous row
    			if(Oset.contains(p-columnSize)){
    				explorer.add(p-columnSize);
    				Oset.remove(p-columnSize);
    			}
    			
    			
    			// check the element on the next row
    			if(Oset.contains(p+columnSize)){
    				explorer.add(p+columnSize);
    				Oset.remove(p+columnSize);
    			}
    			
    		}
    		
    		if(isCaptured){
    			// set the space 'O' to 'X'.
    			for(Integer p : space){
    				board[p/columnSize][p%columnSize] = 'X';
    			}
    		}
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.