Skip to content

Instantly share code, notes, and snippets.

@sdpatil
Created August 12, 2017 00:58
Show Gist options
  • Select an option

  • Save sdpatil/7c942b2cfab28d29d6368f7c2175c26f to your computer and use it in GitHub Desktop.

Select an option

Save sdpatil/7c942b2cfab28d29d6368f7c2175c26f to your computer and use it in GitHub Desktop.
Find the smallest subarray covering all values
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Problem: Write a program that takes two arrays of strings and returns the indices of the starting and ending index of
* a shortest subarray of the first array that sequentially covers all the values in second array
*/
public class FindSmallestSubarraySequential {
public static class Subarray {
public Integer start;
public Integer end;
public Subarray(Integer start, Integer end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "Subarray{" +
"start=" + start +
", end=" + end +
'}';
}
}
public Subarray findSmallestSequentiallyCoveringSubset(List<String> paragraph, List<String> keywords) {
Map<String, Integer> keywordToIndx = new HashMap<>();
List<Integer> latestOccurance = new ArrayList<>(keywords.size());
List<Integer> shortestSubarrayLength = new ArrayList<>(keywords.size());
for (int i = 0; i < keywords.size(); i++) {
latestOccurance.add(-1);
shortestSubarrayLength.add(Integer.MAX_VALUE);
keywordToIndx.put(keywords.get(i), i);
}
Subarray result = new Subarray(-1, -1);
int shortestDistance = Integer.MAX_VALUE;
for (int i = 0; i < paragraph.size(); i++) {
Integer keywordIdx = keywordToIndx.get(paragraph.get(i));
if (keywordIdx != null) {
if (keywordIdx == 0) {
shortestSubarrayLength.set(0, 1);
} else if (shortestSubarrayLength.get(keywordIdx - 1) != Integer.MAX_VALUE) {
int distanceToPreviousKeywords = i - latestOccurance.get(keywordIdx - 1);
shortestSubarrayLength.set(
keywordIdx, distanceToPreviousKeywords + shortestSubarrayLength.get(keywordIdx - 1)
);
}
latestOccurance.set(keywordIdx, i);
if (keywordIdx == keywords.size() - 1 &&
shortestSubarrayLength.get(shortestSubarrayLength.size() - 1) < shortestDistance) {
shortestDistance = shortestSubarrayLength.get(shortestSubarrayLength.size() - 1);
result.start = i - shortestSubarrayLength.get(shortestSubarrayLength.size() - 1) + 1;
result.end = i;
}
}
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment