# Print all subarrays of an array having distinct elements

Posted in

Vinay Khatri
Last updated on September 10, 2024

## Problem

Given an integer array, print all maximum-sized subarrays having all distinct elements in them.

#### Sample Input

`[1, 2, 3, 4, 3]`

#### Sample Output

```[1, 2, 3, 4]
[4, 3]```

### Approach

We can initially iterate until we find a duplicate element. We will obtain a window that has all unique elements. From here, we move the left end of the window towards the right until elements are unique. When all elements become unique, then again iterate the right end of the subarray until a duplicate is found. The approach takes O(N) time.

#### C++ Programming

```#include <iostream>
#include <unordered_map>
using namespace std;
void printSubarray(int arr[], int i, int j, int n)
{
if (i < 0 || i > j || j >= n) {
return;
}
for (int index = i; index < j; index++) {
cout << arr[index] << " ";
}
cout << arr[j] << endl;
}
void solve(int arr[], int n)
{
unordered_map<int, bool> mp;
int r = 0, l = 0;

while (r < n)
{

while (r < n && !mp[arr[r]])
{
mp[arr[r]] = true;
r++;
}
printSubarray(arr, l, r - 1, n);
while (r < n && mp[arr[r]])
{
mp[arr[l]] = false;
l++;
}
}
}
int main()
{
int arr[] = {1, 2, 3, 5, 3 };
int n = sizeof arr / sizeof arr[0];
solve(arr, n);
return 0;
}```

Output

```1 2 3 5
5 3```

#### Python Programming

```def solve(arr):
mp = {}
for val in arr:
mp[val] = False

r = 0
l = 0

while r < len(arr):
while r < len(arr) and not mp[arr[r]]:
mp[arr[r]] = True
r = r + 1
print(arr[l: r])
while r < len(arr) and mp[arr[r]]:
mp[arr[l]] = False
l = l + 1

arr = [1, 2, 3, 5, 3]
solve(arr)```

Output

```[1, 2, 3, 5]
[5, 3]```

#### Java Programming

```import java.util.HashMap;
import java.util.Map;
class Solution
{
public static void printSubarray(int[] arr, int i, int j, int n)
{
if (i < 0 || i > j || j >= n) {
return;
}
for (int index = i; index < j; index++) {
System.out.print(arr[index] + ", ");
}
System.out.println(arr[j]);
}
public static void solve(int[] arr)
{
int n = arr.length;
Map<Integer, Boolean> mp = new HashMap<>();
for (int val: arr) {
mp.put(val, false);
}

int r = 0, l = 0;
while (r < n)
{

while (r < n && !mp.get(arr[r]))
{
mp.put(arr[r], true);
r++;
}
printSubarray(arr, l, r - 1, n);
while (r < n && mp.get(arr[r]))
{
mp.put(arr[l], false);
l++;
}
}
}
public static void main(String[] args)
{
int[] arr = {1, 2, 3, 5, 3};
solve(arr);
}
}```

#### Output

```1, 2, 3, 5
5, 3```