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

Tags: #<Tag:0x00007f1828ed75a0>


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.


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.


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


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