Why does this not work?


  • 0
    K

    public class Solution {
    public IList<int> NumIslands2(int m, int n, int[,] positions) {
    var result = new List<int>();
    var matrix = new int[m, n];

    	for (int i = 0; i < m; i++)
    	{
    		for (int j = 0; j < n; j++)
    		{
    			matrix[i, j] = 0;
    		}
    	}
    	
    	int k = positions.GetLength(0);
    	for (int i = 0; i < k; i++)
    	{
    		int x = positions[i, 0];
    		int y = positions[i, 1];
    		
    		if (matrix[x, y] == 1)
    		{
    			continue;
    		}
    		
    		matrix[x, y] = 1;
    		
    		if (result.Count == 0)
    		{
    			result.Add(1);
    		}
    		else
    		{
    			int last = result[result.Count - 1];
    			
    			int connected = 0;
    			
    			if (x > 0 && matrix[x - 1, y] == 1) connected++;
    			if (x < m - 1 && matrix[x + 1, y] == 1) connected++;
    			if (y < n - 1 && matrix[x, y + 1] == 1) connected++;
    			if (y > 0 && matrix[x, y - 1] == 1) connected++;
    			
    			result.Add(last + 1 - connected > 0 ? last + 1 - connected : 1);
    		}
    	}
    	
    	return result;
    }
    

    }


  • 0
    K

    The code can pass some test cases but it can not pass the case with large input, the first half of the results are correct, the left is wrong.

    My idea is simple, when processing a new position just check can it merge with other islands, the time complexity is O(K), so I know there is something wrong, could you tell me in which case this won't work?


  • 0
    Q

    I bet you know why now, but let me to narrate to teach myself.
    When you connect two points, it might be that there was already another path between the two points. Thus, in your algorithm you decrease the island count by 1, but actually the number of islands is not changed.


Log in to reply
 

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