[C++] [Java] Clean Code - O(N)


  • 26

    The idea is to, start from every number, find circles in those index-pointer-chains, every time you find a set (a circle) mark every number as visited (-1) so that next time you won't step on it again.
    C++

    class Solution {
    public:
        int arrayNesting(vector<int>& a) {
            size_t maxsize = 0;
            for (int i = 0; i < a.size(); i++) {
                size_t size = 0;
                for (int k = i; a[k] >= 0; size++) {
                    int ak = a[k];
                    a[k] = -1; // mark a[k] as visited;
                    k = ak;
                }
                maxsize = max(maxsize, size);
            }
    
            return maxsize;
        }
    };
    

    Java

    public class Solution {
        public int arrayNesting(int[] a) {
            int maxsize = 0;
            for (int i = 0; i < a.length; i++) {
                int size = 0;
                for (int k = i; a[k] >= 0; size++) {
                    int ak = a[k];
                    a[k] = -1; // mark a[k] as visited;
                    k = ak;
                }
                maxsize = Integer.max(maxsize, size);
            }
    
            return maxsize;
        }
    }
    

  • 1
    Y

    @alexander your answer is tle


  • 0

    @yubin_gao Post wrong copy, here we go! Thanks for reminding :)


  • 0
    D

    32 ms solution.

            int maxsize = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == -1) continue;
                int size = 0;
                int idx = nums[i];
                while(nums[idx] >= 0) {
                    int tmp = nums[idx];
                    nums[idx] = -1;
                    idx = tmp;
                    size++;
                }
                maxsize = max(maxsize, size);
            }
            return maxsize;
    

  • 0

    Thank you! Very clean and concise code!


  • 0

    Same Approach.

    public int arrayNesting(int[] nums) {
       int max = 0;
       for (int idx = 0; idx < nums.length; idx ++) {
            int localmax = 0, jdx = idx;
            while (nums [jdx] >= 0) {
                localmax ++;
                int val = nums [jdx];
                nums [jdx] = -1;
                jdx = val;
            }
            max = Math.max (max, localmax);
        }
        return max;
    }
    

  • 0
    S

    @alexander once you change the original a[k] to be -1 for marking it as visited.
    For next iteration with i=1; don't you have to unset all?


  • 6
    L

    @snehakhobragade90-gmail.com This is my opinion. Like some iteration scan '5-4-3'(not this example), which means nums[3] == 5.
    Because items in array are special and nums[5] == 4 & nums[4] == 3, we can conclude 'nums[some digits not 3] == 5' or 'nums[some digits not 5] == 4' is not possible.
    There is no possible to scan like '1-2-5-4-3' in other iteration. So if we scan digits like ‘5’, '4', '3', that iteration must start with '3' or '4' or '5' and stay in this cycle(maybe '4-3-5' or '3-4-5' or '5-4-3'). Obviously, the length of this iteration wouldn't exceed 3. So it's no need to scan them repeatedly.


  • 0
    Z

    considerable


  • 0
    F

    Hi, alexander. I was wondering why don't you use Math.max() directly? The description of integer.max() is returns the greater of two int values as if by calling Math.max. Thank for you sharing.


  • 2
    C

    I think it will pollute original array:(


  • 0
    B

    @alexander Could you kindly explain how the complexity of the code is O(n)? Thank you.


  • 0

    @BatCoder Because every time you find a set (a circle) mark every number as visited (-1) so that next time you won't step on it again.
    at the end of the day, each number should only be visited once.


  • 0
    B

    @alexander Got it, thank you! :)


  • 5
    S

    Just some supplement.

    From the statement "The array of size N contains number [0, N-1]", we can know that in-degree of all nodes are exactly one (n different edges for n nodes).

    Therefore the graph should consist of several cycles and the cycles have no "tails". That's why we can skip the visited nodes, where to begin in a visited cycle doesn't matter in this circumstance.


  • 0
    G

    It's a good solution. It would be better if you return after you found the number of elements which are not visited is smaller than maxsize.


  • 0

    666666666666666666666666666666666666666666666


  • 8

    My initial idea is mark visited number for each start and clear out the mark before loop next start point, got TLE obviously..
    The trick part here is that the numbers are always form a ring, and no matter which number of this ring you start with total count will always be same, so no need to step on it one more time......

        public int arrayNesting(int[] nums) {
            int result = 1;
            for (int i = 0; i < nums.length; i++) {
                int index = i;
                int count = 0;
                while (nums[index] >= 0) {
                    int newIndex = nums[index];
                    nums[index] = -1;
                    index = newIndex;
                    count++;
                } 
                result = Math.max(result, count);
            }
            return result;
        }
    

  • 0

    @szlghl1 This is the long missing formal proof of this problem's solution. Love it.


  • 0
    H

    My idea is same as yours, however my code is not as clear as yours, nice job, bro!

    int arrayNesting(vector<int>& nums) {
    	int result =0;
    	int temp;
    	int tag;
    	int temp_r = 0;
    	for (int i = 0; i < nums.size(); i++) {
    		if (nums[i] < 0) {
    			continue;
    		}
    		else
    		{
    			tag = nums[i];
    			while (nums[tag]>=0) {
    				temp = tag;
    				tag = nums[tag];
    				nums[temp] = -1;
    				temp_r += 1;
    			}
    			nums[i] = -1;
    			result = result > temp_r ? result : temp_r;
    		}
    		temp_r = 0;
    	}
    	return result;
    }
    

Log in to reply
 

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