How to see if an array contains another?

Question

Problem: Check to see if the array arr2 is contained within the arr1 in the same order. The arr2 could be contained anywhere with in arr1.

Examples:

contains({"1", "2", "3"}, {"1", "2"}) → true
contains({"1", "2", "3"}, {"2", "3"}) → true
contains({"1", "2", "3"}, {"2", "1"}) → false

My code works in all cases except when arr2 is shorter than arr1 and arr2 does not start on position 0 of arr1.

Here is my code:

public boolean contains(String[] arr1, String[] arr2){
if (arr2.length>arr1.length)
{
 return false;
}
int x=0;
if(arr2.length==arr1.length)
{
 for (int i=0; i<arr1.length; i++)
 {
 if(arr1[i]==arr2[i])
 {
 x++;
 }
 }
 if(x==arr1.length)
 {
 return true;
 }
 return false;
}
int y=0;
if(arr2.length<arr1.length)
{
 for(int i=0; i<arr2.length; i++)
 {
 if(arr1[i]==arr2[i])
 {
 y++;
 }
 }
}
if(y==arr2.length)
{
 return true;
}
 return false;
}

I would rather have hints instead of the answer itself. Thank you so much!

• Jared Rummler: Not related to the question but, when comparing strings in Java don't use ==, use arr1[i].equals(arr2[i])
• Dawood ibn Kareem: Hint - I think you should be comparing arr1[i] with arr2[y], not arr2[i]. Also, make i go up to arr1.length, not arr2.length.
• Dawood ibn Kareem: @JaredRummler - that IS related to the question, and it's important here.

Answer 1

Here is your code modified to the right solution. You could do it better of course.

public boolean contains(String[] arr1, String[] arr2){
if (arr2.length>arr1.length)
{
 return false;
}
if(arr2.length==arr1.length)
{
 for (int i=0; i<arr1.length; i++)
 {
 if(!arr1[i].equals(arr2[i]))
 {
 retrun false;
 }
 }
return true;
}
int y =0; 
if(arr2.length<arr1.length)
{
 for(int i=0; i<=(arr1.length-arr2.length); i++)
 {
 for(int j=0; j<arr2.length;j++){
 if(arr1[i+j].equals(arr2[j])){
 y++;
 }
 }
 if(y == arr2.length){
 return true;
 }else {
 y = 0;
 }
 }
 return false;
}

Answer 2

You wanted hints only, so here is one:

In your if(arr2.length<arr1.length) statement, you are only looping to compare arr1[i] with arr2[i]. As you said yourself, this is only comparing whether arr2 matches the start of arr1.

To test for a case where arr2 starts at a later position, you would have to do a comparison between arr1[i+j] and arr2[i] for different j, i.e. you need another for loop here over possible "shifts" j between the array starting points, with your for i loop nested inside the for j loop. Make sure to reset your y to zero in the correct place.

• Dawood ibn Kareem: Another loop isn't really necessary. So long as you have one index that represents your position in a1 and another that represents your position in a2, you only need a single loop.
• Emma Middleton: for(int i=0, j=0; i<arr2.length; i++, j++) { if(arr1[i+j].equals(arr2[i])) { y++; }
• Emma Middleton: I added this to the loop, but it still doesn't work.
• Jonas Heidelberg: @Emma, what you are doing looks like one loop to me which counts up i and j at the same time. I was recommending two nested loops (the one with i which you show in your question, nested inside a loop over j).
• Jonas Heidelberg: Exactly, a nested for loop.

Answer 3

I would recommend looking at String#contains method implementation (specifically at String#indexOf static method). Algorithm looks very similar to your problem.

Answer 4

When reading your solution, i see there are 3 parts.

Part 1: if array 2 is smaller than array 1, then array 2 can not be a sub array of array 1

Part 2: compare each element of 2 array when they have the same size. Array 2 is sub array of Array 1 if all elements are the same

Part 3: compare each element of 2 array when array 2 size is smaller than array 1 size. There is an issue in part 2 and part 3. They have the same logic. Part 3 works fine if 2 array have the same size. In fact, if two arrays have the same size, part 2 would have taken care of this scenario. So step 2 and 3 are basically the same thing

I would revise part 3 as follow:

Part 3 (new): if array 2 is smaller than array 1, and array 2 is contained within array 1, then array 1 should have a sub array, in which each element of that sub array is equaled to each element in array 2

step 1: compare each element of array 2 to the sub array of array 1.

step 2: if all elements are equals, then array 2 is contained in array 1. if any of elements are not equal, repeat step 1 for the next sub array of array 1.

Note: if you are familiar with recursion, the solution will be neater. Every time we repeat step 1, we are solving the same problem as part of the general solution.

Below is the recursive solution. This solution does not take into account null and empty array.

<!DOCTYPE html>
<html>
<body>
<p>This example calls a function which performs a calculation, and returns the result:</p>
<p id="demo"></p>
<script>
function findSubArray(bigArray, smallArray, startIndexOfSubArray)
{ 
 if((bigArray.length - startIndexOfSubArray) < smallArray.length)
 return false;
 for(index = 0; index < smallArray.length; index++)
 {
 if(bigArray[startIndexOfSubArray + index] != smallArray[index]){
 return findSubArray(bigArray,
 smallArray,
 startIndexOfSubArray = startIndexOfSubArray + 1); 
 } 
 }
 return true;
}
var bigArray = [1,3,3,4,5,6];
var smallArray = [4,5,7];
var isSubArray = findSubArray(bigArray, smallArray, 0);
document.getElementById("demo").innerHTML = isSubArray.toString();
</script>
</body>
</html>