Print all sub-arrays of an array having distinct elements

Given an array of integers, print all maximum size sub-arrays having all distinct elements in them.


 

For example,


Input: A[] = { 5, 2, 3, 5, 4, 3 }

Output: The largest sub-arrays with all distinct elements are

{ 5, 2, 3 }
{ 2, 3, 5, 4 }
{ 5, 4, 3 }

 
We can use Sliding Window approach to easily solve this problem. The idea is to use a window with invariant that all elements inside it must be distinct. The solution keeps on expanding the window to the right and if any duplicate is encountered, it shrinks the window from the left until all elements are distinct again. To keep track of distinct elements inside a window, we use a Map.

C++

Download   Run Code

Output:

5, 2, 3
2, 3, 5, 4
5, 4, 3

Java

Download   Run Code

Output:

5, 2, 3
2, 3, 5, 4
5, 4, 3

 
The time complexity of the above solution is O(n) and the extra space used by the solution is O(n) to mark elements of the current window.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of