Created
August 12, 2017 00:58
-
-
Save sdpatil/7c942b2cfab28d29d6368f7c2175c26f to your computer and use it in GitHub Desktop.
Find the smallest subarray covering all values
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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