0

Given an array A, find a shortest subarray A[i : j ] such that each distinct value present in A is also present in the subarray.

The question is not for a homework. It's a practice problem from a chapter on Hash tables. I am not looking for the code. Just looking for the algorithm or hints.

Improve this question
6
  • not for a homework. It's a practice problem from a chapter Doesn't it sound like it's the very same thing? Commented Dec 21, 2014 at 10:44
  • @DerGolem Not really. One is imposed by someone else, the other is self-learning. The question is only looking for algorithm pointers rather than having the answer spoon fed, too. Commented Dec 21, 2014 at 10:46
  • See this question. If you do not know the distinct elements, you would have a O(n * log(n)) solution, otherwise it even is O(n) Commented Dec 21, 2014 at 10:47
  • It a self-imposed homework. Commented Dec 21, 2014 at 10:49
  • it's homework, it's not for assessment. the obvious answer is to use a hash table :) Commented Dec 21, 2014 at 11:14

2 Answers 2

Reset to default
1

1- Maintain a hash table element->count

2- Traverse array from begin to end, incrementing the element count. Whenever an element count is changed from 0 to 1, record it's index in a variable , say index_0_1. In the end index_0_1 will have end index of a potential ans.

3- Traverse array from begin to index_0_1, decrementing the element count. Stop, whenever an element count is changed from 1 to 0, record it's index in a variable, say index_1_0. subarray A[index_1_0 : index_0_1] is a potential ans, record it.

4- Traverse from index_0_1 towards end, incrementing the element count and stop whenever you find element A[index_1_0]. Update index_0_1 with current index.

5- Traverse from index_1_0+1 to index_0_1, decrementing the element count. Stop whenever an element count is changed from 1 to 0. This is new index_1_0. If subarray A[index_1_0: index_0_1] is smaller than previous ans, update it and continue with steps 4 and step 5, until whole array have been traversed.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Use a hash table to maintain a count of each type of element in the string.

when you find a new type of element discard all previous answers and start trimming the start of the substring, when you can trim it no more without having zero of one type of element remember the substring if it's the shortest yet found and then start looking for another element to replace the one you are about to loose or to find a new element not previously seen as above.

When you hit the end of the string you are done.

If your hash is any good, this should be O(n)

Improve this answer

2 Comments

Suppose I have the series of elements as aaabbbccccaaabc so we have two windows, one is the A[2:6] and A[12:14]. When we scan past the first 2:6, although we do not know that all are done, but we can not discard the newer a's or b's. Since it could have been cba at the end. Will this method work for such cases? More doubts.. If we hit a new element, we discard the previous answers, did not get that. The newer element will be any way added into the Hashed set.
The window counts up and down keeping a tally of the total number of each letter in the window. separately a record of the coordinates of shortest complete window yet found. why to discard: if we find a 'd' at position 15 any the answers that had only {a,b,c} is worthless, but we can tack the d onto the end of the most recent complete window found howevewe 12:16 has the full set,

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.