ద్వీపం చుట్టుకొలత లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ బ్లూమ్బెర్గ్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ మైక్రోసాఫ్ట్
అర్రే

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు 2-D శ్రేణి రూపంలో గ్రిడ్ ఇవ్వబడుతుంది. గ్రిడ్ [i] [j] = 0 ఆ సమయంలో నీరు ఉందని సూచిస్తుంది మరియు గ్రిడ్ [i] [j] = 1 భూమిని సూచిస్తుంది. గ్రిడ్ కణాలు నిలువుగా / అడ్డంగా అనుసంధానించబడి ఉంటాయి కాని వికర్ణంగా కాదు. ఇచ్చిన ఇన్‌పుట్‌లో సరిగ్గా ఒక ద్వీపం (భూమి కణాల అనుసంధాన భాగం) ఉంది. మేము ఈ సమస్య యొక్క చుట్టుకొలతను నిర్ణయించాలి.

ఉదాహరణ

grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}}
16
grid = {{1}}
4

అప్రోచ్ (సింపుల్ కౌంటింగ్)

సమస్యను చూడటానికి సరళమైన మార్గం ఏమిటంటే, భూమి కణాలు మాత్రమే పరామితికి దోహదం చేస్తాయి. చుట్టుకొలతను లెక్కించడానికి ఇతర భూ కణాలతో పంచుకోని ఏ వైపునైనా ఉన్న భూమి కణాన్ని పరిగణనలోకి తీసుకోవచ్చు. ఎందుకంటే, భూమి కణం ఇతర భూ కణాలతో కొంత భాగాన్ని పంచుకుంటే, అది గ్రిడ్‌లోని ద్వీపం యొక్క బయటి సరిహద్దు కాదు.

ద్వీపం చుట్టుకొలత లీట్‌కోడ్ పరిష్కారం అమలు

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size();
    int perimeter = 0 , sides = 0;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m;  j++) {
            if(grid[i][j] == 1) {
                sides = 0;
                if(i == 0)
                    sides++;
                else
                    sides += (grid[i - 1][j] == 0);

                if(j == 0)
                    sides++;
                else
                    sides += (grid[i][j - 1] == 0);

                if(i == n - 1)
                    sides++;
                else
                    sides += (grid[i + 1][j] == 0);

                if(j == m - 1)
                    sides++;
                else
                    sides += (grid[i][j + 1] == 0);

                perimeter += sides;
            }
        }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

జావా ప్రోగ్రామ్

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length;
        int perimeter = 0 , sides = 0;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m;  j++) {
                if(grid[i][j] == 1) {
                    sides = 0;
                    if(i == 0)
                        sides++;
                    else if(grid[i - 1][j] == 0)
                        sides++;

                    if(j == 0)
                        sides++;
                    else if(grid[i][j - 1] == 0)
                        sides++;

                    if(i == n - 1)
                        sides++;
                    else if(grid[i + 1][j] == 0)
                        sides++;

                    if(j == m - 1)
                        sides++;
                    else if(grid[i][j + 1] == 0)
                        sides++;

                    perimeter += sides;
                }
            }
        return perimeter;
    }
}
16

ద్వీపం చుట్టుకొలత లీట్‌కోడ్ పరిష్కారం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N * M) ఇక్కడ గ్రిడ్‌లోని N = అడ్డు వరుసల సంఖ్య, గ్రిడ్‌లోని M = నిలువు వరుసల సంఖ్య.

అంతరిక్ష సంక్లిష్టత 

O (1) మేము వేరియబుల్స్ కోసం స్థిరమైన స్థలాన్ని ఉపయోగిస్తున్నప్పుడు.

అప్రోచ్ (ఎఫెక్టివ్ కౌంటింగ్)

పై విధానంలో, మేము దాని నాలుగు పొరుగువారిని తనిఖీ చేయడం ద్వారా చుట్టుకొలతకు దోహదపడే భూమి కణం వైపులా లెక్కిస్తున్నాము. ఇద్దరు పొరుగువారిని తనిఖీ చేయడానికి మేము దానిని మెరుగుపరచవచ్చు. గ్రిడ్‌లో ప్రయాణించడానికి మేము కుడి మరియు క్రిందికి వెళుతున్నప్పుడు, మేము ఎడమ మరియు పైకి కణాల తనిఖీని భూమి కణానికి మాత్రమే ఉంచగలం. ప్రతి ల్యాండ్ సెల్ ద్వీపం యొక్క చుట్టుకొలతకు '4' తోడ్పడుతుందని మనం అనుకోవచ్చు. ఒక భూమి కణం దాని వైపు (ల) ను ఇతర కణాలతో పంచుకుంటే, మేము దాని నుండి 2 ను తీసివేస్తాము (ఒకటి దాని భాగస్వామ్య వైపు మరియు మరొక సెల్ ఒక వైపు కూడా పంచుకుంటుంది). రెండు పరిష్కారాల సమయ సంక్లిష్టత ఒకటే కాని ఈ విధానంలో ఆపరేషన్ ఆధారంగా మేము కొంతవరకు మెరుగుపరుస్తాము.

ద్వీపం చుట్టుకొలత లీట్‌కోడ్ పరిష్కారం అమలు

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size() , perimeter = 0;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            if(grid[i][j] == 1) {
                perimeter += 4;

                if(i > 0 && grid[i - 1][j] == 1)
                    perimeter -= 2;

                if(j > 0 && grid[i][j - 1] == 1)
                    perimeter -= 2;
            }
        }
    }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

జావా ప్రోగ్రామ్

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length , perimeter = 0;
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(grid[i][j] == 1) {
                    perimeter += 4;

                    if(i > 0 && grid[i - 1][j] == 1)
                        perimeter -= 2;

                    if(j > 0 && grid[i][j - 1] == 1)
                        perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
}
16

ద్వీపం చుట్టుకొలత లీట్‌కోడ్ పరిష్కారం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N * M) ఇక్కడ గ్రిడ్‌లోని N = అడ్డు వరుసల సంఖ్య, గ్రిడ్‌లోని M = నిలువు వరుసల సంఖ్య.

అంతరిక్ష సంక్లిష్టత 

O (1) మేము వేరియబుల్స్ కోసం స్థిరమైన స్థలాన్ని ఉపయోగిస్తున్నప్పుడు.