Variant 13.9.2 : Given an array A, rearrange the elements so that the shortest subarray containing all the distinct values in A has maximum possible length

#1

Does anyone know how to go about solving this problem? Thanks.

0 Likes

#2

The key idea (or hint) is thinking about partition. After partition, you will get a rearranged array where elements with identical values are group together. Then, you might think about how to make this with maximum possible length.

1 Like

#3

Thanks! After this step, my idea is to get the element with the least duplicates and move it as well is its duplicates to one end of the array. Then do the same for the element with the second least number of duplicates and move them to the other end of the array. Is there a better way to go about it? Thanks again!

0 Likes

#4

I think you got the answer :stuck_out_tongue:

0 Likes

#5

@twedkghksf Could you please help me understand your approach for this example:

(Consider the String as an array of characters)

A = “abcbadcaeaabe”

For this, the frequency map is:
a -> 5
b -> 3
c -> 2
d -> 1
e -> 2

So following your approach, we would place d at the end, then e and so on…
Resulting in aaaaabbbcceed, in which the shortest subarray containing all distinct values is: abbbcceed ( length = 9)

But if we arranged the array as: dccaaaaabbbee, the shortest subarray containing all distinct characters is the entire array except the last element, which is dccaaaaabbbe (length = 12) and longer than previous one.

Am I doing something wrong here ?

0 Likes

#6

The approach that was suggested is to put the least frequent item (and its duplicates) in one end, and the next less frequent item on the other end and so on. So using your example it is going to be: deeaaaaabbcc which has a max window length of 11.

0 Likes