Максимально увеличить остров

 827. Making A Large Island

Дана матрица размеров n x n состоящая из нулей и единиц grid. Можно сделать не более одной операции по изменению 0 в 1.

Вернуть размер наибольшего острова в grid после применения этой операции.

Остров - это связная группа из 1 по 4 направлениям: вверх/вниз/вправо/влево.

Пример 1:

Дано: grid = [[1,0],[0,1]]
Результат: 3
Пояснение: Мы можем поменять любой 0 на 1 и получим связный остров размером 3.

Пример 2:

Дано: grid = [[1,1],[1,0]]
Результат: 4
Пояснение: Мы поменять единственный 0 на 1 и получим связный остров размером 4.

Пример 3:

Дано: grid = [[1,1],[1,1]]
Результат: 4
Пояснение: Нулей нет, мы не можем провести операцию по смене 0 на 1, поэтому размер острова = 4.

Ограничения:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] в каждой ячейке содержит 0 или 1.

Идея решения 

Для каждой 1 в матрице, мы закращиваем существующие островаразными красками (2, 3 и т.д.). Мы также запоминаем размер острова закрашенного определенным цветом.

Затем мы анализируем все 0 в матрице и для них подсчитываем размер нового потенциального острова, если мы конвертируем этот 0 в 1. Заметим, что один и тот же остров может участвовать в образовании нового острова через конвертацию одной и той же ячейки 0 несколько раз. Это проиллюстрировано на картинке ниже:

 

Имплементация 

public int largestIsland(int[][] grid) {
        // создаем словарь: цвет-размер острова
        Map<Integer, Integer> map = new HashMap<>(); 
        // значение по умолчанию
        map.put(0, 0); 
        int n = grid.length; 
        int colorIndex = 2; //0 и 1 уже использованы в матрице, поэтому начинаем с 2
        //сканируем матрицу, и как только встречаем остров, считаем размер и закрашиваем
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int size = paint(grid, i, j, colorIndex); //считаем размер в глубину
                    map.put(colorIndex, size); //запоминаем размер выбранного цвета
                    colorIndex++; //меняем цвет
                }
            }
        }
    
        // первый найденный остров (его размер).
        // если в словаре нет цвета 2, то в матрице не было островов - вернем 0
        int res = map.getOrDefault(2, 0); 
        // смотрим, остались ли 0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    //используем set, чтобы рассматривать острова разного цвета
                    Set<Integer> set = new HashSet<>();
                    // для нулевой ячейки смотрим ее соседей
                    // если 0 на границе матрицы, мы добавляем 0 в set
                    set.add(i > 0 ? grid[i - 1][j] : 0);
                    set.add(i < n - 1 ? grid[i + 1][j] : 0);
                    set.add(j > 0 ? grid[i][j - 1] : 0);
                    set.add(j < n - 1 ? grid[i][j + 1] : 0);
                    
                    int newSize = 1; //допустим мы конвертирует текущий 0 в 1 - получим остров размера 1
                    // эта конвертированная ячейка объединит острова-соседей, 
                    // если они существуют (то есть их размер > 0)
                    for (int color : set) newSize += map.get(color);
                    // выбираем максимальный результат
                    res = Math.max(res, newSize);
                }
            }
        }
        return res; // возвращаем максимальный результат
    }
    
    //Вспомогательный метод для раскраски острова в выбранный цвет 
    //использует dfs
    private int paint(int[][] grid, int i, int j, int color) {
        //проверяем, можно ли идти в глубину
        //для этого мы должны быть внутри матрицы
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length 
        //и рассматриваемая ячейка должна быть островом, и мы рассматриваем ее в первый раз
            || grid[i][j] != 1) return 0;
        //красим ячейку острова в выбранный цвет
        grid[i][j] = color;
        // рекурсивно считаем размер острова поиском в глубину по 4-направлениям
        // +1 к размеру для текущей ячейки
        return 1 + paint(grid, i + 1, j, color) + paint(grid, i - 1, j, color) + paint(grid, i, j + 1, color) + paint(grid, i, j - 1, color);
    }

Анализ имплементации

Для того, чтобы раскрасить матрицу в острова разных цветок, нам нудно просканировать всю матрицу, то есть провести O(n*m) операций.

Затем мы опять сканируем матрицу на наличие нулевых элементов - это опять  O(n*m) операций.