SDE - 1

class Solution {
public:

void nextPermutation(vector& permutation) {
int n = permutation.size(), k,l;
for(k=n-2; k>=0; k--){
if(permutation[k]k; l--){
if(permutation[k] }
swap(permutation[k],permutation[l]);
reverse(permutation.begin()+k+1, permutation.end());
}
}
};

class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) 
return "";
String prefix = strs[0];
int len=0;
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
len = prefix.length()-1;
//System.out.println(len);
prefix = prefix.substring(0, len);
if (prefix.isEmpty()) return "";
} 
return prefix;
}

}

A top down solution for the "Decode Ways" problem. The approach followed is similar to the solution for the "Word Break" problem, which in turn is similar to the "Rod Cutting" problem in CLRS. Every partition is checked to see if it can be decoded. Since partitions may be repeatedly considered, memoization is used to prevent repeating computations.

'''

class Solution {

int numWays(string s, int i, int * dp) {

int res = 0;

int n = s.length();

// The end of the array has been reached and so the string 
// can be decoded
if(i == n) {
return 1;
}

// Get results from memo table if available
if(dp[i] != -1) {
return dp[i];
}

// Cut input string at i creating a substring of size 1
// and determine if remaining substring can be decoded
if(i < n) {
string s_loc = s.substr(i, 1);
int val = stoi(s_loc);
if(1 <= val && val <= 26) {
if(s[i] == '0') {
res = 0;
}
if(s[i] != '0') {
res = numWays(s, i + 1, dp);
} 
}
}

// Cut input string at i creating a substring of size 2
// and determine if remaining substring can be decoded 
if(i < n - 1) {
string s_loc = s.substr(i, 2);
int val = stoi(s_loc);
if(1 <= val && val <= 26) {
if(s[i] == '0') {
res = 0;
}
if(s[i] != '0') {
res = res + numWays(s, i + 2, dp);
} 
}
}

// Store results in memo table
dp[i] = res;

return res;
}

public:
int numDecodings(string s) {

int n = s.length();

// Declare and initialize memo table
int * dp = new int[n];
for(int i = 0; i < n; ++i) {
dp[i] = -1;
}

// Compute number of ways to decode
return numWays(s, 0, dp);
}
};

Since the array is Sorted in both row wise and column wise, Start the checking from first row and last col.
Why Not first row and First Col? Coz If the target is greater than the currentElement You will get confused as u can
move in both directions row wise and colwise.
Hence starting for first row and last col u can explore only 1 direction. If the target is greater than current element then move downwards(As array is sorted , we will have larger elements in the following rows) else move sidewards(bcos target is less than cur element).

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int row = 0;
int col = n - 1;
while(row < m && col >=0){
if(matrix[row][col] == target)
return true;
else if(matrix[row][col] < target)
row++;
else
col--;
}
return false;
}
}

Simple C++ Solution based on histogram question
If you haven't done histogram question then complete it first because it concept is same just with one extra loop.

Time Complexity - O(N^2)

Space Complexity - O(N)

int maximalRectangle(vector> &m)
{
int ans = 0;
vector sums(m[0].size(), 0);
for (int i = 0; i < m.size(); i++)
{
// From here histogram solution starts
stack st;
for (int j = 0; j <= sums.size(); j++)
{
// Summing up each row in sums vector but replacing with zero if current element is zero
if(j != sums.size())
sums[j] += (m[i][j] == '0') ? -sums[j] : m[i][j] - '0';

// Simple increasing Montonic Stack
while (!st.empty() && (j == sums.size() || sums[st.top()] >= sums[j]))
{
int height = sums[st.top()], width;
st.pop();
width = (st.empty()) ? j : j - st.top() - 1;
ans = max(ans, width * height);
}
st.push(j);
}
}
return ans;
}

ListNode* reverseList(ListNode* head) {
ListNode *prev = NULL, *cur=head, *tmp;
while(cur){
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}