Find the smallest window within an array that contains all the elements of another array

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array1 = { 6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5 };
            int[] array2 = { 1, 3, 5 };
            for (int i = 0; i < array1.Length; i++)
            {
                Console.Write(array1[i] + " ");
            }
            Console.WriteLine();
            for (int i = 0; i < array2.Length; i++)
            {
                Console.Write(array2[i] + " ");
            }
            Console.WriteLine();
            int length = 0;
            int index = StartingIndex(array1, array2, out length);
            if(index != -1)
            {
                Console.WriteLine("Starting Index = " + index);
                Console.WriteLine("Window Length = " + length);
            }
            else
            {
                Console.WriteLine("Second array doesn't exist in the first");
            }
        }
        public static int StartingIndex(int[] arr1, int[] arr2, out int length)
        {
            length = 0;
            //Window Length
            for(int i = arr2.Length; i <= arr1.Length; i++)
            {
                //Starting Position
                for(int j = 0; j <= arr1.Length - i; j++)
                {
                    //Extract the elements and store into an array list
                    ArrayList al = new ArrayList();
                    for(int k = j; k < j + i; k++)
                    {
                        al.Add(arr1[k]);
                    }
                    //Check for the coverage
                    if(IsSubset(al, arr2))
                    {
                        length = i;
                        return j;
                    }
                    al.Clear();
                }
            }
            return -1;
        }
        public static bool IsSubset(ArrayList al, int[] arr)
        {
            for(int i = 0; i < arr.Length; i++)
            {
                int flag = 0;
                for (int j = 0; j < al.Count; j++)
                {
                    if(arr[i] == (int)al[j])
                    {
                        flag = 1;
                        al.RemoveAt(j);
                        break;
                    }
                }
                if(flag == 0)
                {
                    return false;
                }
            }
            return true;
        }
    }
}

Output
=======
6 7 1 3 2 4 5 2 3 1 2 5
1 3 5
Starting Index = 6
Window Length = 4
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s