Find minimum length sub-array which has given sub-sequence in it

0 0 8 minutes read

Given an array arr[] of N elements, the task is to find the length of the smallest sub-array which has the sequence {0, 1, 2, 3, 4} as a sub-sequence in it.

Examples:

Input: arr[] = {0, 1, 2, 3, 4, 2, 0, 3, 4}
Output: 5
The required Subarray is {0, 1, 2, 3, 4} with minimum length.
The entire array also includes the sequence
but it is not minimum in length.

Input: arr[] = {0, 1, 1, 0, 1, 2, 0, 3, 4}
Output: 6

Approach:

Maintain an array pref[] of size 5 (equal to the size of the sequence) where pref[i] stores the count of i in the given array till now.
We can increase the count of pref for any number only if pref[Array[i] – 1] > 0. This is because, in order to have the complete sequence as a sub-sequence of the array, all the previous elements of the sequence must occur before the current. Also, store the indices of these elements found so far.
Whenever we witness 4 i.e., the possible end of the sub-sequence and pref[3] > 0 implies that we have found the sequence in our array. Now mark that index as the end as well as the start point and for all other numbers in sequence from 3 to 0. Apply binary search to find the closest index to the next element of the sequence, which will give us the size of the current valid sub-array.
The answer is the minimum size of all the valid sub-arrays found in the previous step.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX_INT 1000000
 
// Function to return the minimum length
// of a sub-array which contains
// {0, 1, 2, 3, 4} as a sub-sequence
int solve(int Array[], int N)
{
    // To store the indices where 0, 1, 2,
    // 3 and 4 are present
    vector<int> pos[5];
 
    // To store if there exist a valid prefix
    // of sequence in array
    int pref[5] = { 0 };
 
    // Base Case
    if (Array[0] == 0) {
        pref[0] = 1;
        pos[0].push_back(0);
    }
 
    int ans = MAX_INT;
 
    for (int i = 1; i < N; i++) {
 
        // If current element is 0
        if (Array[i] == 0) {
 
            // Update the count of 0s till now
            pref[0]++;
 
            // Push the index of the new 0
            pos[0].push_back(i);
        }
        else {
 
            // To check if previous element of the
            // given sequence is found till now
            if (pref[Array[i] - 1] > 0) {
                pref[Array[i]]++;
                pos[Array[i]].push_back(i);
 
                // If it is the end of sequence
                if (Array[i] == 4) {
                    int end = i;
                    int start = i;
 
                    // Iterate for other elements of the
                    // sequence
                    for (int j = 3; j >= 0; j--) {
                        int s = 0;
                        int e = pos[j].size() - 1;
                        int temp = -1;
 
                        // Binary Search to find closest
                        // occurrence less than equal to
                        // starting point
                        while (s <= e) {
                            int m = (s + e) / 2;
                            if (pos[j][m] <= start) {
                                temp = pos[j][m];
                                s = m + 1;
                            }
                            else {
                                e = m - 1;
                            }
                        }
 
                        // Update the starting point
                        start = temp;
                    }
 
                    ans = min(ans, end - start + 1);
                }
            }
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int Array[] = { 0, 1, 2, 3, 4, 2, 0, 3, 4 };
    int N = sizeof(Array) / sizeof(Array[0]);
 
    cout << solve(Array, N);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG {
    static int MAX_INT = 1000000;
 
    // Function to return the minimum length
    // of a sub-array which contains
    // {0, 1, 2, 3, 4} as a sub-sequence
    static int solve(int[] array, int N)
    {
 
        // To store the indices where 0, 1, 2,
        // 3 and 4 are present
        int[][] pos = new int[5][10000];
 
        // To store if there exist a valid prefix
        // of sequence in array
        int[] pref = new int[5];
 
        // Base Case
        if (array[0] == 0) {
            pref[0] = 1;
            pos[0][pos[0].length - 1] = 0;
        }
 
        int ans = MAX_INT;
 
        for (int i = 1; i < N; i++) {
 
            // If current element is 0
            if (array[i] == 0) {
 
                // Update the count of 0s till now
                pref[0]++;
 
                // Push the index of the new 0
                pos[0][pos[0].length - 1] = i;
            }
 
            else {
 
                // To check if previous element of the
                // given sequence is found till now
                if (pref[array[i] - 1] > 0) {
                    pref[array[i]]++;
                    pos[array[i]][pos[array[i]].length - 1]
                        = i;
 
                    // If it is the end of sequence
                    if (array[i] == 4) {
                        int end = i;
                        int start = i;
 
                        // Iterate for other elements of the
                        // sequence
                        for (int j = 3; j >= 0; j--) {
                            int s = 0;
                            int e = pos[j].length - 1;
                            int temp = -1;
 
                            // Binary Search to find closest
                            // occurrence less than equal to
                            // starting point
                            while (s <= e) {
                                int m = (s + e) / 2;
                                if (pos[j][m] <= start) {
                                    temp = pos[j][m];
                                    s = m + 1;
                                }
                                else
                                    e = m - 1;
                            }
 
                            // Update the starting point
                            start = temp;
                        }
                        ans = Math.min(ans,
                                       end - start + 1);
                    }
                }
            }
        }
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] array = { 0, 1, 2, 3, 4, 2, 0, 3, 4 };
        int N = array.length;
 
        System.out.println(solve(array, N));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 implementation of the approach
 
MAX_INT = 1000000
 
# Function to return the minimum length
# of a sub-array which contains
# 0, 1, 2, 3, 4 as a sub-sequence
 
 
def solve(Array, N):
 
    # To store the indices where 0, 1, 2,
    # 3 and 4 are present
    pos = [[] for i in range(5)]
 
    # To store if there exist a valid prefix
    # of sequence in array
    pref = [0 for i in range(5)]
 
    # Base Case
    if (Array[0] == 0):
        pref[0] = 1
        pos[0].append(0)
 
    ans = MAX_INT
 
    for i in range(N):
 
        # If current element is 0
        if (Array[i] == 0):
 
            # Update the count of 0s till now
            pref[0] += 1
 
            # Push the index of the new 0
            pos[0].append(i)
 
        else:
 
            # To check if previous element of the
            # given sequence is found till now
            if (pref[Array[i] - 1] > 0):
                pref[Array[i]] += 1
                pos[Array[i]].append(i)
 
                # If it is the end of sequence
                if (Array[i] == 4):
                    end = i
                    start = i
 
                    # Iterate for other elements of the sequence
                    for j in range(3, -1, -1):
                        s = 0
                        e = len(pos[j]) - 1
                        temp = -1
 
                        # Binary Search to find closest occurrence
                        # less than equal to starting point
                        while (s <= e):
                            m = (s + e) // 2
                            if (pos[j][m] <= start):
                                temp = pos[j][m]
                                s = m + 1
 
                            else:
                                e = m - 1
 
                        # Update the starting point
                        start = temp
 
                    ans = min(ans, end - start + 1)
 
    return ans
 
# Driver code
 
 
Array = [0, 1, 2, 3, 4, 2, 0, 3, 4]
N = len(Array)
 
print(solve(Array, N))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG {
    static int MAX_INT = 1000000;
 
    // Function to return the minimum length
    // of a sub-array which contains
    // {0, 1, 2, 3, 4} as a sub-sequence
    static int solve(int[] array, int N)
    {
 
        // To store the indices where 0, 1, 2,
        // 3 and 4 are present
        int[, ] pos = new int[5, 10000];
 
        // To store if there exist a valid prefix
        // of sequence in array
        int[] pref = new int[5];
 
        // Base Case
        if (array[0] == 0) {
            pref[0] = 1;
            pos[0, pos.GetLength(0) - 1] = 0;
        }
 
        int ans = MAX_INT;
 
        for (int i = 1; i < N; i++) {
 
            // If current element is 0
            if (array[i] == 0) {
 
                // Update the count of 0s till now
                pref[0]++;
 
                // Push the index of the new 0
                pos[0, pos.GetLength(0) - 1] = i;
            }
 
            else {
 
                // To check if previous element of the
                // given sequence is found till now
                if (pref[array[i] - 1] > 0) {
                    pref[array[i]]++;
                    pos[array[i], pos.GetLength(1) - 1] = i;
 
                    // If it is the end of sequence
                    if (array[i] == 4) {
                        int end = i;
                        int start = i;
 
                        // Iterate for other elements of the
                        // sequence
                        for (int j = 3; j >= 0; j--) {
                            int s = 0;
                            int e = pos.GetLength(1) - 1;
                            int temp = -1;
 
                            // Binary Search to find closest
                            // occurrence less than equal to
                            // starting point
                            while (s <= e) {
                                int m = (s + e) / 2;
                                if (pos[j, m] <= start) {
                                    temp = pos[j, m];
                                    s = m + 1;
                                }
                                else
                                    e = m - 1;
                            }
 
                            // Update the starting point
                            start = temp;
                        }
                        ans = Math.Min(ans,
                                       end - start + 1);
                    }
                }
            }
        }
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] array = { 0, 1, 2, 3, 4, 2, 0, 3, 4 };
        int N = array.Length;
 
        Console.WriteLine(solve(array, N));
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript implementation of the approach
 
let MAX_INT = 1000000;
 
// Function to return the minimum length
// of a sub-array which contains
// {0, 1, 2, 3, 4} as a sub-sequence
function solve(array,N)
{
    // To store the indices where 0, 1, 2,
    // 3 and 4 are present
    let pos = new Array(5);
    for(let i=0;i<5;i++)
    {
        pos[i]=new Array(10000);
        for(let j=0;j<10000;j++)
        {
            pos[i][j]=0;
        }
    }
   
    // To store if there exist a valid prefix
    // of sequence in array
    let pref = new Array(5);
      for(let i=0;i<5;i++)
    {
        pref[i]=0;
    }
     
    // Base Case
    if (array[0] == 0)
    {
        pref[0] = 1;
        pos[0][pos[0].length - 1] = 0;
    }
   
    let ans = MAX_INT;
   
    for (let i = 1; i < N; i++) 
    {
   
        // If current element is 0
        if (array[i] == 0) 
        {
   
            // Update the count of 0s till now
            pref[0]++;
   
            // Push the index of the new 0
            pos[0][pos[0].length - 1] = i;
        } 
           
        else
        {
   
            // To check if previous element of the
            // given sequence is found till now
            if (pref[array[i] - 1] > 0) 
            {
                pref[array[i]]++;
                pos[array[i]][pos[array[i]].length - 1] = i;
   
                // If it is the end of sequence
                if (array[i] == 4)
                {
                    let end = i;
                    let start = i;
   
                    // Iterate for other elements of the sequence
                    for (let j = 3; j >= 0; j--) 
                    {
                        let s = 0;
                        let e = pos[j].length - 1;
                        let temp = -1;
   
                        // Binary Search to find closest occurrence
                        // less than equal to starting point
                        while (s <= e) 
                        {
                            let m = Math.floor((s + e) / 2);
                            if (pos[j][m] <= start) 
                            {
                                temp = pos[j][m];
                                s = m + 1;
                            } 
                            else
                                e = m - 1;
                        }
   
                        // Update the starting point
                        start = temp;
                    }
                    ans = Math.min(ans, end - start + 1);
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
let array=[0, 1, 2, 3, 4, 2, 0, 3, 4];
let N = array.length;
document.write(solve(array, N));
 
 
// This code is contributed by patel2127
</script>

Output:

Time Complexity: O(n.log n)
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!