We help IT Professionals succeed at work.

# linearIn  challenge

on
Hi,

I am working on below challenge

Array-3 > linearIn
prev  |  next  |  chance
Given two arrays of ints sorted in increasing order, outer and inner, return true if all of the numbers in inner appear in outer. The best solution makes only a single "linear" pass of both arrays, taking advantage of the fact that both arrays are already in sorted order.

linearIn([1, 2, 4, 6], [2, 4]) → true
linearIn([1, 2, 4, 6], [2, 3, 4]) → false
linearIn([1, 2, 4, 4, 6], [2, 4]) → true

how to verify one array has one other target array or not? is there is built in method for that?
Comment
Watch Question

## View Solutions Only

Most Valuable Expert 2016

Commented:
The arrays are sorted - you just go over them and compare the numbers.

Commented:
i will try. so two for loops needed right for each array?
Most Valuable Expert 2016

Commented:
Yes

Commented:

Commented:
psedo code

1. convert inner array to list
2. convert outer array to list
3. check whether outer contains inner list.
4. if yes return true
5.if false return false

``````public boolean linearIn(int[] outer, int[] inner) {
List o=Arrays.asList(outer);
List i=Arrays.asList(inner);
if(o.contains(i)){
return true;
}
else return false;
}
``````

Expected      Run
linearIn([1, 2, 4, 6], [2, 4]) → true      false      X
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      false      X
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      false      X
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      false      X
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      false      X
linearIn([1, 2, 3], [2]) → true      false      X
linearIn([1, 2, 3], [-1]) → false      false      OK
linearIn([1, 2, 3], []) → true      false      X
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      false      X
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK
other tests
X
Your progress graph for this problem

Commented:
``````import java.util.Arrays;
import java.util.List;

public class LinearIn {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] outer = { 1, 2, 4, 6 };
int[] inner = { 2, 4 };
System.out.println("is-->" + linearIn(outer, inner));
}

public static boolean linearIn(int[] outer, int[] inner) {
List o = Arrays.asList(outer);
List i = Arrays.asList(inner);
if (o.containsAll(i)) {
return true;
} else
return false;
}

}
``````
is-->false

changed contains to containsAll still getting false instead of true
Most Valuable Expert 2016
Commented:
I would just start with the shortest array and try to find values in the longest array, increase indexes as needed. When you reach the end you have either true or false.

Commented:
``````public boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
else if(outer[i]>inner[x]){
return false;
}
else if(outer[i]< inner[x]){
return false;
}
if(match==inner.length){
return true;
}

}
return false;
}
``````
Expected      Run
linearIn([1, 2, 4, 6], [2, 4]) → true      false      X
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      false      X
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      false      X
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      true      OK
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      false      X
linearIn([1, 2, 3], [2]) → true      false      X
linearIn([1, 2, 3], [-1]) → false      false      OK
linearIn([1, 2, 3], []) → true      true      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      false      X
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK
other tests
X

``````package com.upcast;

public class LinearIn {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] outer={1,2,4,6};
int[] inner={2,4};
System.out.println("linearIn is===>"+linearIn(outer,inner));

}
public static boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
else if(outer[i]>inner[x]){
return false;
}
else if(outer[i]< inner[x]){
return false;
}
if(match==inner.length){
return true;
}

}
return false;
}

}
``````
linearIn is===>false
student

Commented:
You should take Gerwin Jansen advice in his last comment above here.
Also debug statements would help here too.

Commented:
``````public boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
else if(outer[i]>inner[x]){
return false;
}
/* else if(outer[i]< inner[x]){
return false;
}*/
if(match==inner.length){
return true;
}

}
return false;
}
``````

Expected      Run
linearIn([1, 2, 4, 6], [2, 4]) → true      true      OK
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      true      OK
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      true      OK
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      true      OK
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      true      OK
linearIn([1, 2, 3], [2]) → true      true      OK
linearIn([1, 2, 3], [-1]) → false      false      OK
linearIn([1, 2, 3], []) → true      true      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      true      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK
other tests
OK
``````package com.upcast;

public class LinearIn {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] outer={1,2,4,6};
int[] inner={2,4};
System.out.println("linearIn is===>"+linearIn(outer,inner));

}
public static boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
else if(outer[i]>inner[x]){
return false;
}
/* else if(outer[i]< inner[x]){
return false;
}*/
if(match==inner.length){
return true;
}

}
return false;
}

}
``````
``````linearIn is===>true
``````
when i comment last else if it passes all tests.

Not clear how and why?
student

Commented:
Not clear how and why?
What was the purpose of
``````29:			/* else if(outer[i]< inner[x]){
30:				 return false;
31:			 }*/
``````
Please tell us what you were thinking when you wrote that .
Anyway, your code looks good.  Here is mine.
``````public boolean linearIn(int[] outer, int[] inner) {
boolean found = false;
int j = 0;
for(int i = 0; i < inner.length; i++){
for(int k = j; k < outer.length; k++){
if(inner[i] == outer[k]){
j = k;
found = true;
break;
}
}
if(!found)return false;
found = false;
}
return true;
}
``````
I don't know which is better.

Commented:
i was thinking there are 3 cases always right when comparing
1. equals
2. greater
3. less than
student

Commented:
We search for when values match.
Why do you care if the values are greater or less than?

Commented:
``````public boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
/*else if(outer[i]>inner[x]){
return false;
}*/
/* else if(outer[i]< inner[x]){
return false;
}*/
if(match==inner.length){
return true;
}

}
return false;
}
``````

actually i could comment other else if still fine as i need to worry only about == case

``````public boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
/*else if(outer[i]>inner[x]){
return false;
}*/
/* else if(outer[i]< inner[x]){
return false;
}*/
if(match==inner.length){
return true;
}

}
return false;
}
``````
Expected      Run
linearIn([1, 2, 4, 6], [2, 4]) → true      true      OK
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      true      OK
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      true      OK
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      true      OK
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      true      OK
linearIn([1, 2, 3], [2]) → true      true      OK
linearIn([1, 2, 3], [-1]) → false      false      OK
linearIn([1, 2, 3], []) → true      true      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      true      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK
other tests
OK
``````package com.upcast;

public class LinearIn {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] outer={1,2,4,6};
int[] inner={2,4};
System.out.println("linearIn is===>"+linearIn(outer,inner));

}
public static boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
/* else if(outer[i]>inner[x]){
return false;
}*/
/* else if(outer[i]< inner[x]){
return false;
}*/
if(match==inner.length){
return true;
}

}
return false;
}

}
``````

linearIn is===>true

above also passes all tests

Commented:
``````package com.upcast;

public class LinearIn {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] outer={1,2,4,6};
int[] inner={2,4};
System.out.println("linearIn is===>"+linearIn(outer,inner));

}
public static boolean linearIn(int[] outer, int[] inner) {
int match=0;
int x=0;
if(inner.length==0){
return true;
}

for (int i = 0; i < outer.length; i++) {

if(outer[i]==inner[x]){
match++;
x++;
}
/* else if(outer[i]>inner[x]){
return false;
}*/
else if(outer[i]< inner[x]){
return false;
}
if(match==inner.length){
return true;
}

}
return false;
}

}
``````

if i keep less than else if while debugging it is going to that loop wrongly. not sure why?
ElseIf.png

Commented:
We search for when values match.
Why do you care if the values are greater or less than?

true.

i will close this

Commented:
one other thing

``````public boolean linearIn(int[] outer, int[] inner) {
List o=Arrays.asList(outer);
List i=Arrays.asList(inner);
if(o.contains(i)){
return true;
}
else return false;
}
``````

why above wont work? how tweak to make above collection list approach work?
student

Commented:
above collection list approach work?

I don't think it will work for all cases.  For instance , this case from codingBat tests
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true
the values of the second array are spread out. Where a List would require them to be sequential (next to each other).
I don't know why it didn't work for the easier cases(where the elements were sequential ).

Commented:
so instead of list use some other collection object which can work with spread out elements?
student

Commented:
Yes, theoretically  your idea should work with Sets.  If I find time, I will try to find a solution.

Commented:
``````package com.upcast;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LinearIn {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] outer={1,2,4,6};
int[] inner={2,3,4};
System.out.println("linearIn is===>"+linearIn(outer,inner));

}
public static boolean linearIn(int[] outer, int[] inner) {

//public boolean linearIn(int[] outer, int[] inner) {
// List o=Arrays.asList(outer);
//   List i=Arrays.asList(inner);
Set<Integer> set1 = new HashSet<Integer>(Arrays.asList(outer));
Set<Integer> set2 = new HashSet<Integer>(Arrays.asList(inner));
if(set1.contains(set2)){
return true;
}
else return false;
//}
}

}
``````

above gives compilation error at line 21 and 22
says

The constructor HashSet<Integer>(Arrays.asList(outer)) is undefined
student

Commented:
I tried to find a solution using List or Set. But, I couldn't do it.
student
Commented:
I finally found a solution.
``````public boolean linearIn(int[] outer, int[] inner) {
Set<Integer> outerSet = new HashSet<Integer>();
Set<Integer> innerSet = new HashSet<Integer>();
for(int i = 0; i < outer.length; i++){