# DVD Class
class DVD:
    def __init__(self, name, releaseYear, director):
        self.name        = name
        self.releaseYear = releaseYear
        self. director   = director
        
    def get_data(self):
        print(f'{self.name}, directed by {self.director}, released in {self.releaseYear}')

# creating an Array(dynamic) of size 15 to hold DVD's.
dvdCollection = [None] * 15

# Firstly, we need to actually create a DVD object for The Avengers.
avengersDVD = DVD("The Avengers",2012,"Joss Whedon")

# Next, we'll put it into the 8th place of the Array. Remember, because we
# started numbering from 0, the index we want is 7.
dvdCollection[7] = avengersDVD

# Let's put a few more DVD's in
incrediblesDVD = DVD("The Incredibles",2004,"Brad Bird")
findingDoryDVD = DVD("Finding Dory",2016,"Andrew Stanton")
lionKingDVD = DVD("The Lion King",2019,"Jon Favreau")

# Put "The Incredibles" into the 4th place: index 3.
dvdCollection[3] = incrediblesDVD;

# Put "Finding Dory" into the 10th place: index 9.
dvdCollection[9] = findingDoryDVD;

# Put "The Lion King" into the 3rd place: index 2.
dvdCollection[2] = lionKingDVD;

starWarsDVD = DVD("Star Wars",1977,"George Lucas")
dvdCollection[3] = starWarsDVD;

# Reading Items from an Array
# Print out what's in indexes 7, 10, and 3.
dvdCollection[7].get_data()
print(dvdCollection[10])
dvdCollection[3].get_data()

# Writing Items into an Array with a Loop
# Go through each of the Array indexes, from 0 to 9.
squareNumbers = [None] * 10
# squareNumbers = [] ---> python style: can grows on demand
for i in range(10):
    squareNumbers[i] = (i+1) * (i+1)
    # squareNumbers.append((i+1) * (i+1)) ---> python style

# Reading Items from an Array with a Loop
for i in range(10):
    print(squareNumbers[i])

capacity = len(squareNumbers)
print(f"The Array has a capacity of {capacity}")

# Array Length
# Create a new array with a capacity of 6.
array = [None] * 6;

# Current length is 0, because it has 0 elements.
length = 0;

# Add 3 items into it.
for i in range(3): 
    array[i] = i * i
    # Each time we add an element, the length goes up by one.
    length+=1

print(f"The Array has a capacity of {len(array)}")
print(f"The Array has a length of {length}")

class Solution:
    def findMaxConsecutiveOnes(self, nums:list) -> int:
        count = 0
        ans = 0
        for num in nums:
            if num == 1:
                count+=1
                ans = max(ans, count)
            else:
                count = 0
        return ans

if __name__ == '__main__':
    nums = [1,1,0,1,1,1]
    obj = Solution()
    print(obj.findMaxConsecutiveOnes(nums))

class Solution:
    def findNumbers(self, nums: list) -> int:
        count = 0
        for num in nums:
            if len(str(num))%2 == 0:
                count += 1
        return count

if __name__ == '__main__':
    nums = [12,345,2,6,7896]
    obj = Solution()
    print(obj.findNumbers(nums))

class Solution:
    def sortedSquares(self, nums: list) -> list:
        for index in range(len(nums)):
            nums[index] = nums[index] ** 2
        nums.sort()
        return nums

if __name__ == '__main__':
    nums = [-7,-3,2,3,11]
    obj = Solution()
    print(obj.sortedSquares(nums))

# Declare an integer array of 6 elements
intArray = [None] * 6
length = 0

for index in range(3):
    intArray[index] = index
    length+=1

# visualise what's happening
for index in range(len(intArray)):
    print(f'Index {index} contains {intArray[index]}')

# Insert a new element at the end of the Array. Again,
# it's important to ensure that there is enough space
# in the array for inserting a new element.
intArray[length] = 10
length+=1

# print the array
for index in range(len(intArray)):
    print(f'Index {index} contains {intArray[index]}')

# First, we will have to create space for a new element.
# We do that by shifting each element one index to the right.
# This will firstly move the element at index 3, then 2, then 1, then finally 0.
# We need to go backwards to avoid overwriting any elements.
for index in range(3,-1,-1):
     intArray[index + 1] = intArray[index]
        
# Now that we have created space for the new element,
# we can insert it at the beginning.
intArray[0] = 20

# print the array
for index in range(len(intArray)):
    print(f'Index {index} contains {intArray[index]}')

# Say we want to insert the element at index 2.
# First, we will have to create space for the new element.
for index in range(4,1,-1):
     intArray[index + 1] = intArray[index]

# Now that we have created space for the new element,
# we can insert it at the required index.
intArray[2] = 30

# print the array
for index in range(len(intArray)):
    print(f'Index {index} contains {intArray[index]}')

class Solution:
    def duplicateZeros(self, arr: list) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        index = 0
        while index < len(arr):
            if arr[index] == 0:
                arr.insert(index+1,0)
                arr.pop()
                index += 2
            else:
                index += 1

if __name__ == '__main__':
    arr = [1,0,2,3,0,4,5,0]
    obj = Solution()
    obj.duplicateZeros(arr)
    print(arr)

class Solution:
    def merge(self, nums1: list, m: int, nums2: list, n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2[:]
        nums1.sort()

if __name__ == '__main__':
    nums1 = [1,2,3,0,0,0]
    m = 3
    nums2 = [2,5,6]
    n = 3
    obj = Solution()
    obj.merge(nums1,m,nums2,n)
    print(nums1)

# Declare an integer array of 10 elements.
intArray = [None] * 10

# The array currently contains 0 elements
length = 0

# Add elements at the first 6 indexes of the Array.
for index in range(6):
    intArray[length] = index
    length+=1

# Deletion from the end is as simple as reducing the length
# of the array by 1.
length-=1

# print
for index in range(len(intArray)):
    print(f'Index {index} contains {intArray[index]}')

# before the deletion
for index in range(length+1):
    print(f'Index {index} contains {intArray[index]}')

# after the deletion
for index in range(length):
    print(f'Index {index} contains {intArray[index]}')

# to the left.
for i in range(1,length):
    # shift each element one position to the left
    intArray[i - 1] = intArray[i]

# Note that it's important to reduce the length of the array by 1.
# Otherwise, we'll lose consistency of the size. This length
# variable is the only thing controlling where new elements might
# get added.
length-=1

# print
for index in range(length):
    print(f'Index {index} contains {intArray[index]}')

# // Say we want to delete the element at index 1
for i in range(2,length):
    # Shift each element one position to the left
    intArray[i - 1] = intArray[i]

# Again, the length needs to be consistent with the current
# state of the array.
length-=1

# print
for index in range(length):
    print(f'Index {index} contains {intArray[index]}')

class Solution:
    def removeElement(self, nums: list, val: int) -> int:
        while val in nums:
            nums.remove(val)
        return len(nums)
# class Solution:
#     def removeElement(self, nums: list, val: int) -> int:
#         k = 0
#         index = 0
#         while index < len(nums):
#             if nums[index] == val:
#                 nums.append('_')
#                 nums.remove(val)
#                 index -= 1
#                 k += 1
#             else:
#                 index += 1              
#         return len(nums)-k

if __name__ == '__main__':
    nums = [0,1,2,2,3,0,4,2]
    val = 2
    obj = Solution()
    print(obj.removeElement(nums,val),", nums =",nums)

class Solution:
    def removeDuplicates(self, nums: list) -> int:
        nums[:] = set(nums)
        nums.sort()
        return len(nums)

if __name__ == '__main__':
    nums = [-1,0,0,0,0,3,3]
    obj = Solution()
    print(obj.removeDuplicates(nums),", nums =",nums)

def linearSearch(array, length, element):
    # Check for edge cases. Is the array null or empty?
    # If it is, then we return false because the element we're
    # searching for couldn't possibly be in it.
    if len(array) == 0 or length == 0:
        return False
    # Carry out the linear search by checking each element,
    # starting from the first one.
    for index in range(length):
        # We found the element at index i.
        # So we return true to say it exists.
        if array[i] == element:
            return True
    # We didn't find the element in the array.
    return False

# Declare a new array of 6 elements
array = [None] * 10
# Variable to keep track of the length of the array
length = 0
# Iterate through the 6 indexes of the Array
for i in range(6):
    # Add a new element and increment the length as well
    length+=1
    array[length] = i

# Print out the results of searching for 4 and 30.
print(f'Does the array contain the element 4? - {linearSearch(array,length,4)}')
print(f'Does the array contain the element 30? - {linearSearch(array,length,30)}')

class Solution:
    def checkIfExist(self, arr: list) -> bool:
        for a in arr:
            if a*2 in arr and a != 0:
                return True
            elif arr.count(0) == 2:
                return True 
        return False

if __name__ == '__main__':
    arr = [10,2,5,3]
    obj = Solution()
    print(obj.checkIfExist(arr))

def squareEven(array, length):
    
    # Check for edge cases.
    if (array == None):
    return None

    # Create a resultant Array which would hold the result.
    result = [None] * length

    # Iterate through the original Array.
    for i in range(len(array)):
        # Get the element from slot i of the input Array.
        element = array[i];
        # If the index is an even number, then we need to square element.
        if i%2 == 0:
            element *= element
        # Write element into the result Array.
        result[i] = element;
    # Return the result Array.
    return result

def sqsquareEven(array, length):
    # Check for edge cases.
    if array is None:
        return None
    
    # Iterate through the original Array.
    for i in range(len(array)):
        # If the index is an even number, then we need to square the element
        # and replace the original value in the Array.
        if i%2==0:
            array[i] = array[i] * array[i]
        # Notice how we don't need to do *anything* for the odd indexes? :-)
    
    # We just return the original array. Some problems on leetcode require you
    # to return it, and other's dont.
    return array

# In place solution
class Solution:
    def replaceElements(self, arr: list) -> list:
        max_right = 0
        for i in range(len(arr)-1):
            max_right = max(arr[i+1:])
            arr[i] = max_right
        arr[-1] = -1
        
        return arr

if __name__ == '__main__':
    arr = [17,18,5,4,6,1]
    obj = Solution()
    print(obj.replaceElements(arr))

# NOT in place
class Solution:
    def replaceElements(self, arr: list) -> list:
        result=[]
        for i in range(len(arr)-1):
            result.append(max(arr[i+1:]))
        result.append(-1)
        return result

if __name__ == '__main__':
    arr = [17,18,5,4,6,1]
    obj = Solution()
    print(obj.replaceElements(arr))

# In place solution
class Solution:
    def removeDuplicates(self, nums: list) -> int:
        nums[:] = set(nums)
        nums.sort()
        return len(nums)

if __name__ == '__main__':
    nums = [0,0,1,1,1,2,2,3,3,4]
    obj = Solution()
    print(obj.removeDuplicates(nums))
    print(nums)

class Solution:
    def moveZeroes(self, nums: list) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for num in nums:
            if num == 0:
                nums.remove(num)
                nums.append(num)
        return nums

if __name__ == '__main__':
    nums = [0,1,0,3,12]
    obj = Solution()
    print(obj.moveZeroes(nums))

# NOT in place
class Solution:
    def sortArrayByParity(self, nums: list) -> list:
        even = []
        odd=[]
        for num in nums:
            if num%2 == 0:
                even.append(num)
            else:
                odd.append(num)
        even.extend(odd)
        return even
    
# In place solution
# class Solution:
#     def sortArrayByParity(self, nums: List[int]) -> List[int]:
#         j = 0
#         for i in range(0, len(nums)):
#             if nums[i] % 2 == 0:
#                 nums[j], nums[i] = nums[i], nums[j]
#                 j += 1
#         return nums

if __name__ == '__main__':
    nums = [3,1,2,4]
    obj = Solution()
    print(obj.sortArrayByParity(nums))

class Solution:
    def removeElement(self, nums: list, val: int) -> int:
        while val in nums:
            nums.remove(val)
        return len(nums)

if __name__ == '__main__':
    nums = [3,2,2,3]
    val = 3
    obj = Solution()
    print(obj.removeElement(nums,val))
    print(nums)

# Maximum SubAyyar using Two-Pointer
A = [1,9,-1,-2,7,3,-1,2]
k = 4
mSum = 0
for i in range(len(A)-k+1):
    wSum = 0
    for j in range(i, i+k):
        wSum += A[j]
    mSum = max(mSum, wSum)
print(mSum)

# Maximum SubAyyar using Sliding Window
A = [1,9,-1,-2,7,3,-1,2]
k = 4
mSum = 0
wSum = 0
for i in range(k):
    wSum += A[i]
for end in range(k, len(A)):
    wSum += A[end] - A[end - k]
    mSum = max(mSum, wSum)
print(mSum)

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = heights[:]
        expected.sort()
        count = 0
        for i in range(len(heights)):
            if heights[i] != expected[i]:
                count+=1   
        return count

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums = list(set(nums))
        if len(nums) < 3:
            return max(nums)
        return sorted(nums)[-3]

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        nums_set = set(nums)
        result = []
        for i in range(1,len(nums)+1):
            if i not in nums_set:
                result.append(i)
        return result