Minimum Operations to Make a Subsequence

Problem Description

Ah, the classic dilemma of life: how to make a sequence of numbers without breaking a sweat! The problem at hand is the “Minimum Operations to Make a Subsequence.” Imagine you have a target sequence of numbers, and you also have a jumbled array of numbers. Your mission, should you choose to accept it, is to transform that jumbled array into the target sequence with the least amount of effort—because who has time for unnecessary operations, right?

In simpler terms, you need to figure out how many numbers you need to remove from the array to make it a subsequence of the target. Think of it like trying to fit into your favorite pair of jeans after the holidays—sometimes, you just have to let go of a few extra pounds (or numbers, in this case).

Code Solution


class Solution {
  public int minOperations(int[] target, int[] arr) {
    List indices = new ArrayList<>();
    Map numToIndex = new HashMap<>();

    for (int i = 0; i < target.length; ++i)
      numToIndex.put(target[i], i);

    for (final int a : arr)
      if (numToIndex.containsKey(a))
        indices.add(numToIndex.get(a));

    return target.length - lengthOfLIS(indices);
  }

  private int lengthOfLIS(List nums) {
    List tails = new ArrayList<>();
    for (final int num : nums)
      if (tails.isEmpty() || num > tails.get(tails.size() - 1))
        tails.add(num);
      else
        tails.set(firstGreaterEqual(tails, num), num);
    return tails.size();
  }

  private int firstGreaterEqual(List A, int target) {
    final int i = Collections.binarySearch(A, target);
    return i < 0 ? -i - 1 : i;
  }
}

Approach Explanation

The code works by first mapping the target numbers to their indices. Then, it filters the input array to only include numbers that exist in the target, converting them into their respective indices. The crux of the solution lies in finding the length of the longest increasing subsequence (LIS) of these indices. The minimum operations required will be the difference between the length of the target and the length of this LIS.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a party, and you want to form a conga line (the target sequence) with your friends (the array). However, some of your friends are busy doing the Macarena (not in the target sequence). You need to figure out how many friends you need to convince to join the conga line to make it happen. The fewer friends you have to convince, the better!