O(N) solution with constant space. Very easy to understand. (93% faster)


  • 0
    M

    We know that each sequence will eventually form a cycle as shown in the example below. To keep it in O(N) timeline, we must make sure to not to visit same cycle again and again. To achieve constant space we will modify input array only to get to solution. If we cannot modify input array, we will have to pay O(N) space for this solution.

    Input: A = [5,4,0,3,1,6,2]
    Index cycle => 0->5->6->2->0

    The idea is to modify each node we visit with the start of cycle as we traverse through.
    Below is how array will look like after each iteration. If we encounter that item at index i is lesser than i, we have already visited it and we will not compute it again.

    iteration 1
    [0,4,0,3,1,0,0] cycle size = 4

    iteration 2
    [0,1,0,3,1,0,0] cycle size = 2

    iteration 2
    [0,1,0,3,1,0,0] cycle size = 3 (3 is at same index so cycle ends right away)

    public class Solution {
        public int arrayNesting(int[] nums) {
            int maxSizeSeen = 0;
            
            for(int i = 0 ; i < nums.length; i++){
                // If value is lower than i, we have already visited this cycle
                if(nums[i] >= i){
                    int nextIndex = nums[i]; // Remember next index
                    nums[i] = i; // 
                    int size = 1;
                    while(nextIndex != i){
                        int nextIndexTemp = nums[nextIndex];
                        nums[nextIndex] = i;
                        nextIndex = nextIndexTemp;
                        size++;
                    }
                     maxSizeSeen = Integer.max(size, maxSizeSeen);
                }
            }
            
            return maxSizeSeen;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.