Remove the shortest non-descending subsequence from original sequence to make all its elements unique

SequenceRemoval.py

import unittest

from collections import deque
from typing import List


def remove_subsequence_length(nums: List[int]) -> int:
    """
        Remove the shortest non-descending subsequence in nums to make elements of nums unique.
        :param nums:
            The original sequence to work on.
        :return:
            Length of the shortest incrementing subsequence to be removed.
            0 if the shortest subsequence is empty or isn't non-descending.
        """
    unique_count, unique_idx = dict(), dict()
    for idx, num in enumerate(nums):
        if num not in unique_count:
            unique_count[num] = 0
            unique_idx[num] = []
        unique_count[num] += 1
        unique_idx[num].append(idx)

    if sum(map(lambda n: n[1], unique_count.items())) == len(unique_count):
        return 0

    res, prev_idx = 0, deque()
    # loop variables
    lst_idx, lst_unique_idx = 0, sorted(unique_idx.items())
    # status of each num in non-descending order
    unique_remove_type = {}
    while lst_idx < len(unique_count):
        num, idx_lst = lst_unique_idx[lst_idx]
        # exclude already unique num
        if unique_count[num] < 2:
            del unique_count[num]
            del unique_idx[num]
            del lst_unique_idx[lst_idx]
            # no increment lst_idx as list is updated
        else:
            # loop through possible steps
            if lst_idx not in unique_remove_type:
                unique_remove_type[lst_idx] = [0, False]

            while unique_remove_type[lst_idx][0] < 3:
                if unique_remove_type[lst_idx][0] == 0:
                    head = idx_lst[0]
                    idx_append = idx_lst[-2]
                elif unique_remove_type[lst_idx][0] == 1:
                    if unique_remove_type[lst_idx][1]:
                        prev_idx.pop()
                    head = idx_lst[1]
                    idx_append = idx_lst[-2]
                else:
                    # unable to make num unique, early return
                    return 0

                unique_remove_type[lst_idx][0] += 1

                if not prev_idx or head >= prev_idx[-1]:
                    # continue on next level
                    if not unique_remove_type[lst_idx][1]:
                        res += len(idx_lst) - 1
                    prev_idx.append(idx_append)
                    unique_remove_type[lst_idx][1] = True
                    lst_idx += 1
                    break  # inner loop
                elif unique_remove_type[lst_idx][0] == 2:
                    # backtrack to previous level
                    unique_remove_type[lst_idx] = [0, False]
                    res -= len(idx_lst) - 1
                    lst_idx -= 1
                    break
                # else continue loop

    return res


def remove_subsequence(nums: List[int]) -> List[int]:
    """
    Remove the shortest non-descending subsequence in nums to make elements of nums unique.
    :param nums:
        The original sequence to work on.
    :return:
        The shortest incrementing subsequence to be removed.
        [-1] if the shortest subsequence is empty or isn't non-descending.
    """
    unique_count, unique_idx = dict(), dict()
    for idx, num in enumerate(nums):
        if num not in unique_count:
            unique_count[num] = 0
            unique_idx[num] = []
        unique_count[num] += 1
        unique_idx[num].append(idx)

    if sum(map(lambda n: n[1], unique_count.items())) == len(unique_count):
        return [-1]

    res = []
    # loop variables, sorted dictionary as list
    lst_idx, lst_unique_idx = 0, sorted(unique_idx.items())
    # status of each lst_idx in non-descending order, [status: int, is_res_appended: bool]
    unique_remove_type = {}
    while lst_idx < len(unique_count):
        num, idx_lst = lst_unique_idx[lst_idx]
        # exclude already unique num
        if unique_count[num] < 2:
            del unique_count[num]
            del unique_idx[num]
            del lst_unique_idx[lst_idx]
            # no increment lst_idx as list is updated
        else:
            if lst_idx not in unique_remove_type:
                unique_remove_type[lst_idx] = [0, False]
            
            # loop through possible steps
            while unique_remove_type[lst_idx][0] < 3:
                if unique_remove_type[lst_idx][0] == 0:
                    remove = idx_lst[:-1]
                    head = idx_lst[0]
                elif unique_remove_type[lst_idx][0] == 1:
                    if unique_remove_type[lst_idx][1]:
                        # remove idx_lst[0], append idx_lst[1]
                        res.remove(idx_lst[0])
                        remove = [idx_lst[-1]]
                    else:
                        # nothing has been appended
                        remove = idx_lst[1:]
                    head = idx_lst[1]
                else:
                    # unable to make num unique, early return
                    return [-1]

                unique_remove_type[lst_idx][0] += 1

                if len(res) < 1 or head >= res[-1]:
                    # append and continue on next level
                    res += remove
                    unique_remove_type[lst_idx][1] = True
                    lst_idx += 1
                    break  # inner loop
                elif unique_remove_type[lst_idx][0] == 2:
                    # reset status and backtrack to previous level
                    unique_remove_type[lst_idx] = [0, False]
                    lst_idx -= 1
                    break
                # else continue loop

    return list(map(lambda i: nums[i], res)) if res else [-1]


class SubsequenceRemovalTest(unittest.TestCase):
    def test_default(self):
        nums = [1, 2, 3, 1, 2, 3, 3, 6, 4]
        expected = [1, 2, 3, 3]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(len(expected), remove_subsequence_length(nums))
    
    def test_default2(self):
        nums = [2, 3, 1, 2, 3, 3, 6, 4, 1]
        expected = [1, 2, 3, 3]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(len(expected), remove_subsequence_length(nums))
        
    def test_empty(self):
        nums = []
        expected = [-1]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(0, remove_subsequence_length(nums))
    
    def test_remove_to_empty_from_1(self):
        nums = [1]
        expected = [-1]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(0, remove_subsequence_length(nums))
        
    def test_remove_to_empty_from_any(self):
        nums = [1, 2, 3, 4, 5]
        expected = [-1]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(0, remove_subsequence_length(nums))
        
    def test_attempt_max_backtracking(self):
        nums = [1, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 7]
        expected = [1, 2, 3, 4, 5, 6, 7]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(len(expected), remove_subsequence_length(nums))

    def test_attempt_max_backtracking2(self):
        nums = [1, 7, 6, 5, 4, 3, 2, 1, 2, 3, 3, 4, 4, 7, 7, 7]
        expected = [1, 2, 3, 3, 4, 4, 7, 7, 7]
        self.assertEqual(expected, remove_subsequence(nums))
        self.assertEqual(len(expected), remove_subsequence_length(nums))


if __name__ == '__main__':
    unittest.main()