Set Matrix Zeroes

/*

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

*/
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rowSize = matrix.size();
        if(rowSize == 0) return;
        int colSize = matrix[0].size();
        if(colSize == 0) return;
       
        int i, j;
        int k;
        int impossibleValue = -10000;
       
        for(i=0; i<rowSize; i++){
          for(j=0; j<colSize; j++){
            if(matrix[i][j]==0){
             matrix[i][j] = impossibleValue;
            }
          }
        }
       
        for(i=0; i<rowSize; i++){
          for(j=0; j<colSize; j++){
            if(matrix[i][j] == impossibleValue){
              for(k=0; k<colSize; k++){
                 if(matrix[i][k]!=impossibleValue)
                 matrix[i][k] = 0;
              }
              for(k=0; k<rowSize; k++){
                 if(matrix[k][j]!=impossibleValue)
                 matrix[k][j] = 0;
              }
            }
          }
        }
       
        for(i=0; i<rowSize; i++){
         for(j=0; j<colSize; j++){
            if(matrix[i][j] == impossibleValue)
            matrix[i][j] = 0;
         }
        }
    }
};

Multiply Strings

/*

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

*/
class Solution {
public:
    vector<int> convertToDigit(string num){
        int size = num.length();
        char init = '0';
        vector<int> result;
        int digit;
        for(int i=0; i<size; i++){
            digit = num[i] - init;
            if(digit>9 || digit<0){
                result.clear();
                return result;
            }
            result.push_back(digit);
        }
        return result;
    }
    char convertToChar(int num){
       char init = '0';
       return init+num;
    }
  
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> left;
        vector<int> right;
        string result;
      
        left = convertToDigit(num1);
        right = convertToDigit(num2);
      
        vector<vector<int>> temp;
        vector<int> line;
        int i, j, k;
        int multi = 0;
        int higher = 0;
        for(i=0; i<right.size(); i++){
            line.clear();
            higher = 0;
            for(j=left.size()-1; j>=0; j--){
                multi = right[i]*left[j];
                line.insert(line.begin(), multi%10 + higher);
                higher = multi/10;
            }
            if(higher>0) line.insert(line.begin(), higher);
            else line.insert(line.begin(), 0);
            temp.push_back(line);
        }
      
        int sum;
        int plus = 0;
        int colSize = right.size();
        int rowSize = left.size()+1;
        for(k=colSize+rowSize-2; k>=0; k--){
            sum = 0;
            for(i=colSize-1; i>=0; i--){
              for(j=rowSize-1; j>=0; j--){
                if(i+j==k){
                   sum = sum + temp[i][j];
                   }
               }
            }
            sum = sum + plus;
            result.insert(0, 1, convertToChar(sum%10));
            plus = sum/10;
        }
       
        i=0;
        while(result[i]=='0'){
         i++;
        }
        if(i==result.size()) i = i-1;
       
        string substring = result.substr(i);
       
        return substring;
    }
};

Remove Element

/*

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

*/
class Solution {
public:
    void swap(int A[], int i, int j){
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0;
        int j = n-1;
        for(i=0; i<n && i<j; i++){
          if(A[i]==elem){
            while(A[j]==elem && j>=0 && i<=j) j--;
            if(j>=0 && i<=j){
            swap(A,i,j);
            j--;
            } else return i;
          }
        }
       
        if(i==j){
         if(A[i]==elem) return i;
         else return i+1;
        }
       
        if(j==-1) return 0;
       
        if(i==n) return n;
    }
};

Search Insert Position

/*

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

*/
class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return 0;
        if(target<=A[0]) return 0;
        if(target==A[n-1]) return n-1;
        if(target>A[n-1]) return n;
       
        int start = 0;
        int end = n-1;
        int mid;
        while(start <= end){
          mid = (start+end)/2;
          if(A[mid]==target) return mid;
          if(target<A[mid] && target>A[mid-1]) return mid;
          if(target>A[mid] && target<A[mid+1]) return mid+1;
          if(target>A[mid]) start = mid+1;
          else end = mid-1;
        }
    }
};

Search for a Range

/*

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

*/
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        result.push_back(-1);
        result.push_back(-1);
       
        if(target < A[0] || target > A[n-1]) return result;
       
        int start = 0;
        int end = n-1;
     
        int low = -1;
        int high = -1;
        int mid;
        if(A[start]==target) low = start;
        else{
          while(start <= end){
            mid = (start+end)/2;
            if(target==A[mid] && target>A[mid-1]){
              low = mid;
              break;
            }
            if(target<=A[mid]) end = mid-1;
            if(target>A[mid]) start = mid+1;
            }
        }
       
        start = 0;
        end = n-1;
        if(A[end]==target) high = end;
        else{
          while(start <= end){
            mid = (start+end)/2;
            if(target==A[mid] && target<A[mid+1]){
              high = mid;
              break;
            }
            if(target<A[mid]) end = mid-1;
            if(target>=A[mid]) start = mid+1;
            }
        }
       
        if(low!=-1 || high!=-1){
          result.clear();
          if(low!=-1){
            result.push_back(low);
          } else result.push_back(high);
          if(high!=-1){
           result.push_back(high);
          } else result.push_back(low);
        }
       
        return result;
    }
};

Search in Rotated Sorted Array

/*

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

*/
class Solution {
public:
    int searchMid(int A[], int low, int high, int const target){
      if(low>high) return -1;
      int mid = (low+high)/2;
      if(A[mid]==target) return mid;
      if(A[low]==target) return low;
      if(A[high]==target) return high;
     
      if(A[mid] > A[low]){
         if(target > A[low] && target < A[mid]) {
           return searchMid(A, low, mid-1, target);
         }
         else return searchMid(A, mid+1, high, target);
      }
      else{
        if(target > A[mid] && target < A[high]){
          return searchMid(A, mid+1, high, target);
        }
        else return searchMid(A, low, mid-1, target);
      }
    }
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return -1;
        if(target<A[0] && target >A[n-1]) return -1;
       
        return searchMid(A, 0, n-1, target);
    }
};

class Solution {
public:
    int searchMid(int A[], int start, int end, int const target){
      int low = start;
      int high = end;
     
      while(low<=high){
      int mid = (low+high)/2;
      if(A[mid]==target) return mid;
      if(A[low]==target) return low;
      if(A[high]==target) return high;
     
      if(A[mid] > A[low]){
         if(target > A[low] && target < A[mid]) {
           high = mid-1;
         }
         else low = mid+1;
      }
      else{
        if(target > A[mid] && target < A[high]){
          //return searchMid(A, mid+1, high, target);
          low = mid+1;
        }
        else high=mid-1;
      }
      }
     
      return -1;
    }
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return -1;
        if(target<A[0] && target >A[n-1]) return -1;
       
        return searchMid(A, 0, n-1, target);
    }
};

Median of Two Sorted Arrays

/*

Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

*/
class Solution {
public:
    int findKthElement(int A[], int sa, int B[], int sb, int k){
      if((sa+sb) < k) return -100;
      if(sa==0) return B[k-1];
      if(sb==0) return A[k-1];
     
      if(A[sa-1]<=B[0]){
        if(sa>=k) return A[k-1];
        else return B[k-sa-1];
      }
      if(B[sb-1]<=A[0]){
        if(sb>=k) return B[k-1];
        else return A[k-sb-1];
      }
      if(k==1) return min(A[0],B[0]);
     
      int ma;
      int mb;
      int newSearch = k/2;
      if(sa<=sb){
      if(sa>=newSearch) ma = newSearch;
      else ma = sa;
      mb = k - ma;
      }
      else{
      if(sb>=newSearch) mb = newSearch;
      else mb = sb;
      ma = k-mb;
      }
     
      if(A[ma-1]==B[mb-1]) return A[ma-1];
     
      if(A[ma-1]<B[mb-1]){
        return findKthElement(A+ma, sa-ma, B, mb, k-ma);
      }
     
      if(A[ma-1]>B[mb-1]){
        return findKthElement(B+mb, sb-mb, A, ma, k-mb);
      }
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int totalSize = m+n;
        double result;
        int half = totalSize/2;
        if(totalSize%2==1){
           result = findKthElement(A, m, B, n, (totalSize+1)/2);
        }
        else{
           double first =  findKthElement(A, m, B, n, half+1);
           double second =  findKthElement(A, m, B, n, half);
           result = (first+second)/2;    
        }
        return result;
    }
};