# Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

class Solution:
    def toLowerCase(self, str: str) -> str:
        lowerCase = str.lower()
        return lowerCase

# Write a function that reverses a string. The input string is given as an array of characters char[].

# Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

# Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

class Solution:
    def reverseWords(self, s: str) -> str:
        reversedWords=[]
        listOfWords= s.split()
        for word in listOfWords:
            reversedWords.append(word[::-1])
        
        
        return " ".join(reversedWords)

# Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

# Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        single_number = []
        for num in nums:
            if num not in single_number:
                single_number.append(num)
            else:
                single_number.remove(num)
        return single_number[0]

# Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        return (nums[-1]-1) * (nums[-2]-1)

# Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

# You may return any answer array that satisfies this condition.

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        even=[]
        odd=[]
        for num in A:
            if (num%2)==0:
                even.append(num)
            else:
                odd.append(num)
        for num in odd:
            even.append(num)
        return even



# The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1 :
            return n 
        return self.fib(n-1) + self.fib(n-2)


# You are given two strings s and t.

# String t is generated by random shuffling string s and then add one more letter at a random position.

# Return the letter that was added to t.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        first_string = [char for char in s]
        second_string= [char for char in t]
  
        for character in second_string:
            if character not in first_string:
                return character

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.
Return the reformatted string or return an empty string if it is impossible to reformat the string.

class Solution:
    def reformat(self, s: str) -> str:
        nums=[]
        letters=[]
        emptyString=""
        for ele in s:
            if ele.isdigit():
                nums.append(ele)
            else:
                letters.append(ele)
        if len(nums)-len(letters) > 1:
            return emptyString
        result = ''.join(a + c for a, c in zip(nums, letters))
        return result

# Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.


class Solution:
    def firstUniqChar(self, s: str) -> int:
        for i in range(len(s)):
            character = s[i]
            if s.count(character)==1:
                return i

        return -1

# Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        tail = dummy 
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next 
            else: 
                tail.next = l2
                l2 = l2.next
            
            tail = tail.next 
        
        if l1:
            tail.next = l1
        elif l2:
            tail.next = l2
        return dummy.next

# Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

while left_index <= right_index:
            middle_index = (left_index + right_index) // 2 
            if target < nums[middle_index]:
                right_index = middle_index - 1 
                
            elif target > nums[middle_index]:
                left_index = middle_index + 1
            else:
                return middle_index
                
        return -1

# Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

# Find all the elements that appear twice in this array.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        duplicates = []
        for i in nums:
            i = abs(i)
            print(i)
            if nums[i-1] < 0:
                duplicates.append(i)
            else:
                nums[i-1] = -nums[i-1]
        return duplicates

# A binary tree is univalued if every node in the tree has the same value.

# Return true if and only if the given tree is univalued.

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        vals = []
        def dfs(node):
            if node:
                vals.append(node.val)
                dfs(node.left)
                dfs(node.right)

        dfs(root)
        return len(set(vals)) == 1

# Given the string, check if it is a palindrome.

def checkPalindrome(inputString):
    #assign the reverse of the input string to a variable and check if it matches the input     string
    #if so return true
    if inputString[::-1] == inputString:
        return True
    else:
        return False

# Given an array of integers, find the pair of adjacent elements that has the largest product and return that product.

def adjacentElementsProduct(inputArray):
    #create a array to store the products of adjacent elemtents 
    #multiply the adjacent elements and store in that list 
    #return the largest element from that array 
    products = []
    for idx, ele in enumerate(inputArray):
        #check index, if zero multiply the number of that index by the the number in the following index and append to array
        if idx == 0:
            products.append(inputArray[idx+1]*inputArray[idx])
        #check if its the last index, if so multiply the number in that index by the number in the previous index and append to array 
        elif idx == len(inputArray)-1:
            products.append(inputArray[idx-1]*inputArray[idx])
        else:
            #multiply the index by the numbers i adjacent indexes and append to array
            products.append(inputArray[idx-1]*inputArray[idx]) and products.append(inputArray[idx+1]*inputArray[idx])
    return max(products)

# Below we will define an n-interesting polygon. Your task is to find the area of a polygon for a given n.
def shapeArea(n):
    #if n is 1 return 1 
    #else if n > 1 return (n*2)*(n-1)+1 
    return (n*2)*(n-1)+1
# Ratiorg got statues of different sizes as a present from CodeMaster for his birthday, each statue having an non-negative integer size. Since he likes to make things perfect, he wants to arrange them from smallest to largest so that each statue will be bigger than the previous one exactly by 1. He may need some additional statues to be able to accomplish that. Help him figure out the minimum number of additional statues needed.
def makeArrayConsecutive2(statues):
    return (max(statues) - min(statues)) - len(statues) + 1
