Why Iterative method cost more time than Recursive method


  • 0
    L

    Hi, firstly I solved the problem with recursive method, the code is below:

     void changeIslands(vector<vector<char>>& grid, int row, int col) {
            if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size()) {
                return;
            }
            if (grid[row][col] != '1') {
                return;
            }
            grid[row][col] = '2';
            changeIslands(grid, row - 1, col);
            changeIslands(grid, row + 1, col);
            changeIslands(grid, row, col - 1);
            changeIslands(grid, row, col + 1);
        }
    

    It passed all the test cases. Then I asked myself can I changed it into the iterative method? So I started. The code is as follow:

     void changeIsland(vector<vector<char>>& grid, int row, int col) {
            queue<pair<int, int> > qu;
            qu.push(make_pair(row, col));
            while (!qu.empty()) {
                int topRow = qu.front().first;
                int topCol = qu.front().second;
                qu.pop();
                grid[topRow][topCol] = '0';
                if (topRow - 1 >= 0 && grid[topRow - 1][topCol] == '1') {
                    qu.push(make_pair(topRow - 1, topCol));
                }
                if (topRow + 1 < grid.size() && grid[topRow + 1][topCol] == '1') {
                    qu.push(make_pair(topRow + 1, topCol));
                }
                if (topCol - 1 >= 0 && grid[topRow][topCol - 1] == '1') {
                    qu.push(make_pair(topRow, topCol - 1));
                }
                if (topCol + 1 < grid[0].size() && grid[topRow][topCol + 1] == '1') {
                    qu.push(make_pair(topRow, topCol + 1));
                }
            }
        }
    

    But it gets TLE.
    So why did I get TLE, could you please help me?


Log in to reply
 

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