Search a value in a special 2D Sorted Matrix

[Question]
Write an efficient algorithm that searches for a value in an m x n 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.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

[Analysis]

Binary search will work on this question. The 2nd condition is a key to apply Binary Search on this 2D sorted matrix. One way is to treat the 2D array as 1D array and do a Binary Search. Another way is to do Binary Search on all first elements of each row; then do a binary search on the potential row. The time complexities of two approaches are the same: O(lgMN) == O(lgN+lgM).

[Solution]
class Solution {
public:
    bool searchVector( vector<int> &v, int target ) {
        if (v.size()==0) return false;
        if (v.size()==1) return (v[0]==target);
       
        int mid = v.size()/2;
        if (v[mid]==target) return true;
       
        vector<int> half;
        if (v[mid]<target) {
            half = vector<int>(v.begin()+mid, v.end());
        } else {
            half = vector<int>(v.begin(), v.begin()+mid);
        }
        return searchVector( half, target );
    }
   
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if (matrix.size()==0) return false;
        if (matrix.size()==1) return searchVector( matrix[0], target);
       
        int mid = matrix.size()/2;
       
        if (matrix[mid][0]== target) return true;
       
        vector<vector<int>> half;
        if (matrix[mid][0]<target) {
            half = vector<vector<int>> (matrix.begin()+mid, matrix.end());
        } else {
            half = vector<vector<int>> (matrix.begin(), matrix.begin()+mid);
        }
        return searchMatrix( half, target );
    }
};

Find the Minimum in a Sorted but Rotated Array

[Question]

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). Find the minimum element.
You may assume no duplicate exists in the array.

[Analysis]

Simple solution is to experiment linear search and the time complexity is O(N).

It is noticeable that the pivot at position i must meet the following condition: A[i-1]>A[i] and A[i]<A[i+1] (if rotation happened). For example, "0" in above array. So we can apply binary search in this case. Time complexity is O(lg N).

A follow-up question can be, find a given value in such array. The first step will be find the pivot. Then the second step is to apply binary search again for the given value. 

[Solution]

int findMin(vector<int> &num) {
    if (num.size()==0) return 0;
    if (num.size()==1 || num[0]<num.back()) return num[0];
    if (num.size()==2) return min (num[0], num[1]);

    int mid = num.size()/2;
    if (num[mid]<num[mid+1] && num[mid]<num[mid-1]) return num[mid];
 

    vector<int> split;
    if (num[mid]>num.back()) {
        split = vector<int> (num.begin()+mid, num.end());
    } else {
        split = vector<int> (num.begin(), num.begin()+mid);
    }
    

    return findMin(split);
}

Palindrome Partitioning - LeetCode 131

[Question]

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.

[Analysis]

The minimum cut of the string S at position i is,
     MinimumCuts(i) = MinimumCuts[j-1]+1, while  S[j] ...S[i] is the longest palindrome sub-string ending at position i.  (j<i).

Use a table to calculate the palindrome sub-string at each position. C[i,j] is true when S[j,i]  is a palindrome. C[i,j] is true, when C[i-1, j+1] is true && S[i] == S[j].

Total time complex is O(N^2).

[Solution]

    int minCut(string s) {
        if (s.size()==0) return 0;
     
        int len = s.size();
     
        int dp[len+1];
        for (int i=0; i<len+1; i++)
            dp[i] = i;

        bool c[len+1][len+1];
        for (int i=0; i<=len; i++)
            for (int j=0; j<=len; j++)
            c[i][j] = false;
         
        c[0][0]=true;
        for (int i=1; i<len+1; i++)
            for (int j=i; j>0; j--) {
                if (s[i-1]==s[j-1] && (i-j<2 || c[i-1][j+1]==true)) {
                    c[i][j] = true;
                    dp[i] = min(dp[i], dp[j-1]+1);
                }
            }
     
        return dp[len]-1;
    }