Print all subarrays of an array having distinct elements

By | November 28, 2021

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);
   }
}

 

Vamware

Output

1, 2, 3, 5
5, 3

People are also reading: 

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *