Leetcode 74. Search a 2D Matrix

 Problem Link

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

In this problem we can find the appropriate row number by using binary search

Then similarly we can find the appropriate row number by using binary search.

So, this solution requires two binary search.

Code:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        int n=matrix[0].size();
        int loRow=0, hiRow= m-1;
        while(hiRow>=loRow){
            int midRow = (hiRow+loRow)/2;
            if(matrix[midRow][0]>target){
                hiRow = midRow-1;
            }
            else{
                loRow = midRow+1;
            }
        }
        // cout << hiRow << " "<< loRow << endl;
        int hiCol=n-1;
        int loCol=0;
        if(hiRow<0)return false;
        while(hiCol>=loCol){
            int midCol = (hiCol+loCol)/2;
            if(matrix[hiRow][midCol]>target){
                hiCol = midCol-1;
            }
            else{
                loCol = midCol+1;
            }
        }
        if(hiCol<0)return false;
        if(matrix[hiRow][hiCol]==target) return true;
        else return false;
    }
}; 

Count inversions in an array || Merge Sort

Problem link

Problem Statement: Given an array of N integers, count the inversion of the array.

What is an inversion of an array? Definition: for all i & j < size of array, if i < j then you have to find pair (A[i],A[j]) such that A[j] < A[i].

for better explanation click 

>>Basically this problem required a direct implementation of merge sort. 

>>The number of inversion is the number of time it finds the array mismatched during a merge sort process. In a merge sort process we divide the array into two halves. until we have the unit of the array elements. Then just comparing the unit variables and put them in right places and merge back to the array.

Code

#include <bits/stdc++.h> 
long long Merge(long long *arr, long long *temp, long long left, long long mid, long long right){
    long long cnt = 0;
    long long i = left;
    long long j = mid;
    long long k = left;
    while((i<=mid-1) && (j<=right)){
        if(arr[i]<=arr[j]){
            temp[k++] = arr[i++];
        }
        else{
            temp[k++] = arr[j++];
            cnt = cnt + (mid-i);
        }
    }
    
    // leftovers
    while(i<=mid-1){
        temp[k++] = arr[i++];
    }
    while(j<=right){
        temp[k++] = arr[j++];
    }
    
    for( i = left; i<=right;i++){
        arr[i] = temp[i];
    }
    return cnt;
}

long long mergeSort(long long *arr, long long *temp, long long left,long long right){
    long long mid, cnt = 0;
    if(right>left){
        mid = (left+right)/2;
        cnt += mergeSort(arr,temp,left,mid);
        cnt += mergeSort(arr,temp,mid+1,right);
        cnt += Merge(arr,temp,left,mid+1,right);
    }
    return cnt;
}
long long getInversions(long long *arr, int n){
    long long temp[n];
    return mergeSort(arr,temp,0,n-1);
}