# Unique Array

Hashing

Easy

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A` with `N` elements containing all elements from `0` to `N-1`, your task is to find the `maximum` length of an `Unique Array`.

Unique Array:
It contains elements in this manner,
`(A[i], A[A[i]], A[A[A[i]]], ...)` for any value of `i`
and the elements are `unique`.

Suppose the first element in `A` starts with the selection of element `A[i]` of `index = i` then next element in `A` will be `A[A[i]]`, and then `A[A[A[i]]]`, till you don't find a duplicate element in the unique array `A`.

See original problem statement here

#### For Example:

``````Input : N = 7, A = [3, 5, 0, 1, 6, 2, 4]

Output: 5

Explanation : We have,

A = 3, A = 5, A = 0, A = 1, A = 6, A = 2, A = 4.

For various values of i :

for i = 0, we have -> (A, A, A, A, A) = (3, 1, 5, 2, 0)

for i = 1, we have -> (A, A, A, A, A) = (5, 2, 0, 3, 1)

for i = 2, we have -> (A, A, A, A, A) = (0, 3, 1, 5, 2)

for i = 3, we have -> (A, A, A, A, A) = (1, 5, 2, 0, 3)

for i = 4, we have -> (A, A)                   = (6, 4)

for i = 5, we have -> (A, A, A, A, A) = (2, 0, 3, 1, 5)

for i = 6, we have -> (A, A)                   = (4, 6)

For indexes = 0, 1, 2, 3, and 5, Maximum length of unique array A is 5.``````

#### SOLVING APPROACH:

1. The idea is to refer best online programming courses and use an additional Visited Array for storing if an element was previously visited or not.

2. Traverse the array and for each element run a while loop and check if it was previously visited or not, if `Not`, mark it as visited, increment the value of `count` and consider this element as our next index and keep repeating the same process till an element is found which was previously visited.

3. Keep updating the `maximum` value with the `maximum count` value.

#### SOLUTIONS:

```
#include <stdio.h>

int max(int a, int b){
return (a>b)? a:b;
}

int main()
{

int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);

/* creating a hash array for marking if the element
was marked previously or not */
int visited = {0};
int ans = 0;

/* start from every index and find for max value */
for(int i=0; i<n; i++){
int count = 0;
int curr = arr[i];

/* if the element was visited earlier skip this iteration
else mark it as visited and increment the count */
while(visited[curr] == 0){
visited[curr] = 1;
count++;
curr = arr[curr];
}

/* compare the value of count with the max value found yet */
ans = max(ans, count);
}

printf("%d\n", ans);
}
return 0;
}

```
```
#include <bits/stdc++.h>
using namespace std;

int main()
{

int t; cin>>t;
while(t--){
int n; cin>>n;
int arr[n];
for(int i=0; i<n; i++)
cin>>arr[i];

/* creating a hash array for marking if the element
was marked previously or not */
int visited = {0};
int ans = 0;

/* start from every index and find for max value */
for(int i=0; i<n; i++){
int count = 0;
int curr = arr[i];

/* if the element was visited earlier skip this iteration
else mark it as visited and increment the count */
while(visited[curr] == 0){
visited[curr] = 1;
count++;
curr = arr[curr];
}

/* compare the value of count with the max value found yet */
ans = max(ans, count);
}

cout<<ans<<"\n";
}
return 0;
}
```
```
import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);

int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++)
arr[i] = sc.nextInt();

/* creating a hash array for marking if the element
was marked previously or not */
int visited[] = new int;
int ans = 0;

/* start from every index and find for max value */
for(int i=0; i<n; i++){
int count = 0;
int curr = arr[i];

/* if the element was visited earlier skip this iteration
else mark it as visited and increment the count */
while(visited[curr] == 0){
visited[curr] = 1;
count++;
curr = arr[curr];
}

/* compare the value of count with the max value found yet */
ans = Math.max(ans, count);
}
System.out.println(ans);
t--;
}
}
}
```

Space Complexity: `O(N)`, due to additional `Visited Array`.