CONCEPTS USED:

Hashing

DIFFICULTY LEVEL:

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[0] = 3, A[1] = 5, A[2] = 0, A[3] = 1, A[4] = 6, A[5] = 2, A[6] = 4.

For various values of i :

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

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

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

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

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

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

for i = 6, we have -> (A[6], A[4])                   = (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[100] = {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[1000000] = {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[1000000];
      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.

Previous post Unique Color Shirt
Next post Rectangular Sweet Box

Leave a Reply

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