Largest Cycle
You are given a maze consisting of N cells numbered from 0 to N - 1 and an array ‘arr’ of N integers in which arr[i] contains the cell number that can be reached from ‘i’th cell in one step. You are supposed to find the length of the largest cycle in the maze, given that each cell has less than or equal to 1 exit but can have multiple entry points.

Note:

The maze may contain self-cycles. arr[i] = -1 means the ‘i’th cell doesn’t have an exit.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow. The first line of each test case contains integer ‘N’, which denotes the number of cells in the maze. The second line contains N integers, denoting the elements of the array ‘arr’.

Output Format:

For each test case, print the length of the largest cycle in the maze and -1 if there are no cycles. Print the output of each test case in a separate line.

Constraints:

1

Question

Largest Cycle

You are given a maze consisting of N cells numbered from 0 to N - 1 and an array ‘arr’ of N integers in which arr[i] contains the cell number that can be reached from ‘i’th cell in one step. You are supposed to find the length of the largest cycle in the maze, given that each cell has less than or equal to 1 exit but can have multiple entry points.

Note:

The maze may contain self-cycles.
arr[i] = -1 means the ‘i’th cell doesn’t have an exit.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains integer ‘N’, which denotes the number of cells in the maze.

The second line contains N integers,  denoting the elements of the array ‘arr’.

Output Format:

For each test case, print the length of the largest cycle in the maze and -1 if there are no cycles.

Print the output of each test case in a separate line.

Constraints:

1<= T <= 50
1 <= N <= 10,000
-1 <= arr[i] <= N-1

Where ’T’ is the number of test cases, and N denotes the number of cells in the maze and arr[i] is the cell that can be reached from ‘i’th cell.

Time Limit: 1 sec

Accepted Answer

DFS

The idea is to do a depth-first search to find all the cycles which are formed and calculate the length of the largest cycle. We are treating the array as a graph of directed edges. Whenever we get into any of the cells in the cycle, using dfs we will visit all the subsequent cells in the cycle. Out of all the cycles, we will return the cycle of maximum length.

The steps are as follows:

Initialize a boolean array ‘visited’ of size N with 0 at all the indexes initially which denotes whether a particular cell is visited or not.
Initialize an integer ‘res’ to 0, which denotes the largest cycle in the maze.
Define a recursive function ‘dfs’ with arguments ‘arr’, ‘positions’, ‘currentCell’, ‘totalLengthCovered’, array ‘visited’, an integer ‘res’ which denotes the given array ‘arr’, a hash map which is used to store the order in which vertices are visited, the current cell for the recursive call, the total number of cells visited in the current recursive call, array to know whether a particular cell is visited or not, and final answer ‘res’.
- If the current cell is already visited in any of the previous recursive calls, then return from the function.
- If there is no exit from the current cell, then mark the cell as visited and return from the function.
- If the current cell is visited in the same recursive call i.e. it is present in the hash map, mark it as visited, take ‘res’ as a maximum of ‘res’ and ‘totalLengthCovered’ - positions[i].
- Insert current cell into the hash map (current cell as the key and total length covered in the current recursion as the value).
- Recursively call for the connected cell to the current cell and increment the total length covered.
- After the recursive call, mark the current cell visited in the array ‘visited’.
Iterate from i = 0 to N-1:
- If the ith cell is not visited:
  - Declare a hash map ‘positions’ that is used to store the order in which the vertices are visited.
  - Call the recursive function ‘dfs’ with arguments ‘arr’, ‘positions’, ‘i’, 0, ‘visited’, ‘res’.
If ‘res’ is equal to 0, it means that there is no cycle, return -1.
Otherwise, return ‘res’ as the final answer.

Space Complexity: O(n)Explanation:

O(N), where N is the number of cells in the maze.

We are using a visited array of size N and a positions array of size N. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the number of cells in the maze.

As the time complexity of a Depth-first Search is O(V+E), where V is the number of vertices and E is the number of edges in the graph. Here the number of vertices is N, and the number of edges is at most N. Hence the overall time complexity is O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the number of cells in the maze.
*/

import java.util.ArrayList;

public class Solution
{
    static ArrayList visited;
    static ArrayList positions;
    static int res = 0;
    static int totalLengthCovered = 0;

    static void dfs(int arr[], int currentCell)
    {
        // If the current cell is already visited
        if (visited.get(currentCell) == 1)
        {
            return;
        }

        // If there is no exit from this cell
        if (arr[currentCell] == -1)
        {
            visited.set(currentCell, 1);
            return;
        }

        // We have found a cycle.
        if (positions.get(currentCell) != -1)
        {
            
            // Update the maximum length.
            res = Math.max(res, totalLengthCovered - positions.get(currentCell));
            visited.set(currentCell, 1);
            return;
        }


        positions.set(currentCell, totalLengthCovered);
        
        // Recur for the next cell.
        totalLengthCovered++;
        dfs(arr, arr[currentCell]);

        // Mark the current cell as visited.
        visited.set(currentCell, 1);
        positions.set(currentCell, -1);
}

    public static int findLongestCycle(int[] arr)
    {
        int n = arr.length;

        // For storing the visited vertices.
        visited = new ArrayList(n);
        positions = new ArrayList(n);

        for (int i = 0; i < n; i++)
        {
            visited.add(0);
            positions.add(-1);
        }

        res = 0;

        // Iterate through the cells.    
        for (int i = 0; i < n; i++)
        {
            if (visited.get(i) == 0)
            {
                totalLengthCovered = 0;
                dfs(arr, i);
            }
        }

        // There is no cycle
        if (res == 0)
        {
            return -1;
        }
        
        return res;
    }
}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of cells in the maze.

*/



void dfs(vector &arr, vector &positions, int currentCell, int totalLengthCovered, vector &visited, int &res)

{

    // If the current cell is already visited

    if (visited[currentCell] == 1)

    {

        return;

    }



    // If there is no exit from this cell

    if (arr[currentCell] == -1)

    {

        visited[currentCell] = 1;

        return;

    }



    // We have found a cycle.

    if (positions[currentCell] != -1)

    {

        // Update the maximum length.

        res = max(res, totalLengthCovered - positions[currentCell]);

        visited[currentCell] = 1;

        return;

    }





    positions[currentCell] = totalLengthCovered;

    

    // Recur for the next cell.

    dfs(arr, positions, arr[currentCell], totalLengthCovered + 1, visited, res);



    // Mark the current cell as visited.

    visited[currentCell] = 1;

    positions[currentCell] = -1;

}





int findLongestCycle(vector &arr)

{



    int n = arr.size();



    // For storing the visited vertices.

    vector visited(n, 0);

    vector positions(n, -1);

    int res = 0;



    // Iterate through the cells.    

    for (int i = 0; i < n; i++)

    {

        if (visited[i] == 0)

        {

            dfs(arr, positions, i, 0, visited, res);

        }

    }



    // There is no cycle

    if (res == 0)

    {

        return -1;

    }

    

    return res;

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of cells in the maze.

'''



def dfs(arr, positions, currentCell, totalLengthCovered, visited, res):



    # If the current cell is already visited

    if (visited[currentCell] == 1):

        return



    # If there is no exit from this cell

    if (arr[currentCell] == -1):

        visited[currentCell] = 1

        return



    # We have found a cycle.

    if (positions[currentCell] != -1):



        # Update the maximum length.

        res[0] = max(res[0], totalLengthCovered - positions[currentCell])

        visited[currentCell] = 1

        return



    positions[currentCell] = totalLengthCovered



    # Recur for the next cell.

    dfs(arr, positions, arr[currentCell], totalLengthCovered + 1, visited, res)



    # Mark the current cell as visited.

    visited[currentCell] = 1

    positions[currentCell] = -1





def findLongestCycle(arr):

    n = len(arr)



    # For storing the visited vertices.

    visited = [0 for i in range(n)]

    positions = [-1 for i in range(n)]



    res = [0]



    # Iterate through the cells.  

    for i in range(n):

        if (visited[i] == 0):

            dfs(arr, positions, i, 0, visited, res)



    # There is no cycle

    if (res[0] == 0):

        return -1



    return res[0]

Note:

Input Format:

Output Format:

Constraints:

Top JUSPAY Software Developer interview questions & answers

Popular interview questions of Software Developer