C++ Solution using Divide and Conquer, Time Complexity: O(log n) [CORRECT ME IF I AM WRONG]

google
Tags: #<Tag:0x00007f1828ed75a0>

#1

The question asks us to perform a minimum number of comparisons to get a maximum and minimum element from the array so doing comparison linearly will result in O(n) time complexity, hence a divide and conquer approach is required.

pair<int, int> getMaxMin(vector<int> &A, int start, int last){

    int n = last - start + 1 ;
    if(n <= 2){
        int maxEle = max(A[start], A[last]) ;
        int minEle = min(A[start], A[last]) ;
        return make_pair(maxEle, minEle) ;    
    }

    int mid = (int)(start + last)/2 ;
    pair<int, int> left = getMaxMin(A, start, mid) ;
    pair<int, int> right = getMaxMin(A, mid+1, last) ;

    int maxEle = max(left.first, right.first) ;
    int minEle = min(left.second, right.second) ;

    return make_pair(maxEle, minEle) ;
}

int Solution::solve(vector<int> &A) {

    if(A.size() == 1){
        return A[0] + A[0] ;
    }

    pair<int, int> maxMinEle = getMaxMin(A, 0, A.size()-1) ;

    return maxMinEle.first + maxMinEle.second ;
}

Any improvements int the code is welcomed.


#2

I think it is still O(n) complexity. You are not making a choice to go either left or right. You are going both ways, and accessing all the elements in the array.


#3

Hi, thanks for the reply, has the number of comparisons reduced by log N instead of N if we had used the linear method?


#4

Normally we do this nX1
you are doing n(1/2 +1/2)
same things bro.