Minimum Deletions to Make Array Beautiful LeetCode solution in Python

1
class Solution:
2
    def minDeletion(self, nums: List[int]) -> int:
3
        # Greedy !
4
        # we first only consider requirement 2: nums[i] != nums[i + 1] for all i % 2 == 0
5
        # at the begining, we consider the num on the even index
6
        # when we delete a num, we need consider the num on the odd index
7
        # then repeat this process
8
        # at the end we check the requirement 1: nums.length is even or not
9

10
        n = len(nums)
11
        count = 0
12
        # flag is true then check the even index
13
        # flag is false then check the odd index
14
        flag = True
15

16
        for i in range(n):
17
            # check the even index
18
            if flag:
19
                if i % 2 == 0 and i != n - 1 and nums[i] == nums[i + 1]:
20
                    count += 1
21
                    flag = False
22
            # check the odd index
23
            elif not flag:
24
                if i % 2 == 1 and i != n - 1 and nums[i] == nums[i + 1]:
25
                    count += 1
26
                    flag = True
27

28
        curLength = n - count
29

30
        return count if curLength % 2 == 0 else count + 1