1
$\begingroup$

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.

Any subarray array[start, end] with 0 <= start <= end < n will have a unique element. The algorithm will return :

  • True for array = [1, 3, 5, 3, 1]

  • False for array = [1, 3, 5, 3, 5] because the sequence [3, 5, 3, 5] does not contain any unique element.



My idea (that does not seem to work in the competition) is to use divide and conquer as following :

  • Create the following hash map : hash map[element] = [list of the index of the element in the array]
  • Considering a recursive function that use start and end as array bounds
  • Then iterating though the keys, and as soon as it finds, using the hash map, an element that is unique (only one index is in the range [start; end]), the index will be used as a pivot
  • Recursively calling the function on array[start;pivot-1] and array[pivot+1; end]

As a subsequence can be the whole array, the array must contain one unique element. Then if each side of the pivot respect the condition, any subarray that contains the pivot obviously contain a unique element.

I simply want to know the my reasoning is valid. If yes, it means the problem comes from my code. Any thoughts ?

$\endgroup$

1 Answer 1

1
$\begingroup$

Pivot is unique in the whole array, therefore every sub array containing pivot contains a unique item. Subarrays not containing pivot are the subarrays of the array from start to pivot-1 and the subarrays of the array from pivot+1 to end.

In case you have more than one unique item, say at pivot1, pivot2 and pivot3, you would examine start to pivot1-1, pivot1+1 to pivot2-1 and so on.

Yes, your argument is correct.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.