Array Recursive Index Algorithm By Simulation

Given a list of integers nums and an integer k, let’s create a new set of possible elements { nums[k], nums[nums[k]], nums[nums[nums[k]]], … } stopping before it’s out of index.

Return the size of this set, or -1 if there’s a cycle.
Example 1
Input
nums = [1, 2, 3, 4, 5]
k = 0
Output
5
Explanation
We visit indices {0, 1, 2, 3, 4}

A[0] which has value of 1
A[1] which has value of 2
A[2] which has value of 3
A[3] which has value of 4
A[4] has value of 5 and A[5] is out of index.

Example 2
Input
nums = [4, 2, 1, 1, 1]
k = 3
Output
-1
Explanation
We visit indices {3, 1, 2, 1, …} which has a cycle

Recursive Index Algorithm

Although it is recursive, the implementation doesn’t have to be. We can use a hash set to remember the indices that we have already visited and return -1 if there is a cycle. We increment the counter if the new index is still within the range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int recursiveIndex(vector<int>& nums, int k) {
    int ans = 0;
    unordered_set<int> memo;
    while (true) {
        if (memo.count(k)) return -1;
        memo.insert(k);
        if (k < 0 || k >= nums.size()) {
            break;
        }
        ans ++;
        k = nums[k];
    }
    return ans;
}

int recursiveIndex(vector<int>& nums, int k) {
    int ans = 0;
    unordered_set<int> memo;
    while (true) {
        if (memo.count(k)) return -1;
        memo.insert(k);
        if (k < 0 || k >= nums.size()) {
            break;
        }
        ans ++;
        k = nums[k];
    }
    return ans;
}

Given that we know the size of the array, we can store the current iteration count, and return -1 (there must be a cycle) if the count is equal or more than the size of the array. If the N is large, it might take time to detect the loop.

1
2
3
4
5
6
7
8
9
10
11
12
13

int recursiveIndex(vector<int>& nums, int k) {
    int ans = 0;
    int cnt = 0;
    while (true) {
        if (k < 0 || k >= nums.size()) {
            break;
        }
        if (++ cnt > nums.size()) return -1;
        ans ++;
        k = nums[k];
    }
    return ans;
}

int recursiveIndex(vector<int>& nums, int k) {
    int ans = 0;
    int cnt = 0;
    while (true) {
        if (k < 0 || k >= nums.size()) {
            break;
        }
        if (++ cnt > nums.size()) return -1;
        ans ++;
        k = nums[k];
    }
    return ans;
}

The Pros is that we are using O(1) constant space for this algorithm.

–EOF (The Ultimate Computing & Technology Blog) —