Print all subarrays of an array having distinct elements

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

People are also reading:

• Print a given matrix in spiral form
• Program to Rotate an Array
• Construct a tree from Inorder and Level order traversals
• Find LCM and HCF of two numbers
• Move all zeros present in an array to the end
• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Create a mirror of an m–ary Tree
• Rearrange an array such that arr[i] = i