Print all subarrays of an array having distinct elements

Posted in

Vinay Khatri
Last updated on September 26, 2022

    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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments