1713. Minimum Operations to Make a Subsequence

Problem Description

The problem presents two integer arrays, target and arr. The target array contains distinct integers, meaning no duplicates. On the other hand, arr can contain duplicates and does not necessarily have the same elements or element order as target.

The primary goal is to transform the arr array into a sequence that contains target as a subsequence by performing a certain operation. This operation involves inserting any integer at any position in arr. The task is to determine the minimum number of such operations needed to achieve the goal.

A subsequence is defined as a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements. The problem asks for the smallest number of insertions required to make target a subsequence of arr.

Intuition

The essential intuition for solving this problem comes from understanding the nature of subsequences and the relationship between the target array and the arr array. Since the target consists of distinct integers, any repeated elements in arr do not help us in forming the subsequence and thus do not affect the number of operations required.

The intuition for the solution lies in finding the longest common subsequence between target and arr and using this to determine the minimum number of operations. However, since the problem asks us to perform insertions to make target a subsequence of arr, rather than finding a common subsequence of both, we can focus on finding a subsequence in arr that matches the order of target. The length of this subsequence in arr will allow us to calculate the operations needed as len(target) - len(longest_subsequence_in_arr_matching_target).

To find the longest increasing subsequence efficiently, we take advantage of the fact that numbers in target are unique, which allows us to assign a unique index to each number in target. Then, we process arr and transform it into a sequence of indices according to the positions of its elements in target. Now the problem becomes finding the length of the longest increasing subsequence in this transformed sequence, which can be done using a segment tree or, as in this code, using a Binary Indexed Tree (BIT), also known as a Fenwick Tree.

The Binary Indexed Tree is used to store information about the longest increasing subsequence efficiently while we iterate through the transformed arr. For each element, we find the length of the longest subsequence up to that point and update our tree. After processing all elements, the length of the longest increasing subsequence is known, which gives us the number of elements in arr that already form a subsequence with target. Subtracting this number from the length of target gives us the minimum number of operations needed.

Learn more about Greedy and Binary Search patterns.

Solution Approach

The solution uses a Binary Indexed Tree (BIT) to find the length of the Longest Increasing Subsequence (LIS) efficiently, which is a key part in solving this problem.

Here is a step-by-step implementation of the solution:

Create a dictionary d from elements of target to their indices. This serves two purposes. It allows us to check if an element of arr is in target in constant time and gives us a way to transform elements of arr to their corresponding indices in target.
Create a new list nums consisting of the indices in target of the elements in arr. This transformation helps us to ignore elements in arr which are not in target and to work with indices rather than values, simplifying the problem to finding an LIS (which indicates the longest subsequence in arr that is in order with target).
Compute the length of the LIS in this new list nums. To perform this step:
- We create a BIT class with an update and query operation, where update(x, val) will update the tree at index x with the value val, and query(x) retrieves the maximum value from the beginning of the array up to index x.
- Then, we sort nums to eliminate duplicates and map each element to its index plus one (to avoid 0 index in BIT as the tree is 1-indexed) and create an instance of BIT with the length of this unique elements list.
- Iterate through each element v in the original nums list (which is a list of indices within target), and for each of these, use the BIT to find the longest subsequence up until that point and update the value of that index plus one in the tree with the new length if it's larger than the current value.
The length of the LIS is equivalent to the number of operations we don't need to perform. Therefore, we subtract the length of the LIS from the length of target to find the minimum number of operations required to make target a subsequence of arr.

By understanding the definition of a subsequence and using the efficient updates and queries of a Binary Indexed Tree to track the length of the longest subsequence, the implementation solves the problem with a time complexity of O(N log N), where N is the length of arr.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's work through a small example to illustrate the solution approach:

Suppose we are given the following input:

target = [5, 1, 3]
arr = [3, 5, 3, 1, 3, 5]

Here's the step-by-step process:

Creating the dictionary: We map each element in target to its index:
- d = {5: 0, 1: 1, 3: 2}
Transforming arr into indices: Using the dictionary d, we convert arr to a sequence of indices based on target (ignoring elements not found in target):
- nums = [2, 0, 2, 1, 2, 0]
Computing the LIS:
- Initialize a Binary Indexed Tree to help us compute the LIS.
- Process the transformed nums. As we iterate over nums, for each element v = nums[i], we find the length of the longest subsequence that we can achieve up to the current index.
- Update the BIT with the new LIS length at the index corresponding to v if it's larger than the current recorded length.

For our example nums = [2, 0, 2, 1, 2, 0], let's see how the Binary Indexed Tree updates:

Initially, the BIT is all zeroes: BIT = [0, 0, 0]
We process the first element 2: BIT = [0, 0, 1] (longest subsequence ending in index 2 is of length 1)
Process 0: BIT = [1, 0, 1] (subsequence of length 1 ending in index 0)
Process the second 2: BIT remains the same, as 2 does not add to the longest subsequence when coming after 0
Process 1: BIT = [1, 2, 1] (subsequence of length 2 can be formed by [3 (index 0), 1 (index 1)])
Continue with the rest of the elements...

By the end of this process, the BIT's entry for index 2 (which is the largest index) will reflect the length of the LIS of our nums sequence. It turns out that our example has a longest subsequence [0, 1] or [5, 1] in terms of the original target array, which has a length of 2.

Calculating Minimum Operations: Finally, we determine the minimum insertions needed:
- minimum_operations = len(target) - LIS_length
- minimum_operations = 3 - 2 = 1

Thus, the minimum number of operations required to make target a subsequence of arr is one insertion.

In our example, we could insert the number 1 at the beginning or end of the arr to make target a subsequence of arr:

Insert 1 at the beginning: [1, 3, 5, 3, 1, 3, 5] -> [1, - (ignored), 5, 1, 3]
Insert 1 at the end is unnecessary since target is already a subsequence of arr.

This illustrates how using indices and a BIT can efficiently solve the problem of finding the minimum number of insertions to make one array a subsequence of another.

Solution Implementation

1from typing import List
2
3class BinaryIndexedTree:
4    def __init__(self, size):
5        self.size = size
6        self.tree_array = [0] * (size + 1)
7
8    @staticmethod
9    def lowbit(index):
10        # Calculate the least significant bit (LSB)
11        return index & -index
12
13    def update(self, index, val):
14        # Update the tree with the value 'val'
15        while index <= self.size:
16            # Maintain the maximum value in the path
17            self.tree_array[index] = max(self.tree_array[index], val)
18            # Move to next index to be updated
19            index += BinaryIndexedTree.lowbit(index)
20
21    def query(self, index):
22        max_val = 0
23        while index:
24            # Find max value up to the 'index'
25            max_val = max(max_val, self.tree_array[index])
26            # Move to parent index
27            index -= BinaryIndexedTree.lowbit(index)
28        return max_val
29
30
31class Solution:
32    def minOperations(self, target: List[int], arr: List[int]) -> int:
33        # Map each target value to its index
34        index_mapping = {value: idx for idx, value in enumerate(target)}
35        # Filter and map the values in 'arr' using the index_mapping
36        mapped_nums = [index_mapping[value] for value in arr if value in index_mapping]
37        # Calculate and return the min number of operations
38        return len(target) - self.lengthOfLIS(mapped_nums)
39
40    def lengthOfLIS(self, nums: List[int]) -> int:
41        # Create a sorted list of unique values from 'nums'
42        unique_sorted_nums = sorted(set(nums))
43        # Map each value to its index (+1 to avoid zero index)
44        index_mapping = {value: idx for idx, value in enumerate(unique_sorted_nums, 1)}
45        tree = BinaryIndexedTree(len(index_mapping))
46        longest_increasing_subsequence = 0
47        for value in nums:
48            # Map the value to its corresponding index in the tree
49            mapped_index = index_mapping[value]
50            # Find the length of LIS ending with 'value'
51            current_lis = tree.query(mapped_index - 1) + 1
52            # Update the maximum length found so far
53            longest_increasing_subsequence = max(longest_increasing_subsequence, current_lis)
54            # Update the tree with the new length
55            tree.update(mapped_index, current_lis)
56        # Return the length of the longest increasing subsequence
57        return longest_increasing_subsequence
58

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.TreeSet;
6
7// Class representing a Binary Indexed Tree (also known as a Fenwick Tree)
8class BinaryIndexedTree {
9    private int size; // The size of the array
10    private int[] tree; // The array representation of the tree
11
12    // Constructor initializes the tree with a specified size
13    public BinaryIndexedTree(int size) {
14        this.size = size;
15        this.tree = new int[size + 1];
16    }
17
18    // Method to calculate the lowest one bit of an integer
19    public static int lowbit(int x) {
20        return x & -x;
21    }
22
23    // Method to update the tree with a new value at a specific index
24    public void update(int index, int val) {
25        while (index <= size) {
26            tree[index] = Math.max(tree[index], val);
27            index += lowbit(index);
28        }
29    }
30
31    // Method to query the maximum value in the tree up to a certain index
32    public int query(int index) {
33        int maxVal = 0;
34        while (index > 0) {
35            maxVal = Math.max(maxVal, tree[index]);
36            index -= lowbit(index);
37        }
38        return maxVal;
39    }
40}
41
42// Solution class containing methods to solve the minimum operations problem
43class Solution {
44    // Method that returns the minimum number of operations to make one array a subsequence of another
45    public int minOperations(int[] target, int[] arr) {
46        Map<Integer, Integer> valueToIndex = new HashMap<>();
47        for (int i = 0; i < target.length; ++i) {
48            valueToIndex.put(target[i], i);
49        }
50        List<Integer> indices = new ArrayList<>();
51        for (int value : arr) {
52            if (valueToIndex.containsKey(value)) {
53                indices.add(valueToIndex.get(value));
54            }
55        }
56        return target.length - lengthOfLIS(indices);
57    }
58
59    // Private method that computes the length of the Longest Increasing Subsequence (LIS)
60    private int lengthOfLIS(List<Integer> nums) {
61        TreeSet<Integer> orderedSet = new TreeSet<>();
62        for (int v : nums) {
63            orderedSet.add(v);
64        }
65        int idx = 1;
66        Map<Integer, Integer> valueToTreeIndex = new HashMap<>();
67        for (int v : orderedSet) {
68            valueToTreeIndex.put(v, idx++);
69        }
70        int lisLength = 0;
71        BinaryIndexedTree tree = new BinaryIndexedTree(nums.size());
72        for (int v : nums) {
73            int x = valueToTreeIndex.get(v);
74            int len = tree.query(x - 1) + 1;
75            lisLength = Math.max(lisLength, len);
76            tree.update(x, len);
77        }
78        return lisLength;
79    }
80}
81

1#include <vector>
2#include <unordered_map>
3#include <set>
4using namespace std;
5
6class BinaryIndexedTree {
7public:
8    int size;
9    vector<int> tree;
10
11    // Constructor initializes the tree
12    BinaryIndexedTree(int size)
13        : size(size), tree(size + 1) {}
14
15    // Update function applies the given value using the max operation
16    void update(int index, int val) {
17        while (index <= size) {
18            tree[index] = max(tree[index], val);
19            index += lowBit(index);
20        }
21    }
22
23    // Query function finds the maximum value up to the given index
24    int query(int index) {
25        int result = 0;
26        while (index > 0) {
27            result = max(result, tree[index]);
28            index -= lowBit(index);
29        }
30        return result;
31    }
32
33    // Helper function to calculate the lowest set bit (important for BIT operations)
34    int lowBit(int x) {
35        return x & -x;
36    }
37};
38
39class Solution {
40public:
41    // Function to calculate the minimum operations needed to make target a subsequence of arr
42    int minOperations(vector<int>& target, vector<int>& arr) {
43        unordered_map<int, int> indexMap;
44      
45        // Mapping each element of target to its index
46        for (int i = 0; i < target.size(); ++i) {
47            indexMap[target[i]] = i;
48        }
49      
50        // Creating a list of indices of elements in arr that are found in target
51        vector<int> relevantIndices;
52        for (int num : arr) {
53            if (indexMap.count(num)) {
54                relevantIndices.push_back(indexMap[num]);
55            }
56        }
57      
58        // The result is the size of target minus the length of the longest increasing subsequence of relevant indices
59        return target.size() - lengthOfLIS(relevantIndices);
60    }
61
62    // Function to find the length of the longest increasing subsequence using a Binary Indexed Tree
63    int lengthOfLIS(vector<int>& nums) {
64        set<int> sortedNums(nums.begin(), nums.end());
65        int index = 1;
66        unordered_map<int, int> indexMap;
67      
68        // Create a mapping from each number to its rank in the sorted set
69        for (int value : sortedNums) {
70            indexMap[value] = index++;
71        }
72      
73        // Using Binary Indexed Tree to keep track of the longest increasing subsequence dynamically
74        BinaryIndexedTree bit(indexMap.size());
75        int maxLength = 0;
76        for (int num : nums) {
77            int currentIndex = indexMap[num];
78            int currentLength = bit.query(currentIndex - 1) + 1;
79            maxLength = max(maxLength, currentLength);
80            bit.update(currentIndex, currentLength);
81        }
82        return maxLength;
83    }
84};
85

1// Import the necessary libraries for collections and algorithm
2import { max } from 'lodash';
3
4// TypeScript doesn't have a built-in max function, you could use Math.max or a utility library like lodash.
5
6// Initialize the size of the Binary Indexed Tree and the tree structure as an array
7let size: number;
8let tree: number[];
9
10// Function to initialize the Binary Indexed Tree
11function initializeBIT(newSize: number) {
12  size = newSize;
13  tree = Array(newSize + 1).fill(0);
14}
15
16// Function to update a value in the Binary Indexed Tree using max operation
17function update(index: number, val: number): void {
18  while (index <= size) {
19    tree[index] = max([tree[index], val]);
20    index += lowBit(index);
21  }
22}
23
24// Function to query the maximum value in the Binary Indexed Tree up to a given index
25function query(index: number): number {
26  let result = 0;
27  while (index > 0) {
28    result = max([result, tree[index]]);
29    index -= lowBit(index);
30  }
31  return result;
32}
33
34// Helper function for Binary Indexed Tree to calculate the lowest set bit
35function lowBit(x: number): number {
36  return x & -x;
37}
38
39// Function to calculate the minimum number of operations needed to make the target a subsequence of arr
40function minOperations(target: number[], arr: number[]): number {
41  let indexMap: Map<number, number> = new Map<number, number>();
42
43  // Map each element of target to its index
44  target.forEach((num, index) => indexMap.set(num, index));
45
46  // Create a list of indices in arr that are present in target
47  let relevantIndices: number[] = arr
48    .filter(num => indexMap.has(num))
49    .map(num => indexMap.get(num)!);
50
51  // Deduce the result from the size of target and the length of the longest increasing subsequence of relevantIndices
52  return target.length - lengthOfLIS(relevantIndices);
53}
54
55// Function to find the length of the longest increasing subsequence (LIS)
56function lengthOfLIS(nums: number[]): number {
57  let sortedNums = Array.from(new Set(nums)).sort((a, b) => a - b);
58  let index = 1;
59  let indexMap: Map<number, number> = new Map<number, number>();
60
61  // Map each number to its rank in the sorted list
62  sortedNums.forEach(value => indexMap.set(value, index++));
63
64  // Initialize the Binary Indexed Tree for tracking the longest increasing subsequence dynamically
65  initializeBIT(indexMap.size);
66  let maxLength = 0;
67
68  // Calculate the LIS using the Binary Indexed Tree
69  nums.forEach(num => {
70    let currentIndex = indexMap.get(num)!;
71    let currentLength = query(currentIndex - 1) + 1;
72    maxLength = max([maxLength, currentLength]);
73    update(currentIndex, currentLength);
74  });
75
76  return maxLength;
77}
78

Time and Space Complexity

Time Complexity

The time complexity of this solution is analyzed as follows:

Constructing a dictionary d from target has a time complexity of O(N) where N is the length of target.
Filtering arr to create nums using dictionary d has a time complexity of O(M) where M is the length of arr.
So far, the overall time complexity is O(N + M).
Sorting the unique values of nums has a time complexity of O(P log P) where P is the number of unique values in nums.
Then, creating a mapping m is an O(P) operation.
The lengthOfLIS involves iterating over all elements in nums and making use of Binary Indexed Tree operations (query and update), which has O(log P) complexity for each call.
As it does this for every one of the K numbers in nums, this part contributes an O(K log P) complexity.

Thus, the overall time complexity of the solution is O(N + M + P log P + K log P).

Note: Since the Binary Indexed Tree has a size equal to the amount of unique elements in the nums array and all values are mapped to a continuous range, P is the upper-bound for K as well, and therefore O(K log P) can be considered as O(P log P) in worst case scenario.

Space Complexity

The space complexity is calculated based on the data structures used:

The dictionary d and mapping m both store at most N and P elements respectively, contributing O(N) and O(P) space.
The Binary Indexed Tree (c array) has a length of P + 1, providing an additional O(P) space complexity.
The transformed array nums which stores filtered and mapped values from arr based on target contributes an O(M) space requirement.

Therefore, the overall space complexity of the solution is O(N + P + M) with P <= N <= M generally.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know