algoadvance

Leetcode 565. Array Nesting

Problem Statement

You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].

You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the rule below.

Suppose the first element in s[k] starts with the selection of the element nums[k] of nums. The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on. By that analog, we stop adding right before a duplicate element occurs in s[k].

Return the longest length of a set s[k].

Clarifying Questions

  1. Is the array nums guaranteed to be a permutation of [0, n - 1] without any duplicates?
    • Yes.
  2. Should we expect large input sizes for nums?
    • Yes, your solution should account for potentially large inputs efficiently.
  3. Can we modify the input array nums?
    • Yes, modifying nums is allowed to optimize space usage.

Strategy

  1. Identify Loops: Because nums is a permutation of numbers [0, n-1], it means each element in nums is unique and appears exactly once. We can form cycles starting from any element. Our goal is to find the length of the longest cycle.

  2. Visited Array: Use a boolean array to keep track of visited indices to avoid recalculating lengths of cycles starting from the same elements multiple times.

  3. Iterate and Count: For each index, if it’s not visited, perform a traversal to count the length of the cycle starting from that index.

  4. Optimization:

    • Use the input array nums itself to mark elements as visited by modifying their value.
    • While traversing a cycle, mark the elements to avoid revisiting them.

Code

public class Solution {
    public int arrayNesting(int[] nums) {
        int maxSize = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != Integer.MAX_VALUE) {
                int size = 0;
                int start = i;

                while (nums[start] != Integer.MAX_VALUE) {
                    int temp = start;
                    start = nums[start];
                    size++;
                    nums[temp] = Integer.MAX_VALUE; // Mark as visited
                }
                
                maxSize = Math.max(maxSize, size);
            }
        }

        return maxSize;
    }
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the input array nums. Each element will be visited at most once.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI