C++ Codes - Basic to Advanced 💻

// Given a 2D array mXn in which,
// => Integer in each row is sorted from left to right
// => First integer of each row > last integer of previous row
//Output: if element present - return true
//        if element absent - return false
function binarySearchof2DArr(arr,m,n,value){
    let left=0;
    let right=(m*n)-1;
    while(left<=right){
        let mid=left+Math.floor((right-left)/2);
        let mid_element=arr[Math.floor(mid/n)][mid%n];
        if(mid_element === value){
            return true;
        }
        else if(mid_element < value){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    return false;
}


let arr=[ [1,2,4,6], [10,11,16,20], [23,30,34,60] ];
let m=arr.length;
let n=arr[0].length;
let value=6;
let res=binarySearchof2DArr(arr,m,n,value);
console.log(res);

// time complexity - O(log(m*n))

// Best time for buying and selling the stocks 
function findMaxProfit(prices){
    let minValue=Number.MAX_SAFE_INTEGER;
    let maxValue=0;
    for(let i=0;i<prices.length;i++){
        if(prices[i]<minValue){
            minValue=prices[i];
        }
        else if(prices[i]-minValue > maxValue){
            maxValue=prices[i]-minValue;
        }
    }
    return maxValue;
}


// Driver code 
let prices=[7,1,4,6,5];
let maxProfit=findMaxProfit(prices);
console.log(maxProfit);

//time complexity: O(n)

// Two Pointer Approach
// Given an array [20,40,60,80,90,120,240] give the index of two numbers 
// for which sum will be 210.
function findIndex(arr,sum_val){
    let l=0;
    let r=arr.length-1;
    while(l<=r){
        if( (arr[l]+arr[r]) === sum_val){
            return [l,r];
        }
        else if(arr[l]+arr[r]>sum_val){
            r=r-1;
        }
        else{
            l=l+1;
        }
    }
}

let arr=[20,40,60,80,90,120,240];
let sum_val=210;
let [a,b]=findIndex(arr,sum_val);
console.log(`${arr[a]}+${arr[b]}=${arr[a]+arr[b]}`);

// time complexity: O(n)

// Binary Search 
// recursive approach 
function binarySearch(arr,x,left,right){
    let mid=left+Math.floor((right-left)/2);
    if(left>right){
        return -1;
    }
    else{
        if(arr[mid]===x){
            return mid;
        }
        else if(arr[mid] < x){
            return binarySearch(arr,x,mid+1,right);
        }
        else{
            return binarySearch(arr,x,left,mid-1);
        }
    }
}

let arr=[10,20,30,40,50];   //sorted array
let x=33;
let left=0;
let right=arr.length-1;
let res=binarySearch(arr,x,left,right);
if(res!=-1){
    console.log("Element found at ",res," index");
}
else{
    console.log("Element not found");
}

// time-complexity : O(log n)
// space-complexity : O(1)

// Binary Search 
// iterative approach 
function binarySearch(arr,x){
    let left=0;
    let right=arr.length-1;
    while(left<=right){
    let mid=left+Math.floor((right-left)/2);
        if(arr[mid] === x){
            return mid;
        }
        else if(arr[mid]<x){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    return -1;
}

let arr=[10,20,30,40,50];   //sorted array
let x=50;
let res=binarySearch(arr,x);
if(res!=-1){
    console.log("Element found at ",res," index");
}
else{
    console.log("Element not found");
}

// time-complexity : O(log n)
// space-complexity : O(1)

// Linear Search 

function linearSearch(arr,x){
    for(let i=0;i<arr.length;i++){
        if(arr[i]==x){
            return i;
        }
    }
    return -1;
}
let arr=[10,34,21,54,77,53];
let x=77;
let res=linearSearch(arr,x);
if(res!=-1){
    console.log("Element found at ",res," position");
}
else{
    console.log("Element not found");
}

// time complexity- O(n)

// space complexity - O(1)