# Daily Coding Challenge #22

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
*/

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//  L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
//  L(i) = 1, if no such j exists.
int n=nums.size();
if(n==0) return 0;
vector<int> dp(n+1,1);
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
// find out the max in dp
int ans=0;
for(int k:dp) ans=max(ans,k);
return ans;
// or return *max_element(dp.begin(),dp.end());
}
};
``````

``````/*
LeetCode - Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
*/

class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n=(int)triangle.size();
// starting from the second last row
// e.g. [6,5,7]
for(int i=n-2;i>=0;i--){
// traverse each item
for(int j=0;j<(int)triangle[i].size();j++){
// add itself to the min of below 2 numbers
// e.g j=0: 6 + min(4,1) = 7
//     j=1: 5 + min(1,8) = 6
//     j=2: 7 + min(8,3) = 10
triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
}
}
// at the end, the value in the top row is the min sum
return triangle[0][0];
}
};
``````

``````/*
LeetCode - Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
*/

class Solution {
public:
char isValid(char a){
return a!='0';
}

char isValid(char a, char b){
return (a=='1'||(a=='2'&&b<='6'));
}

int numDecodings(string s) {
int n=(int)s.size();
if(n==0||s[0]=='0') return 0;
if(n==1) return 1;
int m1=1,m2=1,m;
for(int i=1;i<n;i++){
m=0;
// validate the current character and the previous character
if(!isValid(s[i])&&!isValid(s[i-1],s[i])) return 0;
if(isValid(s[i])) m=m1;
if(isValid(s[i-1],s[i])) m+=m2;
m2=m1;
m1=m;
}
return m;
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

### Discussion

My `O(n log n)` solution to the first problem: play.rust-lang.org/?version=stable...

``````fn length_of_lis(numbers: &[isize]) -> usize {
// This is the longest increasing subsequence that can end with a number:
let mut chain_length = std::collections::BTreeMap::new();

// This acts as a reverse index of chain_length. Since we always increase the length by one -
// it can be a vector:
let mut best_for_length = Vec::new();

for &num in numbers {
// Find the longest subsequence num can continue:
let continue_from = chain_length.range(..num).next_back();
let prefix_length = if let Some((_, &prefix_length)) = continue_from {
prefix_length
} else {
0
};

if prefix_length < best_for_length.len() {
// This is where the magic happens. If we already have a subsequence with the same
// length that ends with a higher number, we don't need that subsequence since any
// subsequence that can continue it can also continue this new subsequence we just
// discovered. By removing the old one, we are preventing the `continue_from` search
// from yielding a higher that represents a shorter subsequence.

let prev_best = best_for_length[prefix_length];
assert!(num <= prev_best); // otherwise num would have continued the subsequence
best_for_length[prefix_length] = num;
chain_length.remove(&prev_best);
} else {
best_for_length.push(num);
}
chain_length.insert(num, prefix_length + 1);
}
chain_length.values().max().copied().unwrap_or(0)

}
``````