# Leetcode - Episode 16 - Pretty Efficient (3 x E)

More algorithms today. Pretty efficient ones at that. All above 90% ranked on the first submission. I'm beginning to find a lot of patterns that can be applied to the different problems. Most of the Easy binary tree questions are guilty of this.

I'm really happy that I finally solved Flipping an Image -- I had been in the thicket of a messy solution for a couple days but I was able to Pythonize it (read: refactor it)! I got hung up on solving it optimally before peaking at any resources.

### Flipping an Image

Problem: Flip a binary matrix and then invert it.

The trick is doing both steps at once. In other words, you don't want two for loops.

`class Solution(object):    def flipAndInvertImage(self, A):        """        :type A: List[List[int]]        :rtype: List[List[int]]        """        for x in range(len(A)):            A[x] = A[x][::-1]            for y in range(len(A[x])):                A[x][y] ^= 1                return A`

Outrageously straightforwards when it's reduced down to four lines.

Runtime complexity: `O(n)`.

Spacetime complexity: `O(n)`.

### Leaf-Similar Trees

Problem: Do these two trees have similar leaves -- read left-to-right.

We're going to the edge of these trees and comparing the concatenated values found therein, or, there-out-there.

```# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution(object):    def leafSimilar(self, root1, root2):        """        :type root1: TreeNode        :type root2: TreeNode        :rtype: bool        """        self.root1_store = []        self.root2_store = []        def bfs_recurse(node, store):            if not node.left and not node.right:                store.append(node.val)            else:                if node.left:                    bfs_recurse(node.left, store)                if node.right:                    bfs_recurse(node.right, store)        if root1:            bfs_recurse(root1, self.root1_store)        if root2:            bfs_recurse(root2, self.root2_store)        return self.root1_store == self.root2_store```

First try, pre-optimization: `Runtime: 32 ms, faster than 99.02% of Python online submissions.`.

Runtime complexity: `O(n)`.

Spacetime complexity: `O(n)`.

### Maximum Depth of N-ary Tree

Problem: What is the deepest level of this n-ary tree?

For this, we'll need a full tree traversal and some way of keeping track of the maximum depth so far. Lately, I've been reaching for instance variables in situations like this.

`"""# Definition for a Node.class Node(object):    def __init__(self, val, children):        self.val = val        self.children = children"""class Solution(object):    def maxDepth(self, root):        """        :type root: Node        :rtype: int        """        self.depth = 0        def dfs_recurse(node, depth):            depth += 1            for c in node.children:                dfs_recurse(c, depth)            self.depth = max(depth, self.depth)        if root:            dfs_recurse(root, 0)        return self.depth`

I'm going to check out some other solutions that don't use pseudo-globals.

Runtime complexity: `O(n)`.

Space complexity: `O(n)`.