from typing import List

"""
For O(1) space complexity use math operation or XOR.
a^a = 0
a^0 = a
a^b^c = a^a^b = 0^b = b
"""
class Solution(object):
    def singleNumber(self, nums: List[int]) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        idx = {}
        for i in range(len(nums)):
            if nums[i] not in idx:
                idx[nums[i]] = 1
            else:
                idx[nums[i]] += 1
        
        for k in idx.keys():
            if idx[k] == 1:
                return k

print(Solution().singleNumber([4,1,2,1,2]))

"""
Explanation: String Problems
https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3283/
Q.1. Given a non-empty array of integers, every element appears twice except for one. Find that single one.
End of explanation
"""


class Solution(object):
    def ifHappy(self, n: int) -> bool:
        """
        :type n: int
        :rtype: bool
        """
        l = 0
        while (n != 1):
            add = 0
            for i in str(n):
                add += int(i) ** 2
            n = add
            l += 1
            if l > 100:
                return False
        return True

print(Solution().ifHappy(19))

"""
Explanation: Q.2. Write an algorithm to determine if a number n is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Return True if n is a happy number, and False if not.
End of explanation
"""


class Solution(object):
    def maxSubArray(self, nums: List[int]) -> int:
        """
        :type nums: List[int]
        :rtype int
        """
        # Special case is when all values in num are negative.
        if max(nums) < 0:
            return max(nums)
        
        max_sum = 0; curr = 0
        for i in range(len(nums)):            
            if curr + nums[i] > 0:
                curr = curr + nums[i]
            else:
                curr = 0 # Reset the sum.
            
            if curr > max_sum:
                max_sum = curr
        
        return max_sum
                

print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

"""
Explanation: Q.3. Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
End of explanation
"""


class Solution(object):
    def moveZeroes(self, nums: List[int]) -> None:
        """
        :type nums: List[int]
        :rtype None
        Perform inplace ordering.
        
        Method: Apply a form of insert sort that moves each non-negative value
                to its right place in the list.
        """
        for i in range(len(nums)):
            if nums[i] != 0:
                j = i
                while j > 0 and nums[j - 1] == 0:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
                    j -= 1

nums = [0,1,0,3,12]
Solution().moveZeroes(nums)
print(nums)

"""
Explanation: Q.4. Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
End of explanation
"""


class Solution(object):
    def maxProfit(self, prices: List[int]) -> int:
        """
        :type prices: List[int]
        :rtype: int
        
        Maximum Profit is the cumulation of all positive differences.
        """
        profit = 0
        for i in range(1, len(prices)):
            diff = prices[i] - prices[i-1]
            if diff > 0:
                profit += diff
        
        return profit

print(Solution().maxProfit([7,6,4,3,1]))

"""
Explanation: Q.5. Say you have an array prices for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
End of explanation
"""


class Solution(object):
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        
        Method: Build a dictionary of words creating a bag of characters representation.
                Generate a has for that representation and add words with a similar hash.
        """
        words = {}
        
        # Build a dictionary of words.
        for word in strs:
            boc_vec = [0 for i in range(26)]
            for char in word:
                boc_vec[ord(char) - 97] += 1

            # Check if the representation if present in the dict.
            hval = hash(tuple(boc_vec))
            if hval not in words:
                words[hval] = [word]
            else:
                words[hval].append(word)
        
        # Once, the dictionary is built, generate list.
        fin = []
        for key in words.keys():
            fin.append(words[key])
        
        return fin
        

print(Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

"""
Explanation: Q.6. Given an array of strings, group anagrams together.
End of explanation
"""


class Solution(object):
    def countElements(self, arr: List[int]) -> int:
        """
        :type arr: List[int]
        :rtype: int
        
        Method: Build a dictionary of all numbers in the list and then separately
                verify if (n+1) number exists in the dictionary for every n.
        """
        nums = {}
        for n in arr:
            if n not in nums:
                nums[n] = 1
        
        cnt = 0
        for n in arr:
            if n+1 in nums:
                cnt += 1
        
        return cnt

print(Solution().countElements([1,3,2,3,5,0]))

        if root.left is None and root.right is None:
            return 0
        
        def get_longest_path(root):
            if root.left is None and root.right is None:
                return 0
            elif root.left is None:
                return 1 + get_longest_path(root.right)
            elif root.right is None:
                return 1 + get_longest_path(root.left)
            else:
                return max(1 + get_longest_path(root.left), 1 + get_longest_path(root.right))
        
        return get_longest_path(root.left) + get_longest_path(root.right)


"""
Explanation: Q.7. Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there're duplicates in arr, count them seperately.
End of explanation
"""


