Minimum Operations to Make a Subsequence in C++

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 (because who doesn’t love a good conga line?). You have a target sequence of people you want in your line, but your friends keep showing up in random order. The problem is to figure out how many of your friends you need to remove from the party to get that perfect conga line going.

In more technical terms, the problem is to find the minimum number of operations required to make a given target sequence a subsequence of another array.

Code Solution

Here’s the C++ solution to tackle this problem:


class Solution {
 public:
  int minOperations(vector& target, vector& arr) {
    vector indices;
    unordered_map numToIndex;

    for (int i = 0; i < target.size(); ++i)
      numToIndex[target[i]] = i;

    for (const int a : arr)
      if (const auto it = numToIndex.find(a); it != numToIndex.end())
        indices.push_back(it->second);

    return target.size() - lengthOfLIS(indices);
  }

 private:
  int lengthOfLIS(vector& nums) {
    vector tails;
    for (const int num : nums)
      if (tails.empty() || num > tails.back())
        tails.push_back(num);
      else
        tails[firstGreaterEqual(tails, num)] = num;
    return tails.size();
  }

 private:
  int firstGreaterEqual(const vector& A, int target) {
    return ranges::lower_bound(A, target) - A.begin();
  }
};

Approach Explanation

The code works by first mapping the target numbers to their indices. Then, it checks which of these indices can be found in the arr array. The goal is to find the longest increasing subsequence (LIS) of these indices, as this will tell us how many elements from the target can be retained. The minimum operations required will be the total number of elements in the target minus the length of this LIS.

Time and Space Complexity

Time Complexity: O(n log n), where n is the length of the arr array. This is due to the binary search used in finding the position of elements in the tails array.

Space Complexity: O(n) for storing the tails array and the numToIndex map.

Real-World Example

Let’s say you’re trying to organize a playlist for a road trip, but your friends keep adding random songs. Your target playlist is a specific order of songs you want to hear, but your friends’ suggestions are all over the place. You need to figure out how many songs you need to remove from their suggestions to get back to your perfect playlist. This is essentially what the problem is asking you to solve!