Sponsored
Sponsored
In this approach, we use an auxiliary 'visited' array to keep track of the elements that have already been included in any set s[k]. For each unvisited element at index i, we keep iterating through the sequence by accessing nums[nums[i]] until we encounter an element already visited. Each time we reach an unvisited element, we mark it as visited, and increment the length of the current sequence. We keep track of the longest length among all sequences generated from each starting index.
Time Complexity: O(N), where N is the number of elements in the array, as each element is visited at most once.
Space Complexity: O(N) due to the additional 'visited' array.
1#include <stdio.h>
2#include <stdbool.h>
3
4int arrayNesting(int* nums, int numsSize){
5 bool visited[numsSize];
6 for (int i = 0; i < numsSize; i++) visited[i] = false;
7 int max_length = 0;
8 for (int i = 0; i < numsSize; i++) {
9 if (!visited[i]) {
10 int start = i, length = 0;
11 do {
12 visited[start] = true;
13 start = nums[start];
14 length++;
15 } while (!visited[start]);
16 if (length > max_length) max_length = length;
17 }
18 }
19 return max_length;
20}
21
22int main() {
23 int nums[] = {5, 4, 0, 3, 1, 6, 2};
24 int numsSize = sizeof(nums) / sizeof(nums[0]);
25 printf("%d\n", arrayNesting(nums, numsSize));
26 return 0;
27}This C program uses an iterative method with a boolean array to track visited elements. It loops through each element in the array and checks sequences starting from unvisited indices. The nested do-while loop continues until a visited element is encountered, at which point the sequence stops. The maximum length of the sequences encountered is stored and returned.
This approach minimizes space usage by modifying the input array itself as a marker of visited nodes. By setting each visited position to a sentinel value (e.g., -1 or a number outside the expected range), we can achieve the same iterative closure tracking. We simply iterate over each number and trace the sequence until we circle back to a marked node. This is an improvement on memory constraints when needing to handle particularly large datasets.
Time Complexity: O(N), executing a linear pass through the nodes.
Space Complexity: O(1), modifying input without auxiliary space.
public class Solution {
public int ArrayNesting(int[] nums) {
int max_length = 0;
for (int i = 0; i < nums.Length; i++) {
if (nums[i] != -1) {
int start = i, length = 0;
while (nums[start] != -1) {
int temp = nums[start];
nums[start] = -1;
start = temp;
length++;
}
max_length = Math.Max(max_length, length);
}
}
return max_length;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {5, 4, 0, 3, 1, 6, 2};
Console.WriteLine(solution.ArrayNesting(nums));
}
}C# adopts this efficient conversion technique by using indexed tails realized through transformed values. Each index update assesses completed sections, making accurate length tallies possible with low system overhead, showcasing C# capability in minimizing resource use by known value modifications.