Array Nesting

2.1K

Question: Given a zero-indexed array ‘A’ of length ‘N’ which contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], …} subjected to a particular condition.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]],.. and so on. By that analogy, we stop adding elements as soon as we get a duplicate.

Input: A = {5, 4, 0, 3, 1, 6, 2}

Output: 4

Let us try to understand the problem statement. Given the condition of the set S, the elements must be nested one after the other.

-> Starting at i = 0.
A[0] = 5;   // A[i] == A[0]
A[5] = 6;   // A[A[i]] == A[A[0]] == A[5]
A[6] = 2;   // A[A[A[i]]] == A[A[A[0]]] == A[A[5]] == A[6]
A[2] = 0;   // and so on…
A[0] = 5;   // We reach the start point hence S = 4 elements

-> Starting at i = 1.
A[1] = 4;   // A[i] == A[1]
A[4] = 1;   // A[A[i]] == A[A[1] == A[4]
A[1] = 4;   // We reach the start point hence S = 2 elements

As per the problem statement, out of all these sets possible, we need to give the highest number of elements in such a set.

A brute force solution would be to start at each of the indices and try to form sets. We can keep a track of the largest set formed and then return the result.
Looking at the problem closely can hint at a better solution.

Let us look at the array once again, when we start from i = 0.

We see that we form a kind of cycle.
A similar cycle is seen when we start from i = 1.

So, this means that we will get the same set S if we start from positions (0, 2, 5, 6). Because we are forming a cycle.

Hence, we should try to leverage this fact and form a solution. While evaluating the set S, we can mark the elements of the array as visited. In the next iteration, if the element is already visited, we do not need to evaluate the set S again. This will save a lot of time in our solution.

public int findSetS(int[] nums) {

    boolean[] visited = new boolean[nums.length];
    int res = 0;

    for (int i = 0; i < nums.length; i++) {
      if (!visited[i]) {
        int start = nums[i];
        int count = 0;
        do {
          start = nums[start];
          count++;
          visited[start] = true;
        }
        while (start != nums[i]);
        res = Math.max(res, count);
      }
    }
    return res;
  }
Code language: Java (java)

A working solution can be found here. https://ideone.com/vIvw89

Time Complexity: O(n)
Space Complexity: O(n)