Watch 7 video solutions for Minimum Operations to Make a Subsequence, a hard level problem involving Array, Hash Table, Binary Search. This walkthrough by Hua Hua has 1,649 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.
In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.
Return the minimum number of operations needed to make target a subsequence of arr.
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.
Example 1:
Input: target = [5,1,3],arr= [9,4,2,3,4] Output: 2 Explanation: You can add 5 and 1 in such a way that makesarr= [5,9,4,1,2,3,4], then target will be a subsequence ofarr.
Example 2:
Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3
Constraints:
1 <= target.length, arr.length <= 1051 <= target[i], arr[i] <= 109target contains no duplicates.Problem Overview: You are given two arrays: target (with distinct values) and arr. The task is to compute the minimum number of insert operations needed so that target becomes a subsequence of arr. Instead of simulating insertions directly, the key observation is that maximizing the part of target already appearing in order inside arr minimizes the required operations.
Approach 1: Dynamic Programming (O(n * m) time, O(n * m) space)
This approach treats the problem as a variation of the Longest Common Subsequence (LCS). Compute the LCS between target and arr using a DP table where dp[i][j] represents the LCS length for the first i elements of target and first j elements of arr. If elements match, extend the subsequence; otherwise take the maximum of skipping one element from either array. The minimum operations required equals target.length - LCS. While straightforward and useful for understanding subsequence alignment, the O(n * m) time complexity becomes too slow for large inputs.
Approach 2: Hash Map + Longest Increasing Subsequence (O(n log n) time, O(n) space)
The optimal solution converts the problem into a Longest Increasing Subsequence (LIS) problem. Since target contains unique values, create a hash map mapping each value to its index in target. Then iterate through arr and replace each element with its mapped index if it exists in the map. This produces a sequence of indices representing the order of elements relative to target.
The goal becomes finding the longest increasing subsequence of these indices. An increasing sequence means elements appear in the correct order relative to target. Compute LIS efficiently using binary search and a dynamic array that stores the smallest tail value for subsequences of each length. Each index either extends the sequence or replaces a larger tail via binary search.
If the LIS length is k, then k elements of target already appear in correct order inside arr. The remaining target.length - k elements must be inserted. This reduces the problem to a classic binary search optimization combined with hash table indexing and sequence processing over an array.
Recommended for interviews: The hash map + LIS approach is what most interviewers expect. It demonstrates the ability to transform a subsequence matching problem into an index-ordering problem and apply the O(n log n) LIS technique. The dynamic programming solution shows understanding of subsequences but does not scale well for the input constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (LCS) | O(n * m) | O(n * m) | Good for learning subsequence matching or when constraints are small |
| Hash Map + Longest Increasing Subsequence | O(n log n) | O(n) | Optimal for large inputs; converts order matching into LIS using binary search |