Divida la array en un número mínimo de sub-arrays que tengan elementos únicos

Dada una array arr . La tarea es dividir la array en el número mínimo de subarreglos que contienen elementos únicos y devolver el recuento de dichos subarreglos. 
Nota : un elemento de array no puede estar presente en más de un subarreglo.
Ejemplos: 
 

Input : arr[] = {1, 2, 1, 1, 2, 3}
Output : 3
Explanation : The subarrays having unique elements are 
{ 1, 2 }, { 1 }, and { 1, 2, 3 }

Input : arr[] = {1, 2, 3, 4, 5}
Output : 1
Explanation : The subarray having unique elements is 
{ 1, 2, 3, 4, 5 }

Enfoque: 
la idea es mantener un conjunto mientras se recorre la array. Mientras se recorre, si ya se encuentra un elemento en el conjunto, aumente el recuento de subarreglo en 1, ya que tenemos que incluir el elemento actual en el siguiente subarreglo y borrar el conjunto para el nuevo subarreglo. Luego, proceda con la array completa de manera similar. La variable que almacena el conteo será la respuesta. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to count minimum subarray having
// unique elements
#include <bits/stdc++.h>
using namespace std;
 
// Function to count minimum number of subarrays
int minimumSubarrays(int ar[], int n)
{
    set<int> se;
 
    int cnt = 1;
 
    for (int i = 0; i < n; i++) {
        // Checking if an element already exist in
        // the current sub-array
        if (se.count(ar[i]) == 0) {
            // inserting the current element
            se.insert(ar[i]);
        }
        else {
            cnt++;
            // clear set for new possible value of subarrays
            se.clear();
            // inserting the current element
            se.insert(ar[i]);
        }
    }
 
    return cnt;
}
 
// Driver Code
int main()
{
    int ar[] = { 1, 2, 1, 3, 4, 2, 4, 4, 4 };
    int n = sizeof(ar) / sizeof(ar[0]);
    cout << minimumSubarrays(ar, n);
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
    // Function to count minimum number of subarrays
    static int minimumSubarrays(int ar[], int n)
    {
        Vector se = new Vector();
     
        int cnt = 1;
     
        for (int i = 0; i < n; i++)
        {
             
            // Checking if an element already exist in
            // the current sub-array
            if (se.contains(ar[i]) == false)
            {
                // inserting the current element
                se.add(ar[i]);
            }
            else
            {
                cnt++;
                 
                // clear set for new possible value
                // of subarrays
                se.clear();
                 
                // inserting the current element
                se.add(ar[i]);
            }
        }
        return cnt;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int ar[] = { 1, 2, 1, 3, 4, 2, 4, 4, 4 };
        int n = ar.length ;
         
        System.out.println(minimumSubarrays(ar, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python 3 implementation of the approach
 
# Function to count minimum number of subarrays
def minimumSubarrays(ar, n) :
    se = []
 
    cnt = 1;
 
    for i in range(n) :
         
        # Checking if an element already exist in
        # the current sub-array
        if se.count(ar[i]) == 0 :
             
            # inserting the current element
            se.append(ar[i])
        else :
            cnt += 1
             
            # clear set for new possible value
            # of subarrays
            se.clear()
             
            # inserting the current element
            se.append(ar[i])
    return cnt
 
# Driver Code
ar = [ 1, 2, 1, 3, 4, 2, 4, 4, 4 ]
n = len(ar)
print(minimumSubarrays(ar, n))
 
# This code is contributed by
# divyamohan123

// C# implementation of the approach
using System;
using System.Collections.Generic;            
 
class GFG
{
     
    // Function to count minimum number of subarrays
    static int minimumSubarrays(int []ar, int n)
    {
        List<int> se = new List<int>();
     
        int cnt = 1;
     
        for (int i = 0; i < n; i++)
        {
             
            // Checking if an element already exist in
            // the current sub-array
            if (se.Contains(ar[i]) == false)
            {
                // inserting the current element
                se.Add(ar[i]);
            }
            else
            {
                cnt++;
                 
                // clear set for new possible value
                // of subarrays
                se.Clear();
                 
                // inserting the current element
                se.Add(ar[i]);
            }
        }
        return cnt;
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
        int []ar = { 1, 2, 1, 3, 4, 2, 4, 4, 4 };
        int n = ar.Length ;
         
        Console.WriteLine(minimumSubarrays(ar, n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
    // Javascript implementation of the approach
     
    // Function to count minimum number of subarrays
    function minimumSubarrays(ar, n)
    {
        let se = new Set();
       
        let cnt = 1;
       
        for (let i = 0; i < n; i++)
        {
               
            // Checking if an element already exist in
            // the current sub-array
            if (se.has(ar[i]) == false)
            {
                // inserting the current element
                se.add(ar[i]);
            }
            else
            {
                cnt++;
                   
                // clear set for new possible value
                // of subarrays
                se.clear();
                   
                // inserting the current element
                se.add(ar[i]);
            }
        }
        return cnt;
    }
     
    // Driver code
     
        let ar = [ 1, 2, 1, 3, 4, 2, 4, 4, 4 ];
        let n = ar.length ;
           
        document.write(minimumSubarrays(ar, n));
 
// This code is contributed by susmitakundugoaldanga.
</script>

5

Complejidad del tiempo: