Problem:
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
Solution:
public boolean linearIn(int[] outer, int[] inner) {
int numFound = 0;
if(inner.length == 0) {
return true;
}
int k = 0;
for(int i = 0; i < outer.length; i++) {
if(outer[i] == inner[k]) {
numFound++;
k++;
} else if(outer[i] > inner[k]) {
return false;
}
if(numFound == inner.length)
return true;
}
return false;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteint count = 0;
for (int i = 0; i < inner.length; i++) {
for (int j = 0; j < outer.length; j++) {
if (inner[i] == outer[j]) {
count++;
break;
}
}
}
if (count == (inner.length)) return true;
return false;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteint j=0;
for(int i=0;i<outer.length&&j<inner.length;i++)
if(outer[i]==inner[j])j++;
return j==inner.length;
}
cleaver and nice)
DeleteWe are not worthy
DeleteNice!
Deletethis does not return a boolean.
DeleteKV , it does .. Look at the "==" sign.This Syntax means its comparing and output from that always returns boolean.Good Luck.
DeleteA better approach which takes the complexity down to the liner time:
ReplyDeletepublic boolean linearIn(int[] outer, int[] inner) {
int i=0, j=0; int count =0;
while(jinner[j]){
j++;
}
else i++;
}
if(count==inner.length){
return true;
}
return false;
}
oops. used "=" not "==". yeah, elegant
Deletepublic boolean checkVal(int num, int array[ ]){
ReplyDeletefor(int i = 0; i < array.length; i++){
if(array[i] == num){return true;}
}
return false;
}
public boolean linearIn(int[] outer, int[] inner) {
int count = 0;
for(int i = 0; i < inner.length; i++){
if(checkVal(inner[i], outer)){count++;}
}
if(count == inner.length){return true;}
return false;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteint currIn = 0;
if(inner.length == 0)
return true;
for(int i = 0; i < outer.length; i++) {
if(outer[i] == inner[currIn])
currIn++;
if(currIn == inner.length)
return true;
}
return false;
}
1 For loop, 2 If comparisons, 3 variables!
ReplyDeletepublic boolean linearIn(int[] outer, int[] inner) {
int innerlength=inner.length;
int samecount=0;
int j=0;
for(int i=0; i<outer.length && j<innerlength;i++){
if( outer[i] == inner[j] ){
samecount++;
j++;
}
}
if(samecount==inner.length) return true;
return false;
}
catypus
Very Very easy approach---
ReplyDeletepublic boolean linearIn(int[] outer, int[] inner) {
int i=0;
int j=0;
int count=0;
while(i<outer.length && j<inner.length){
if(outer[i]==inner[j]) {
count++;
i++;
j++;
}
else i++;
}
return count==inner.length;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteint pos =0, val = inner.length;
boolean flag = val == 0 ? true : false;
for (int i = 0; i < outer.length && pos < inner.length; i++)
if (outer[i] == inner[pos] ){
flag = true;
pos++;
if (pos < inner.length)
flag = false;
}
return flag;
}
boolean controlValue = false;
ReplyDeletefor (int i = 0; i < inner.length; i++) {
controlValue = false;
for (int j = 0; j < outer.length; j++) {
if (inner[i] == outer[j]) {
controlValue = true;
}
if (j == outer.length - 1 && controlValue == false) {
return false;
}
}
}
return true;
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteboolean match = false;
for(int i=0;i<inner.length;i++){
for(int o=0;o<outer.length;o++){
if(inner[i]==outer[o]){
match = true;
}
}
if(match){
match = false;
} else return false;
}
return true;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteif(inner.length == 0){
return true;
}
int j = 0;
for(int i = 0; i < outer.length; i++) {
if(inner[j] == outer[i]) {
j++;
if(j>=inner.length) {
return true;
}
}
if(outer[i] > inner[j]) {
return false;
}
}
return false;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteif (inner.length == 0) return true;
for(int i = 0; i < inner.length; i++) {
boolean found = false;
for (int j = i; j < outer.length; j++) {
if (outer[j] == inner[i]) found = true;
}
if (!(found)) break;
if (found && i == inner.length - 1) return true;
}
return false;
}
Arrays.sort(outer);
ReplyDeletefor(int i = 0;i<inner.length;i++)
{
if(Arrays.binarySearch(outer,inner[i])<0)return false;
}
return true;
}
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteif (inner.length == 0)
{
return true;
}
int pos = 0;
int count = 0;
for (int i = 0; i < outer.length; i++)
{
if (outer[i] == inner[pos])
{
pos++;
count++;
}
if (count == inner.length)
{
return true;
}
else if (outer[i] > inner[pos])
{
return false;
}
}
return false;
}
def linearIn(out, inn):
ReplyDeleteb = True
for i in range(len(inn)):
if inn[i] not in out:
b = False
return b
With Java Stream and Collections
ReplyDeletepublic boolean linearIn(int[] outer, int[] inner) {
List numbers1 = Arrays.stream(outer).boxed().collect(Collectors.toList());
List numbers2 = Arrays.stream(inner).boxed().collect(Collectors.toList());
return numbers1.containsAll(numbers2);
}
for(int i = 0; i<inner.length; i++) {
ReplyDeleteboolean b = false;
for(int j=0; j<outer.length; j++) {
if(inner[i] == outer[j]) b = true;
}
if(b == false) return false;
}
return true;
public boolean linearIn(int[] outer, int[] inner) {
ReplyDeleteboolean result=false;
if(inner.length==0)return true;
for(int i=0;i<inner.length;i++){
for(int j=0;j<outer.length;j++){
if(inner[i]==outer[j]){
result=true;
break;
}else{
result=false;
}
}
if(!result){
return false;
}
}
return result;
}