# APPLE
"""
    SOLVED -- LEETCODE#26
    Given a sorted list of size n, with m unique elements (thus m < n), 
    modify the list such that the first m unique elements in the list will be sorted, 
    ignoring the rest of the list. Your solution should have a space complexity of O(1). 
    Instead of returning the list (since you are just modifying the original list), 
    you should return what m is.
"""


def remove_dups(nums):
    # Time: O(n)    Space: O(1)
    n = len(nums)
    if n == 1:
        return 1
    p = 1

    for i in range(1, n):
        if nums[i] > nums[p-1]:
            nums[i], nums[p] = nums[p], nums[i]
            p += 1

    # nums = nums[:p] does not work
    del nums[p:n]
    return p


nums = [1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 6, 7, 9]
print(remove_dups(nums))
# 8
print(nums)
# [1, 2, 3, 4, 5, 6, 7, 9]

nums = [1, 1, 1, 1, 1, 1]
print(remove_dups(nums))
print(nums)
# 1
# [1]
