Find smallest subarray that contains all elements in same order

0 0 11 minutes read

Given two arrays of integers of size m and n. The task is to find the minimum length subarray in the first array that contains all the elements of second array.
Note: element of second array may be present in the large array in non-contiguous but order must same. ( m < n )

Examples :

Input :  A[] = {2, 2, 4, 5, 8, 9}  
         B[] = {2, 5, 9}  
Output : 5
Smallest subarray of A[] that contains all
elements of B[] is {2, 4, 5, 8, 9} which is
of size 5.

Input :  A[] = {5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7}  
         B[] = {5, 5, 7}  
Output : 3

Method 1 (Naive): A simple solution is to generate all subarrays of given array and check for every sub-array if it contains elements of another array or not. In the end, return the minimum length of sub-array that contain another array.

Below is the implementation of above idea.

C++

// CPP program to find smallest length 
// subarray that contains all elements 
// of another array.
#include <bits/stdc++.h>
using namespace std;
 
// function return the minimum length of sub_array
int minimumSubArray(int A[], int n, int B[], int m)
{
    int result = INT_MAX;
 
    // Pick starting point
    for (int i = 0; i < n; i++) {
 
        // Pick ending point
        for (int j = i; j < n; j++) {
 
            // k is index in first array and
            // 'index' is index in second array.
            int k, index = 0; 
            for (k = i; k <= j; k++) {
                if (A[k] == B[index])
                    index++;
                if (index == m)
                    break;
            }
 
            // update minimum length sub_array
            if (index == m && result > k - i + 1)
              result = (k == n) ? k - i : k - i + 1;
        }
    }
 
    // return minimum length subarray
    return result;
}
 
// driver program to test above function
int main()
{
    int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
    int B[] = { 5, 5, 7 };
    int n = sizeof(A)/sizeof(A[0]);
    int m = sizeof(B)/sizeof(B[0]);
    cout << minimumSubArray(A, n, B, m);
    return 0;
}

Java

// Java program to find smallest length 
// subarray that contains all elements 
// of another array.
import java.io.*;
 
class GFG {
 
// function return the minimum length 
// of sub_array
static int minimumSubArray(int A[], int n, 
                           int B[], int m)
{
    int result = Integer.MAX_VALUE;
 
    // Pick starting point
    for (int i = 0; i < n; i++) {
 
        // Pick ending point
        for (int j = i; j < n; j++) {
 
            // k is index in first array 
            // and 'index' is index in
            // second array.
            int k, index = 0; 
            for (k = i; k <= j; k++) {
                if (A[k] == B[index])
                    index++;
                if (index == m)
                    break;
            }
 
            // update minimum length sub_array
            if (index == m && result > k - i + 1)
            result = (k == n) ? k - i : k - i + 1;
        }
    }
 
    // return minimum length subarray
    return result;
}
 
// driver program to test above function
public static void main(String[] args)
{
    int A[] = { 5, 6, 5, 2, 7, 5, 
                6, 7, 5, 5, 7 };
    int B[] = { 5, 5, 7 };
    int n = A.length;
    int m = B.length;
    System.out.println(minimumSubArray(A, n, B, m));
}
}
 
// This code is contributed by Prerna Saini

Python3

# Python 3 program to find smallest 
# length subarray that contains all 
# elements of another array.
 
# function return the minimum length 
# of sub_array
def minimumSubArray(A, n, B, m) :
    result = 10000000
  
    # Pick starting point
    for i in range(0, n) :
         
        # Pick ending point
        for j in range(0,n) :
   
            # k is index in first array and
            # 'index' is index in second array.
            index = 0
            for k in range(i, j + 1) :
                if (A[k] == B[index]) :
                    index=index + 1
                if (index == m) :
                    break
                 
            # update minimum length sub_array
            if (index == m and result > k - i + 1) :
                if (k == n) :
                    result =  k - i 
                else :
                    result = k - i + 1
         
    # return minimum length subarray
    return result
     
# driver program to test above function
A = [ 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 ]
B = [ 5, 5, 7 ]
n = len(A)
m = len(B)
print(minimumSubArray(A, n, B, m))
 
 
#This code is contributed by Nikita Tiwari

C#

// C# program to find smallest length 
// subarray that contains all elements 
// of another array.
using System;
 
class GFG {
 
// function return the minimum 
// length of sub_array
static int minimumSubArray(int []A, int n, 
                           int []B, int m)
{
    int result = int.MaxValue;
 
    // Pick starting point
    for (int i = 0; i < n; i++) {
 
        // Pick ending point
        for (int j = i; j < n; j++) {
 
            // k is index in first array 
            // and 'index' is index in
            // second array.
            int k, index = 0; 
            for (k = i; k <= j; k++) {
                if (A[k] == B[index])
                    index++;
                if (index == m)
                    break;
            }
 
            // update minimum length sub_array
            if (index == m && result > k - i + 1)
            result = (k == n) ? k - i : k - i + 1;
        }
    }
 
    // return minimum length subarray
    return result;
}
 
  // Driver code
  public static void Main()
  {
    int []A = { 5, 6, 5, 2, 7, 5, 
                 6, 7, 5, 5, 7 };
    int []B = { 5, 5, 7 };
    int n = A.Length;
    int m = B.Length;
    Console.Write(minimumSubArray(A, n, B, m));
  }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find smallest length 
// subarray that contains all elements 
// of another array.
 
// function return the minimum
// length of sub_array
function minimumSubArray($A, $n, $B, $m)
{
     
    $result = PHP_INT_MAX;
 
    // Pick starting point
    for ($i = 0; $i < $n; $i++) 
    {
 
        // Pick ending point
        for ( $j = $i; $j < $n; $j++) 
        {
 
            // k is index in first array and
            // 'index' is index in second array.
            $k; $index = 0; 
            for ($k = $i; $k <= $j; $k++)
            {
                if ($A[$k] == $B[$index])
                    $index++;
                if ($index == $m)
                    break;
            }
 
            // update minimum length 
            // sub_array
            if ($index == $m && $result > $k - $i + 1)
            $result = ($k == $n) ? $k - $i : $k - $i + 1;
        }
    }
 
    // return minimum length subarray
    return $result;
}
 
    // Driver Code
    $A = array(5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7);
    $B = array(5, 5, 7);
    $n = count($A);
    $m = count($B);
    echo minimumSubArray($A, $n, $B, $m);
     
// This code is contributed by anuj_67
?>

Javascript

<script>
 
// Javascript program to find smallest length 
// subarray that contains all elements 
// of another array.
 
// function return the minimum length of sub_array
function minimumSubArray(A, n, B, m)
{
    var result = 1000000000;
 
    // Pick starting point
    for (var i = 0; i < n; i++) {
 
        // Pick ending point
        for (var j = i; j < n; j++) {
 
            // k is index in first array and
            // 'index' is index in second array.
            var k, index = 0; 
            for (k = i; k <= j; k++) {
                if (A[k] == B[index])
                    index++;
                if (index == m)
                    break;
            }
 
            // update minimum length sub_array
            if (index == m && result > k - i + 1)
              result = (k == n) ? k - i : k - i + 1;
        }
    }
 
    // return minimum length subarray
    return result;
}
 
// driver program to test above function
var A = [ 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 ];
var B = [ 5, 5, 7 ];
var n = A.length;
var m = B.length;
document.write( minimumSubArray(A, n, B, m));
 
// This code is contributed by noob2000.
</script>

Output:

Time Complexity : O(n³)
Auxiliary Space : O(1)

Method 2 (Efficient): Method 2 is an optimized version of method 1. Here we consider only those subarrays whose first element match with the first element of second array. If first element matches, then we match the rest of the elements of second array in the Main_array and if all elements match then we update length if need. In the end, we return minimum length of sub_array.

Below is the implementation of above idea:

C++

// C++ program to find smallest length 
// subarray that contains all elements 
// of another array.
#include <bits/stdc++.h>
using namespace std;
 
// Returns the minimum length of sub_array 
int minimumSubArray(int A[], int n, int B[], 
                                     int m)
{
    int result = INT_MAX;
 
    // Traverse main_array element
    for (int i = 0; i < n - m + 1; i++)
    {
        // Pick only those subarray of main_array 
        // whose first element match with the 
        // first element of second_array
        if (A[i] == B[0]) {
         
            // initialize starting of both
            // subarrays
            int j = 0, index = i;
            for (; index < n; index++) {
                if (A[index] == B[j])
                    j++;
 
                // if we found all elements of 
                // second array
                if (j == m)
                    break;
            }
 
            // update minimum length sub_array
            if (j == m && result > index - i + 1)
              result = (index == n) ? index - i : index - i + 1;
    }
}
 
    // return minimum length subarray
    return result;
}
 
// driver program to test above function
int main()
{
    int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
    int B[] = { 5, 5, 7 };
    int n = sizeof(A)/sizeof(A[0]);
    int m = sizeof(B)/sizeof(B[0]);
    cout << minimumSubArray(A, n, B, m);
    return 0;
}

Java

// Java program to find smallest length 
// subarray that contains all elements 
// of another array.
import java.io.*;
 
class GFG {
 
// Returns the minimum length of sub_array 
static int minimumSubArray(int A[], int n,
                           int B[], int m)
{
    int result = Integer.MAX_VALUE;
 
    // Traverse main_array element
    for (int i = 0; i < n - m + 1; i++)
    {
        // Pick only those subarray of
        // main_array whose first element
        // match with the first element 
        // of second_array
        if (A[i] == B[0]) {
         
            // initialize starting of 
            // both subarrays
            int j = 0, index = i;
            for (; index < n; index++) {
                if (A[index] == B[j])
                    j++;
 
                // if we found all elements 
                // of second array
                if (j == m)
                    break;
            }
 
            // update minimum length sub_array
            if (j == m && result > index - i + 1)
            result = (index == n) ? index - i :
                                 index - i + 1;
    }
 
    }
     
    // return minimum length subarray
    return result;
}
 
// driver program to test above function
public static void main(String[] args)
{
    int A[] = { 5, 6, 5, 2, 7, 5, 
                6, 7, 5, 5, 7 };
    int B[] = { 5, 5, 7 };
    int n = A.length;
    int m = B.length;
    System.out.println(minimumSubArray(A, n, 
                                     B, m));
}
}
 
// This code is contributed by Prerna Saini

Python3

# Python 3 program to find smallest length 
# subarray that contains all elements 
# of another array.
 
# Returns the minimum length of sub_array 
def minimumSubArray( A,n, B, m) :
    result = 1000000
  
    # Traverse main_array element
    for i in range(0, n - m + 1) :
 
        # Pick only those subarray of main_array 
        # whose first element match with the 
        # first element of second_array
        if (A[i] == B[0]) :
             
            # initialize starting of both
            # subarrays
            j = 0
            index = i
            for index in range(i, n) :
                if (A[index] == B[j]) :
                    j = j+1
  
                # if we found all elements 
                # of second array
                if (j == m) :
                    break
             
            # update minimum length sub_array
            if (j == m and result > index - i + 1) :
                if(index == n) :
                    result = index - i 
                else: 
                    result = index - i + 1
     
  
    # return minimum length subarray
    return result
     
# driver program to test above function
A = [ 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 ]
B = [ 5, 5, 7 ]
n = len(A)
m = len(B)
print(minimumSubArray(A, n, B, m))
 
 
# This code is contributed by Nikita Tiwari.

C#

// C# program to find smallest length 
// subarray that contains all elements 
// of another array.
using System;
 
class GFG {
 
// Returns the minimum length of sub_array 
static int minimumSubArray(int []A, int n,
                           int []B, int m)
{
    int result = int.MaxValue;
 
    // Traverse main_array element
    for (int i = 0; i < n - m + 1; i++)
    {
        // Pick only those subarray of
        // main_array whose first element
        // match with the first element 
        // of second_array
        if (A[i] == B[0]) {
         
            // initialize starting of 
            // both subarrays
            int j = 0, index = i;
            for (; index < n; index++)
            {
                if (A[index] == B[j])
                    j++;
 
                // if we found all elements 
                // of second array
                if (j == m)
                    break;
            }
 
            // update minimum length sub_array
            if (j == m && result > index - i + 1)
            result = (index == n) ? index - i :
                                index - i + 1;
    }
    }
     
    // return minimum length subarray
    return result;
}
 
  // Driver code
  public static void Main()
  {
    int []A = { 5, 6, 5, 2, 7, 5, 
                 6, 7, 5, 5, 7 };
    int []B = { 5, 5, 7 };
    int n = A.Length;
    int m = B.Length;
    Console.Write(minimumSubArray(A, n, B, m));
  }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find smallest length 
// subarray that contains all elements 
// of another array.
 
// Returns the minimum length of sub_array 
function minimumSubArray(&$A, $n, &$B, $m)
{
    $result = PHP_INT_MAX;
 
    // Traverse main_array element
    for ($i = 0; $i < $n - $m + 1; $i++)
    {
        // Pick only those subarray of main_array 
        // whose first element match with the 
        // first element of second_array
        if ($A[$i] == $B[0]) 
        {
         
            // initialize starting of both
            // subarrays
            $j = 0;
            $index = $i;
            for ($index = $i; $index < $n; $index++) 
            {
                if ($A[$index] == $B[$j])
                    $j++;
 
                // if we found all elements of 
                // second array
                if ($j == $m)
                    break;
            }
 
            // update minimum length sub_array
            if ($j == $m && $result > $index - $i + 1)
            $result = ($index == $n) ? 
                         $index - $i : 
                         $index - $i + 1;
        }
    }
 
    // return minimum length subarray
    return $result;
}
 
// Driver Code
$A = array(5, 6, 5, 2, 7, 5, 
              6, 7, 5, 5, 7 );
$B = array(5, 5, 7 );
$n = sizeof($A);
$m = sizeof($B);
echo(minimumSubArray($A, $n, $B, $m));
 
// This code is contributed 
// by Shivi_Aggarwal 
?>

Javascript

<script>
    // Javascript program to find smallest length
    // subarray that contains all elements
    // of another array.
     
    // Returns the minimum length of sub_array
    function minimumSubArray(A, n, B, m)
    {
        let result = Number.MAX_VALUE;
 
        // Traverse main_array element
        for (let i = 0; i < n - m + 1; i++)
        {
            // Pick only those subarray of
            // main_array whose first element
            // match with the first element
            // of second_array
            if (A[i] == B[0]) {
 
                // initialize starting of
                // both subarrays
                let j = 0, index = i;
                for (; index < n; index++)
                {
                    if (A[index] == B[j])
                        j++;
 
                    // if we found all elements
                    // of second array
                    if (j == m)
                        break;
                }
 
                // update minimum length sub_array
                if (j == m && result > index - i + 1)
                result = (index == n) ? index - i :
                                    index - i + 1;
        }
        }
 
        // return minimum length subarray
        return result;
    }
     
    let A = [ 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 ];
    let B = [ 5, 5, 7 ];
    let n = A.length;
    let m = B.length;
    document.write(minimumSubArray(A, n, B, m));
     
    // This code is contributed by divyesh072019.
</script>

Output:

Time Complexity : O(n*n)
Auxiliary Space : O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!