# “Does an array contain the same elements as another array?”

Posted on

Problem

Write a static method named contains that accepts two arrays of
integers a1 and a2 as parameters and that returns a boolean value
indicating whether or not a2’s sequence of elements appears in a1
(true for yes, false for no). The sequence of elements in a2 may
appear anywhere in a1 but must appear consecutively and in the same
order. For example, if variables called list1 and list2 store the
following values:

int[] list1 = {1, 6, 2, 1, 4, 1, 2, 1, 8}; int[] list2 = {1, 2, 1};

Then the call of contains(list1, list2) should return true because
list2’s sequence of values {1, 2, 1} is contained in list1 starting at
index 5. If list2 had stored the values {2, 1, 2}, the call of
contains(list1, list2) would return false because list1 does not
contain that sequence of values. Any two lists with identical elements
are considered to contain each other, so a call such as
contains(list1, list1) should return true.

You may assume that both arrays passed to your method will have
lengths of at least 1. You may not use any Strings to help you solve
this problem, nor methods that produce Strings such as
Arrays.toString.

I’m looking for general feedback to improve my future code. I’m intent on learning Java, so any style tips would be well appreciated. Other ways to accomplish this task?

public static boolean contains(int[] list1, int[] list2) {
for (int i = 0; i <= (list1.length - list2.length); i++) {
if (list1[i] == list2[0]) {
for (int j = 1; j < list2.length; j++) {
if (list1[i + j] == list2[j]) {
if (j == (list2.length - 1)) {
return true;
}
} else {
break;
}
}
}
}
return false;
}

Solution

if (list1[i] == list2[0]) {
for (int j = 1; j < list2.length; j++) {
if (list1[i + j] == list2[j]) {

We can drop this from three lines to one.

for (int j = 0; j < list2.length && list1[i + j] == list2[j]; j++) {

A side benefit is that this handles the case where list2 is empty (zero length). The original code would crash in that case.

At the expense of an extra comparison (which could be compiled out), we get rid of two levels of indent and

} else {
break;

Because this will leave the loop automatically. It won’t be necessary to break out manually.

It might be better to replace

if (list1[i] == list2[0]) {
for (int j = 1; j < list2.length; j++) {
if (list1[i + j] == list2[j]) {
if (j == (list2.length - 1)) {
return true;
}
} else {
break;
}
}
}

with

int j = 0;
while (j < list2.length && list1[i + j] == list2[j]) {
j++;
}

if (j == list2.length) {
return true;
}

Moving the scope of j outside the inner loop allows us to move the test out of the loop as well. So rather than testing on every iteration, we can test just once.

Alternately

for (int j = 0; list1[i + j] == list2[j]; j++) {
if (j + 1 >= list2.length) {
return true;
}
}

Does the same thing as the original code. It may not be obvious, but this does the same thing with fewer comparisons.

But we’re back to throwing an exception if list2 is zero length. This does exactly the same thing as the original code with fewer comparisons and less code.