Find subarray of an array coding

Q. Can you write code to find starting position of a sub array in an array? if not found, return -1 as the position.

For example, find

• [-3, 7] in [5, 9, -3, 7, 8] --> 2
• [7, 8, 9] in   [5, 9, -3, 7, 8] --> -1
• [5] in   [5, 9, -3, 7, 8] --> 0

A. This can be approached a number of different ways. I will discuss 3 approaches.

Define the interface first

 
package findarray;

public interface FindArray {
    abstract int findArray(int[] array, int[] subArray) ;
}

Approach 1: Make use of the Collections.indexOfSubList method as per dont reinvent the wheel principle.

 
package findarray;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FindArrayImpl1 implements FindArray
{
    
    @Override
    public int findArray(int[] array, int[] subArray)
    {
        if (array == null || subArray == null || subArray.length > array.length)
        {
            return -1;
        }
        
        //convert primitive int to Integer and then use the Collections API 
        return Collections.indexOfSubList(convertArrayToList(array), convertArrayToList(subArray));
    }
    
    /**
     * convert int[] to List<Integer>
     */
    public List<Integer> convertArrayToList(int[] input)
    {
        if (input == null)
        {
            return null;
        }
        List<Integer> output = new ArrayList<Integer>(input.length);
        for (int i = 0; i < input.length; i++)
        {
            output.add(Integer.valueOf(input[i]));
        }
        
        return output;
        
    }
    
    public static void main(String[] args)
    {
        int[] array =
        {
            5, 9, -3, 7, 8
        };
        
        int[] subArray1 =
        {
            -3, 7
        };
        
        //should return 2
        System.out.println(new FindArrayImpl1().findArray(array, subArray1));
        
        int[] subArray2 =
        {
            7, 8, 9
        };
        
        //should return -1
        System.out.println(new FindArrayImpl1().findArray(array, subArray2));
        
        int[] subArray3 =
        {
            5
        };
        
        //should return 0
        System.out.println(new FindArrayImpl1().findArray(array, subArray3));
        
    }
}

Approach 2: Write your own logic. The interviewer might be wanting to test your logic processing ability.

 
package findarray;

public class FindArrayImpl2 implements FindArray
{
    
    @Override
    public int findArray(int[] array, int[] subArray)
    {
        if (array == null || subArray == null || subArray.length > array.length)
        {
            return -1;
        }
        
        int index = -1; // assume not found
        
        for (int i = 0; i < array.length; i++)
        {
            // Check if the next element of array is same as the first element of subarray
            if (array[i] == subArray[0])
            {
                //check subsequent elements of subarray against the subsequent elements of array
                for (int j = 0; j < subArray.length; j++)
                {
                    //if found, set the index
                    if (i + j < array.length && subArray[j] == array[i + j])
                    {
                        index = i;
                    }
                    else
                    {
                        index = -1;
                        break;
                    }
                }
            }
        }
        
        return index;
        
    }
    
    public static void main(String[] args)
    {
        int[] array =
        {
            5, 9, -3, 7, 8
        };
        
        int[] subArray1 =
        {
            -3, 7
        };
        
        //should return 2
        System.out.println(new FindArrayImpl2().findArray(array, subArray1));
        
        int[] subArray2 =
        {
            7, 8, 9
        };
        
        //should return -1
        System.out.println(new FindArrayImpl2().findArray(array, subArray2));
        
        int[] subArray3 =
        {
            5
        };
        
        //should return 0
        System.out.println(new FindArrayImpl2().findArray(array, subArray3));
        
    }  
}

Approach 3: Using the StringBuilder class.

 
package findarray;

public class FindArrayImpl3 implements FindArray
{
    
    @Override
    public int findArray(int[] array, int[] subArray)
    {
        if (array == null || subArray == null || subArray.length > array.length)
        {
            return -1;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++)
        {
            sb.append(array[i]);
        }
        
        StringBuilder sbSub = new StringBuilder();
        for (int i = 0; i < subArray.length; i++)
        {
            sbSub.append(subArray[i]);
        }
        
        int index = sb.toString().indexOf(sbSub.toString());
        if (index >= 0)
        {
            return index;
        }
        else
        {
            return -1;
        }
    }
    
    public static void main(String[] args)
    {
        int[] array =
        {
            5, 9, -3, 7, 8
        };
        
        int[] subArray1 =
        {
            -3, 7
        };
        
        //should return 2
        System.out.println(new FindArrayImpl3().findArray(array, subArray1));
        
        int[] subArray2 =
        {
            7, 8, 9
        };
        
        //should return -1
        System.out.println(new FindArrayImpl3().findArray(array, subArray2));
        
        int[] subArray3 =
        {
            5
        };
        
        //should return 0
        System.out.println(new FindArrayImpl3().findArray(array, subArray3));
        
    }
}

The output for all 3 approaches:

 
2
-1
0

Feel free to show us other creative and better approaches.

Related Posts by Categories