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);
}

DP || Leetcode 5. Longest Palindromic Substring

Problem Link

In this problem, there will be given a string, we have to find the longest palindromic substring of this string.

For this purpose, we have to check all the substring we can generate. From them the longest one which is palindrome will be the answer. In the naive approach, surely will cross the time limit.

DP approach: Suppose we have a string "cababa". Lets simulate this string by building a table of 6*6.

The cell value (i,j) = 0, means starting from index i to index j of the string doesn't have a palindrome

The cell value (i,j) = 1, means starting from index i to index j of the string have a palindrome, and its size is (j-i+1)

1. A single character is a palindrome itself. so, we will fill all the diagonal(i,i) as 1. 

So, the table looks like Fig :1

                                           Fig[1]
2. We will check all of 2 size substring, they formed palindrome[if the string characters are same] or not.

    for (0,1)>> characters are 'c' and 'a' so its not a palindrome we will put 0 at (0,1) 

    for (1,2)>> characters are 'a' and 'b' so its not a palindrome we will put 0 at (1,2)

    for (2,3)>> characters are 'b' and 'a' so its not a palindrome we will put 0 at (2,3)

    ....

    ....

 

3.Then we will check if the start index i and the end index j is the same character. if they are same then we will check between them all the characters are palindrome or not. In other word mathematically we will say a range palindrome if and only if,
    s[i]==s[j] and table[i+1][j-1]==1

table[i+1][j-1] represents middle substring, if you dont catch it, you can understand this by doing some paper works.

Finally, our looks like Fig 2.

                                            Fig[2]

Code:

class Solution {
public:
    int dp[1000][1000];
    string longestPalindrome(string s) {
        int ans=1;
        int start=0,end=0;
        for(int i=0;i<(int)s.size();i++){
            dp[i][i] =1; 
        }
        for(int i=0;i<(int)s.size()-1;i++){
            if(s[i]==s[i+1]){ dp[i][i+1] = 1;ans = 2;start=i;end=i+1;}
            else dp[i][i+1] = 0;
        }
        
        for(int j=2;j<(int)s.size();j++){
            for(int i=0;i<(int)s.size()-2;i++){
                if(s[i]==s[j] && dp[i+1][j-1]==1){
                    dp[i][j] = 1;
                    ans = max(ans,j-i+1);
                    if(ans==j-i+1){
                        start = i;
                        end = j;
                    }
                }
            }
        }
        string ansString = "";
        for(int i=start;i<=end;i++){
            ansString.push_back(s[i]);
        }
        return ansString;
    }
};

Leetcode 1048. Longest String Chain || DP

Problem Link

In this problem, there will be given array of words consisting of lowercase English letters. We have to find the longest chain of word we can make from these words. A chain between two words can make if and only if deleting only single character from one of the word makes other one. In example,
abcde->abde , abcde->bcde can have chain between them. But, abcde->adce cant.
Now, we have to find the longest chain length we can make  from these words.

Idea: Instead of making words from smaller word, we can find a smaller word from a bigger one. For this purpose,
1.We first generated all the word(size == original word size -1) from a given word and,
2.we tested which generated word is belongs to the words array. If any word is found repeat step 1-2.

So, it seems going for the all possible case we can generate  so far. But doing it in recursive naive approach surely will exceed the time limits. So, we need to use memoization.

Code[ Memoization]:

class Solution {
public:
    unordered_map<string,int>wordMap,memo;
    int ans=1;
    int caller(string str){
        if(str.size()==1){
            if(wordMap[str]!=0) memo[str]=1;
            else memo[str]=0;
            return memo[str];
        }
        if(wordMap[str]==0){
            memo[str] = 0;
            return 0;
        }
        else if(wordMap[str]!=0){
            for(int j=0;j<str.size();j++){
                string temp = str.substr(0,j) + str.substr(j+1,str.size()-j);
                if(memo[temp]==0){
                    memo[str] = max(memo[str],caller(temp)+1);
                }
                else memo[str] = max(memo[str],memo[temp]+1);
            }
        }
        return memo[str];
    }
    int longestStrChain(vector<string>& words) {
        for(int i=0;i<(int)words.size();i++){
            wordMap[words[i]]++;
        }
        for(int i=0;i<(int)words.size();i++){
            if(memo[words[i]]==0){
                memo[words[i]]=caller(words[i]);
            }
            ans = max(ans,memo[words[i]]);
        }
        return ans;
    }
};

LCS || Leetcode 583. Delete Operation for Two Strings

Problem Link

In this problem , Given two strings. we have to make these two strings equal. In one move we can delete any character from either string. We have to do it in minimum number of steps possible.

Problem Idea: We have to reduce the strings, which makes the two strings equal. But hence we have to do it in minimum number of steps. So, we can say, we have to find such subsequence of strings that both the strings consisted. In other word we have to find the size of the longest common subsequence (LCS)

Complexity: O(m*n) ||   where m and n are size of the two strings.

Code[LCS Tabulization]:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: const static int sz = 505; int dp[sz][sz]; int lcs(string s1,string s2){ for(int i=0;i<s1.size();i++){ dp[i][0] = 0; } for(int i=0;i<s2.size();i++){ dp[0][i] = 0; } for(int i=1;i<=s1.size();i++){ for(int j=1;j<=s2.size();j++){ if(s1[i-1]==s2[j-1]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } return 2*dp[s1.size()][s2.size()]; } int minDistance(string word1, string word2) { return word1.size()+word2.size()-lcs(word1,word2); } };

Leetcode 1641. Count Sorted Vowel Strings

Problem Link

We have to get the number of permutations we can have with using 5 vowels character in lexicographical order.

After every vowel character we can only take characters which are lexicographically equal or larger than it.
Suppose, we have a substring "aei" but we have to make the string size 4. But we can't take character "a" or "e", we forced to take character "i", "o", or "u".
For decrease the time complexity we used memoization technique with some extra memory space.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: int memo[51][6]; int solve(int n,int i){ if(n==0){ return 1; } if(memo[n][i]!=0){ return memo[n][i]; } int forReturn = 0; for(int j=i;j<5;j++){ forReturn += solve(n-1,j); } memo[n][i] = forReturn; return memo[n][i]; } int countVowelStrings(int n) { return solve(n,0); } };

Leetcode 216. Combination Sum III ||Backtracking

 Problem Link

In this problem, we just have to generate a sum  S using K numbers. The numbers could be in a range of (1-9) we only can take a number once for a combination.

Solution Idea: Backtracking.  

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<vector<int> > ans; int k,n; void fun(int numberUsed, int num, int sum,vector<int>vec,int flag[]){ if(numberUsed == k){ if(sum==n){ ans.push_back(vec); } } else if(numberUsed<k){ if(sum<n){ for(int i=num+1;i<=9;i++){ if(flag[i]==0 && sum+i<=n){ vec.push_back(i); flag[i]=1; fun(numberUsed+1,i,sum+i,vec,flag); vec.pop_back(); flag[i]=0; } } } } } vector<vector<int>> combinationSum3(int kk, int nn) { k = kk; n = nn; int flag[10]; memset(flag,0,sizeof flag); vector<int>vec; fun(0,0,0,vec,flag); return ans; } };

Leetcode 17. Letter Combinations of a Phone Number

Problem Link

In this problem we will be given a string of digits, as like old days featured phones. We have to generate the number of ways we can generate string if,

digit 2 = "abc"

digit 3 = "def"

....

digit 9 = "wxyz"

Solution idea:
we can use dfs  approach for solve this.

Code: 

 class Solution {  
 public:  
   map<char,string>mm;  
   vector<string>vec;  
   void solve(string digits,int pos,string ans){  
     if(pos == digits.size()){  
       if(digits!="")vec.push_back(ans);  
       return;  
     }  
     for(auto it:mm[digits[pos]]){  
       ans.push_back(it);  
       solve(digits,pos+1,ans);  
       ans.pop_back();  
     }      
   }  
   vector<string> letterCombinations(string digits) {  
     mm['2'] = "abc";  
     mm['3'] = "def";  
     mm['4'] = "ghi";  
     mm['5'] = "jkl";  
     mm['6'] = "mno";  
     mm['7'] = "pqrs";  
     mm['8'] = "tuv";  
     mm['9'] = "wxyz";  
     solve(digits,0,"");  
     return vec;  
   }  
 };