Minimum Operations to Make a Subsequence - Practice Coding Problems

Minimum Operations to Make a Subsequence - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: target = [5,1,3], arr = [9,4,2,3,4]

› Output: 2

💡 Note: Only element 3 from target appears in arr at the correct relative position. We need to insert 5 and 1, so 2 operations are needed.

Example 2 — Multiple Elements Match

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

› Output: 3

💡 Note: The longest subsequence we can form is [4,6,8] or [4,2,3] or [6,8] etc. The optimal is length 3, so we need 6-3=3 operations.

Example 3 — No Common Elements

$ Input: target = [1,2,3], arr = [4,5,6]

› Output: 3

💡 Note: No elements from target appear in arr, so we need to insert all 3 elements.

Constraints

1 ≤ target.length ≤ 10⁵
1 ≤ arr.length ≤ 10⁵
1 ≤ target[i], arr[i] ≤ 10⁹
All elements in target are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

target=[5,1,3], arr=[9,4,2,3,4] - need target as subsequence of arr

Find Common Elements

Only element 3 appears in both arrays in valid position

Calculate Operations

Need to insert missing elements: 5 and 1 → 2 operations

Key Takeaway

🎯 Key Insight: Transform the problem into finding the Longest Increasing Subsequence after mapping elements to positions

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is to transform this into a Longest Increasing Subsequence (LIS) problem. Map each target element to its position, then find the LIS of positions from arr elements. Best approach uses binary search for LIS with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized LIS with Binary Search	O(n log n + m log m)	O(n + m)	Use binary search to find LIS in O(n log n) time after position mapping
Hash Map + LIS Transformation	O(n²)	O(n + k)	Transform problem to Longest Increasing Subsequence using position mapping
Brute Force - Direct Subsequence Matching	O(n + m)	O(1)	Directly find longest common subsequence using two pointers

Optimized LIS with Binary Search — Algorithm Steps

Map target elements to positions
Transform arr to position array
Use binary search based LIS algorithm
Return target.length - LIS length

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Mapping

Map target elements to positions: {5→0, 1→1, 3→2}

Transform to Positions

Convert arr=[9,4,2,3,4] to positions=[2] (only 3 exists)

Binary Search LIS

Use binary search to maintain sorted tails array efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int binarySearch(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int lengthOfLIS(int* nums, int size) {
    if (size == 0) return 0;
    
    int* tails = (int*)malloc(size * sizeof(int));
    int tailsSize = 0;
    
    for (int i = 0; i < size; i++) {
        int pos = binarySearch(tails, tailsSize, nums[i]);
        if (pos == tailsSize) {
            tails[tailsSize++] = nums[i];
        } else {
            tails[pos] = nums[i];
        }
    }
    
    int result = tailsSize;
    free(tails);
    return result;
}

int solution(int* target, int targetSize, int* arr, int arrSize) {
    // Simple hash map using array (assuming values are small)
    int posMap[100001];
    memset(posMap, -1, sizeof(posMap));
    
    for (int i = 0; i < targetSize; i++) {
        if (target[i] >= 0 && target[i] <= 100000) {
            posMap[target[i]] = i;
        }
    }
    
    int positions[100000];
    int posCount = 0;
    
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] >= 0 && arr[i] <= 100000 && posMap[arr[i]] != -1) {
            positions[posCount++] = posMap[arr[i]];
        }
    }
    
    int lisLength = lengthOfLIS(positions, posCount);
    return targetSize - lisLength;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int target[1000], arr[100000];
    int targetSize = 0, arrSize = 0;
    
    // Parse first array
    char* ptr = strtok(line1, "[],\n ");
    while (ptr != NULL) {
        target[targetSize++] = atoi(ptr);
        ptr = strtok(NULL, "[],\n ");
    }
    
    // Parse second array
    ptr = strtok(line2, "[],\n ");
    while (ptr != NULL) {
        arr[arrSize++] = atoi(ptr);
        ptr = strtok(NULL, "[],\n ");
    }
    
    int result = solution(target, targetSize, arr, arrSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log m)

O(n) for mapping + O(m log m) for optimized LIS where m is arr length

⚡ Linearithmic

Space Complexity

O(n + m)

Hash map for positions O(n) plus arrays for LIS computation O(m)

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized LIS with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler