instance variable difference (Python)

Question

I have 2 questions about the solutions below.

Below is my answer (Solution 1) for this question of leetcode: https://leetcode.com/problems/distribute-coins-in-binary-tree/

# Solution 1:
class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        self.ans = 0

        def dfs(node):
            if not node:
                return 0

            L, R = dfs(node.left), dfs(node.right)
            self.ans += abs(L) + abs(R)
            return node.val + L + R - 1

        dfs(root)
        return self.ans

Quesion1 I was wondering why below does not work. What is the difference between the variable ans of Solution 1 and Solution 2?

# Solution 2:
class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        ans = 0  
        self.dfs(root, ans)
        return ans
    
    def dfs(self, node, ans):
        if not node:
            return 0

        L, R = self.dfs(node.left, ans), self.dfs(node.right, ans)
        ans += abs(L) + abs(R)

        return node.val + L + R - 1

Because changes on grid variable below (Solution 3) is accumulated and affects all each recursions, I thought it would also be the case for Solution 2.

Question2 What is the difference between ans of Solution 2 and grid of Solution 3 which makes the differences due to recursion not accumulate? (Below is solution for https://leetcode.com/problems/number-of-islands/)

# Solution 3:
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(i, j, grid)
                    count += 1

        return count

    def dfs(self, i: int, j: int, grid: List[List[str]]):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return

        grid[i][j] = '#'

        self.dfs(i + 1, j, grid)
        self.dfs(i - 1, j, grid)
        self.dfs(i, j - 1, grid)
        self.dfs(i, j + 1, grid)

Lior Cohen · Accepted Answer · 2021-01-09 22:36:17Z

1

in solution #2 you pass integer ans to the dfs function, the function may change it but this change is not seen by the caller because integer is immutable so the modified ans is a new object that has nothing to do with the original ans=0.

On the other hand, Solution #3, pass List which is mutable object. Changing (mutating) this object grid[i][j] = '#' is seen to any scope that hold (reference to) this object.

This is the same as Solution #1 which change self.ans which is again the very same attribute of the very same object in all the recursion scopes.

answered Jan 9, 2021 at 22:36

Lior Cohen

5,7202 gold badges18 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

instance variable difference (Python)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related