Print all subarrays of an array having distinct elements
Given an integer array, print all maximum size subarrays having all distinct elements in them.
For example,
Output: The largest subarrays with all distinct elements are:
{ 5, 2, 3 }
{ 2, 3, 5, 4 }
{ 5, 4, 3 }
The problem differs from the problem of finding the maximum size subsequence with distinct elements. Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.
We can use a sliding window to solve this problem easily. The idea is to maintain a window with an 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, use a map.
Following is the implementation in C++, Java, and Python based on the above idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> #include <unordered_map> using namespace std; // Utility function to print the subarray formed by `A[i, j]` void printSubarray(int A[], int i, int j, int n) { if (i < 0 || i > j || j >= n) { // invalid input return; } for (int index = i; index < j; index++) { cout << A[index] << ", "; } cout << A[j] << endl; } // Function to print all subarrays having distinct elements void calculate(int A[], int n) { // create a map to mark elements as visited in the current window unordered_map<int, bool> visited; // points to the left and right boundary of the current window; // i.e., the current window is formed by `A[left, right]` int right = 0, left = 0; // loop until the right index of the current window is less // than the maximum index while (right < n) { // keep increasing the window size if all elements in the // current window are distinct while (right < n && !visited[A[right]]) { visited[A[right]] = true; right++; } printSubarray(A, left, right - 1, n); // As soon as a duplicate is found (`A[right]`), // terminate the above loop, and reduce the window's size // from its left to remove the duplicate while (right < n && visited[A[right]]) { visited[A[left]] = false; left++; } } } int main() { int A[] = { 5, 2, 3, 5, 4, 3 }; int n = sizeof A / sizeof A[0]; calculate(A, n); return 0; } |
Output:
5, 2, 3
2, 3, 5, 4
5, 4, 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
import java.util.HashMap; import java.util.Map; class Main { // Utility function to print the subarray formed by `A[i, j]` public static void printSubarray(int[] A, int i, int j, int n) { if (i < 0 || i > j || j >= n) { // invalid input return; } for (int index = i; index < j; index++) { System.out.print(A[index] + ", "); } System.out.println(A[j]); } // Function to print all subarrays having distinct elements public static void calculate(int[] A) { int n = A.length; // create a map to mark elements as visited in the current window Map<Integer, Boolean> visited = new HashMap<>(); // put all elements on a map for (int val: A) { visited.put(val, false); } // points to the left and right boundary of the current window, // i.e., the current window is formed by `A[left, right]` int right = 0, left = 0; // loop until the right index of the current window is less // than the maximum index while (right < n) { // keep increasing the window size if all elements in the // current window are distinct while (right < n && !visited.get(A[right])) { visited.put(A[right], true); right++; } printSubarray(A, left, right - 1, n); // As soon as a duplicate is found (`A[right]`), // terminate the above loop, and reduce the window's size // from its left to remove the duplicate while (right < n && visited.get(A[right])) { visited.put(A[left], false); left++; } } } public static void main(String[] args) { int[] A = { 5, 2, 3, 5, 4, 3 }; calculate(A); } } |
Output:
5, 2, 3
2, 3, 5, 4
5, 4, 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# Function to print all sublists having distinct elements def calculate(A): # create a map to mark elements as visited in the current window visited = {} # put all elements in a dictionary for val in A: visited[val] = False # points to the left and right boundary of the current window, # i.e., the current window is formed by `A[left, right]` right = 0 left = 0 # loop until the right index of the current window is less # than the maximum index while right < len(A): # keep increasing the window size if all elements in the # current window are distinct while right < len(A) and not visited[A[right]]: visited[A[right]] = True right = right + 1 print(A[left: right]) # As soon as a duplicate is found (`A[right]`), terminate the above loop, # and reduce the window's size from its left to remove the duplicate while right < len(A) and visited[A[right]]: visited[A[left]] = False left = left + 1 if __name__ == '__main__': A = [5, 2, 3, 5, 4, 3] calculate(A) |
Output:
[5, 2, 3]
[2, 3, 5, 4]
[5, 4, 3]
The time complexity of the above solution is O(n), where n is the input size and requires O(n) extra space to mark elements in the current window.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)