# Leetcode - Episode 2 - Three More Easys

After warming up (literally, I cycled home in frosty weather) I tackled some more Leetcode problems today.

### N-Repeated Element in Size 2N Array

Problem: Given an list `A` of size `2N`, there are `N+1` unique elements -- which one is repeated `N` times?

For this solution I used the high performance Counter that I discovered in my previous blog post.

```from collections import Counter
class Solution:    def repeatedNTimes(self, A):        """        :type A: List[int]        :rtype: int        """        counter = set()        half = len(A) / 2
for i in A:            counter[i] += 1            if counter[i] == half:
return i```

This solution has a runtime complexity of `O(n)` and a space complexity of `O(n)`. I'm not sure whether this can be improved upon. All elements of the list need to be checked because it is unsorted -- we can't know where our `N` element will be.

Leetcode's tests for this problem only have unique elements and so a Set is technically faster but I prefer my solution as it's more 'correct' per the problem statement.

### Univalued Binary Tree

Problem: Are all the values of this binary tree the same?

It's a tree-traversal problem so it's either going to be Depth-First Search or Breadth-First Search. I chose DFS.

```# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def isUnivalTree(self, root):        """        :type root: TreeNode        :rtype: bool        """        value = root.val                def recursive_search(node):            if node == None:                return True            elif node.val != value:                return False            else:                return recursive_search(node.left) and recursive_search(node.right)            return True                return recursive_search(root)```

Whatever the solution to this problem, the runtime complexity will be `O(n)` as every node must be touched to satisfy the problem condition. We used DFS so the stack will only hold one singular winding tree-root in memory at once. Hence the space complexity is `O(d)` where `d` is the depth of the tree.

### Unique Morse Code Words

Problem: Given a list of lowercase words, how many unique morse code sequences are there?

They're looking for unique occurrences so a standard optimization is likely to be a Set.

```class Solution:    def uniqueMorseRepresentations(self, words):        """        :type words: List[str]        :rtype: int        """        morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
unique_words = set()                for word in words:            as_morse = []            for c in word:                as_morse.append(morse[ord(c) - 97])            unique_words.add(''.join(as_morse))
return len(unique_words)```

My solution has a runtime complexity of `O(n)` with a space complexity of `O(n)`. Similar to Leetcode problem 709, it may be faster to use a Dictionary that maps letters to morse as opposed to performing a calculation for each letter but this may depend on language implementation.

After looking through other peoples' Python solutions, I noted that for the future I need to focus on using more Python language features. For instance, I saw lines like:

`code = ''.join([morseTable[ord(letter) - 97] for letter in list(word)])`.

Lines like this are more terse while remaining understandable.