Is partition-based method O(n)


  • 0
    Z

    Hello, I used a partition-based method to solve this problem, but I'm not quite sure if its complexity is O(n), so can anybody help me to analys it?

    The algorithm is :

    1. partition the array into two part using nums[-1] (indicated in val)
    2. as I scan the array, I can get the minimum and maximum of both the left and right array (iLessMin, iLessMax, iBiggerMin, iBiggerMax)
    3. calculate the bigger gap between the "val" and left/right array (indicated in currentGap)
    4. if the max possible gap of left array or right array is bigger than gap, calculate its max gap (indicated by lGap and rGap, done in recursive way); otherwise, neglect the left or right array.
    5. return the max value of the three gaps : max (lefGap, rightGap, currentGap)

    The method is a little similar to the algorithm of "find the kth biggest value in an array", but I just can't be sure if it's O(n). Thanks for your help :)

    class Solution:
        def partition(self,nums):
            if len(nums) < 2:
                return
            i = 0
            j = len(nums)-2
    
            iLessMin = float("inf")
            iLessMax = 0
    
            iBiggerMin = float("inf")
            iBiggerMax = 0
    
            while i <= j:
                if nums[i] < nums[-1]:
                    iLessMin = min(iLessMin, nums[i])
                    iLessMax = max(iLessMax, nums[i])
                    i += 1
                else:
                    iBiggerMin = min(iBiggerMin, nums[i])
                    iBiggerMax = max(iBiggerMax, nums[i])
                    nums[i], nums[j] = nums[j], nums[i]
                    j -= 1
            assert(i < len(nums))
            nums[i], nums[-1] = nums[-1], nums[i]
            return iLessMin, iLessMax, iBiggerMin, iBiggerMax, i, len(nums) - i - 1, nums[i]
            
            
        
        # @param {integer[]} nums
        # @return {integer}
        def maximumGap(self, nums):
            if len(nums) < 2:
                return 0
            if len(nums) is 2:
                return abs(nums[0] - nums[1])
    
            iLessMin, iLessMax, iBiggerMin, iBiggerMax, i, j, val = self.partition(nums)
    
            currentGap = 0
            if i >= 1:
                currentGap = max(currentGap, val - iLessMax)
            if j >= 1:
                currentGap = max(currentGap, iBiggerMin - val)
    
            lGap = 0
            rGap = 0
            if i >= 2:
                if currentGap < iLessMax - iLessMin:
                    lGap = self.maximumGap(nums[:i])
            if j >= 2:
                if currentGap < iBiggerMax - iBiggerMin:
                    rGap = self.maximumGap(nums[i+1:])
            return max(rGap, lGap, currentGap)

  • 0
    C

    Nope. This is nlg(n)

    Because it calls partition on both half the array "maximumGap"


  • 0
    Z

    But this a more practical. Imagine how large the memory has to be allocated in bucket sort based solution


  • 0
    M
    public class Solution {
    public int maximumGap(int[] nums) {
        if(nums.length<2) return 0;
        if(nums.length==2) return Math.abs(nums[0]-nums[1]);
        return maximumGapOne(nums,0,nums.length-1,0,30);
        
    }
    public int maximumGapOne(int[]nums, int start, int end, int maxGap, int bitN){
        if(start>=end) return maxGap;
        if(bitN<0) return maxGap;
        int splitPoint=split(nums,bitN,start,end);
        // System.out.println("split: " + Arrays.toString(nums) +" bitN:" + bitN + " start: "+start+" end:" + end+ " split: " + splitPoint);
        int max=findMax(nums,start,splitPoint-1);
        // System.out.println("max: " + max);
        int min=findMin(nums,splitPoint,end);
        // System.out.println("min: " + min);
        if(max>=0 && min>=0) maxGap=Math.max(maxGap,max<min?min-max:0);
        if(bitN!=0) {
            maxGap=Math.max(maxGap,maximumGapOne(nums,start,splitPoint-1,maxGap,bitN-1));
            maxGap=Math.max(maxGap,maximumGapOne(nums,splitPoint,end,maxGap,bitN-1));
        }
        return maxGap;
            
        
    }
    public int findMax(int[]nums, int start, int endInc){
        if(start>endInc)return -1;
        int max=Integer.MIN_VALUE;
        for(int i=start;i<=endInc;i++){
            max=Math.max(max,nums[i]);
        }
        return max;
    }
    public int findMin(int[]nums,int start,int endInc){
        if(start>endInc)return -1;
        int min=Integer.MAX_VALUE;
        for(int i=start;i<=endInc;i++){
            min=Math.min(min,nums[i]);
        }
        return min;
    }
    public int split(int[]nums,int bitN, int start, int end){
        if(start==end) return start;
        int twoPow=1<<bitN; //bitN = 0 to 30
        while(start<=end){
            boolean isStartZero=(twoPow&nums[start])==0;
            boolean isEndZero=(twoPow&nums[end])==0;
            if(!isStartZero && isEndZero ){
                int temp=nums[start];
                nums[start]=nums[end];
                nums[end]=temp;
                ++start;
                --end;
            }else if(isStartZero && isEndZero){
                ++start;
            }else if(!isStartZero && !isEndZero){
                --end;
            }else {
                ++start;
                --end;
            }
        }
        return start;//the splitting point from where 1's start at bitN
        
    }
    

    }

    this is my partition based method.
    during the split method, I am running over the elements O(n) times in total even with the run on two different splits the total elements analyzed is O(n) and since I am calling this 31 times. Its O(n)


Log in to reply
 

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