Help finding complexity


  • 0
    J

    Hi there

    I just got a solution for this problem maybe the code could be a bit more elegant but here it goes.

    The idea is simple given that the 2 arrays are ordered we can easily understand how many positions we need to transverse till we find the values.

    If it's odd then is one position if it's even then there are 2 positions to find. On the loop i have 2 pointers, i and j. I will transverse the first array and j the second. The count is the virtual pointer which will tell me if i have reached the mid position, if i have i will add the value if not i continue to iterate.

    Inside of the for loop i have 4 cases:

    • There are no more items on the first array to transverse or is empty
    • There are no more items on the second array to transverse or is empty
    • the value on the first array is less than the second therefore i have to visit it
    • the value on the second array is less than the second therefore i have to visit it

    The returned value is either divided or not, this depends on the sum of the size of the arrays.

    Regards Complexity:

    On the best case scenario:

    Let's say that one of the arrays is empty, if that is the case i am still iterating through half of the items (this could actually be enhanced on the solution). this means the complexity is O(n/2) being n the size of the array

    On the worst case:
    n - size of the first array
    m - size of the second array
    all values are smaller than in the second array which means i iterate on the first till the end and then on the second till half
    n + m/2 -> O(n + m/2 )

    Can you please help me understand if i have calculated the complexity correct;y?

    '''

    public double findMedianSortedArrays(int[] nums1, int[] nums2) { int size1= nums1.length;
            int size2= nums2.length;
            double result = 0.0;
            int sum = size1+size2;
            if(sum == 0)
            	return result;
            int findMiddle = (int) Math.ceil(sum/2.0) ;
            int remaining = sum % 2;
            int first =  findMiddle ;
            int second = remaining == 0? findMiddle +1: findMiddle;
            
            int count = 1;
            int checkStop = remaining ==0? 2:1;
    
            for (int i = 0, j=0; 
            		count < second || checkStop >0 ;      )
            {
         
            	if(size1 == 0 || !(i <size1))
            	{
            		if(count == first || count == second ) { result += nums2[j];checkStop--;}
            		count++;
            		j++;
            	}
            	else if(size2 ==0 || !(j<size2)){
            		if(count == first || count == second) { result += nums1[i]; checkStop--;}
            		count++;
            		i++;
            	}
            	else if( i < size1 && nums1[i] <  nums2[j])
            	{
                   	if(count == first || count == second) { result += nums1[i]; checkStop--;}
            		count++;
            		i++;
            		
            	}
            	else if(size2 != 0 && j < size2) 
            	{
                   	if(count == first || count == second ) { result += nums2[j];checkStop--;}
            		count++;
            		j++;
            	}
            	
            }
            
      
            return remaining == 0? result /2.0 : result;
        }
    

    '''


Log in to reply
 

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