Minimum Operations to Make a Subsequence

Hard
1395.

Minimum Operations to Make a Subsequence

Minimum Operations to Make a Subsequence is a hard coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

target holds distinct integers; arr is any integer array (it may repeat values).

In one operation you insert a single integer anywhere in arr (at the front, at the end, or between two elements).

Return the minimum number of operations needed so that target becomes a subsequence of arr — its elements appear in arr in the same order, not necessarily contiguously.

Example 1

Input
target = [5,1,3], arr = [9,4,2,3,4]
Output
2
Explanation
Insert 5 and 1 before the 3: `[5,9,4,1,2,3,4]`.

Example 2

Input
target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output
3

Example 3

Input
target = [2,7], arr = [2,7,2]
Output
0

Constraints

  • 1 <= target.length, arr.length <= 10^5
  • 1 <= target[i], arr[i] <= 10^9
  • target contains no duplicates
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} target
 * @param {number[]} arr
 * @return {number}
 */
var minOperations = function(target, arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make a Subsequence — Solution

Minimum Operations to Make a Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Operations to Make a Subsequence is a hard coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

Problem statement

target holds distinct integers; arr is any integer array (it may repeat values).

In one operation you insert a single integer anywhere in arr (at the front, at the end, or between two elements).

Return the minimum number of operations needed so that target becomes a subsequence of arr — its elements appear in arr in the same order, not necessarily contiguously.

Example 1

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: Insert 5 and 1 before the 3: `[5,9,4,1,2,3,4]`.

Example 2

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

Example 3

Input: target = [2,7], arr = [2,7,2]
Output: 0

Constraints

  • 1 <= target.length, arr.length <= 10^5
  • 1 <= target[i], arr[i] <= 10^9
  • target contains no duplicates

Hints for Minimum Operations to Make a Subsequence

  1. Hint 1

    Whatever part of target already appears in order inside arr can stay; everything else must be inserted. So the answer is target.length minus the longest common subsequence.

  2. Hint 2

    Because target is distinct, replace each element of arr by its position in target (dropping values not in target).

  3. Hint 3

    A common subsequence is now a strictly increasing subsequence of those positions — find the longest one in O(n log n) with patience sorting and binary search.

How to solve Minimum Operations to Make a Subsequence

The answer is |target| - LCS(target, arr). With distinct target values, the LCS equals the longest strictly increasing subsequence of the target-positions of arr's elements, which the binary-search LIS computes in O(m log m).

Approach

  1. Map every value of target to its index.
  2. Walk arr; skip values not in target, and turn the rest into their target indices.
  3. Maintain tails, where tails[len - 1] is the smallest possible last index of an increasing run of length len; for each index p, binary-search the first tail >= p and replace it (or append p).
  4. Return target.length - tails.length.

Why it works

Elements of target that are matched in order to elements of arr need no insertion, and the rest need exactly one each, so maximising the matched part is the whole problem. Matching in order means the chosen arr elements have strictly increasing target positions — the LIS. The tails array is sorted, and replacing the first tail >= p keeps each length's best ending, so its final length is the LIS length.

Complexity

  • Time — O(n + m log m)
  • Space — O(n + m)

Pitfalls

  • The quadratic LCS table is far too big for 10^5 × 10^5 — the distinctness of target is what makes the LIS reduction possible.
  • Use strict increase (lower bound): a repeated value in arr maps to the same position and cannot be matched twice.
  • Values of arr that are absent from target are simply ignored.

Reference solution

Python

from typing import List
import bisect

def minOperations(target: List[int], arr: List[int]) -> int:
    pos = {v: i for i, v in enumerate(target)}
    tails = []
    for v in arr:
        p = pos.get(v)
        if p is None:
            continue
        k = bisect.bisect_left(tails, p)
        if k == len(tails):
            tails.append(p)
        else:
            tails[k] = p
    return len(target) - len(tails)

Java

public static int minOperations(int[] target, int[] arr) {
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < target.length; i++) pos.put(target[i], i);
    int[] tails = new int[arr.length];
    int len = 0;
    for (int v : arr) {
        Integer p = pos.get(v);
        if (p == null) continue;
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < p) lo = mid + 1; else hi = mid;
        }
        tails[lo] = p;
        if (lo == len) len++;
    }
    return target.length - len;
}

C++

int minOperations(vector<int>& target, vector<int>& arr) {
    unordered_map<int, int> pos;
    for (int i = 0; i < (int)target.size(); i++) pos[target[i]] = i;
    vector<int> tails;
    for (int v : arr) {
        auto f = pos.find(v);
        if (f == pos.end()) continue;
        int p = f->second;
        auto it = lower_bound(tails.begin(), tails.end(), p);
        if (it == tails.end()) tails.push_back(p); else *it = p;
    }
    return (int)target.size() - (int)tails.size();
}

JavaScript

var minOperations = function(target, arr) {
    var pos = new Map();
    for (var i = 0; i < target.length; i++) pos.set(target[i], i);
    var tails = [];
    for (var j = 0; j < arr.length; j++) {
        var p = pos.get(arr[j]);
        if (p === undefined) continue;
        var lo = 0, hi = tails.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (tails[mid] < p) lo = mid + 1; else hi = mid;
        }
        if (lo === tails.length) tails.push(p); else tails[lo] = p;
    }
    return target.length - tails.length;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets