Minimum Operations to Make a Subsequence

Problem Description

Ah, the classic dilemma of trying to make a sequence out of a jumbled mess of numbers! Imagine you’re at a party, and you want to form a conga line with your friends, but instead of everyone lining up nicely, they’re all scattered around the room like they just heard the DJ play “Baby Shark.” Your goal? To get them in order with the least amount of shoving and pleading.

In the LeetCode problem “Minimum Operations to Make a Subsequence,” you are given two lists: target and arr. Your mission, should you choose to accept it, is to determine the minimum number of operations required to make target a subsequence of arr. An operation is defined as removing an element from arr.

So, if you think about it, it’s like trying to convince your friends to stop dancing and line up in a specific order. Good luck with that!

Code Solution


class Solution:
    def minOperations(self, target: list[int], arr: list[int]) -> int:
        indices = []
        numToIndex = {num: i for i, num in enumerate(target)}

        for a in arr:
            if a in numToIndex:
                indices.append(numToIndex[a])

        return len(target) - self._lengthOfLIS(indices)

    def _lengthOfLIS(self, nums: list[int]) -> int:
        tails = []
        for num in nums:
            if not tails or num > tails[-1]:
                tails.append(num)
            else:
                tails[bisect.bisect_left(tails, num)] = num
        return len(tails)

Approach Explanation

The approach taken in the code is quite clever. First, it maps each number in the target list to its index. Then, it iterates through the arr list, checking if each number exists in the target. If it does, it appends the corresponding index to a new list called indices.

The real magic happens when it calculates the length of the longest increasing subsequence (LIS) from the indices list. The minimum operations required to make target a subsequence of arr is simply the length of target minus the length of this LIS.

In simpler terms, it’s like figuring out how many of your friends are already in line and how many you need to drag into position.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n), where n is the length of `arr`. This is due to the binary search used in finding the position to replace elements in the `tails` list.
Space Complexity	O(n) for storing the `indices` list.

Real-World Example

Let’s say you’re organizing a group photo with your friends, and you want them to stand in a specific order. Some of them are already in the right spots, while others are just wandering around, oblivious to your pleas. The number of friends you need to convince to move is akin to the operations you need to perform to make target a subsequence of arr.