# Daily Coding Challenge #79

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 - Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.
*/

class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// stack approach
stack<int> s;
unordered_map<int,int> m;
for(int n:nums2){
// if s.top() is less than n
// set n as the next greater for all s.top()<n cases
while(s.size()&&s.top()<n){
m[s.top()]=n;
s.pop();
}
s.push(n);
}
int sz=nums1.size();
vector<int> ans(sz,-1);
for(int i=0;i<sz;i++){
auto lt=m.find(nums1[i]);
// if it can be found, the ans is lt->second
if(lt!=m.end()){
ans[i]=lt->second;
}
}
return ans;
}
};

class Solution2 {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// small numbers
vector<int> ans;
for(int i=0;i<nums1.size();i++){
int next=0, t=-1;
for(int j=0;j<nums2.size();j++){
if(next){
if(nums2[j]>nums1[i]) {
t=nums2[j];
break;
}
}
if(nums1[i]==nums2[j]){
next = 1;
}
}
ans.push_back(t);
}
return ans;
}
};


/*
LeetCode - Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
*/

class Solution {
public:
int climbStairs(int n) {
if(!n) return 1;
int dp[n+1];
memset(dp,0,sizeof(int)*(n+1));
dp=1;
dp=1;
// targets: no of stairs
for(int i=2;i<=n;i++){
// ways: no of steps
for(int j=1;j<=2;j++){
dp[i] += dp[i-j];
}
}
return dp[n];
}
};

class Solution2 {
public:
int climbStairs(int n) {
if(n==1) return 1;
vector<int> dp(n+1,0);
dp=1; // take 1 step
dp=2; // either take 1 step + 1 step or take 2 steps
for(int i=3;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};

class Solution3 {
public:
int climbStairs(int n) {
vector<int> memo(n+1,0);
return h(memo,n,0);
}
private:
int h(vector<int> &memo, int n, int k){
if(k>n) return 0;
if(k==n) return 1;
if(memo[k]) return memo[k];
memo[k] = h(memo,n,k+1) + h(memo,n,k+2);
return memo[k];
}
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();



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

## wingkwong / atcoder

### Discussion My solutions in Haskell. I have not run them against LeetCodes tests since they don't support Haskell, but I think they're correct. I did another more complex solution to the second one, but after testing some numbers I realized it was just the Fibonacci sequence.

findNextGreater nums n =
let x = dropWhile (< n) $tail$ dropWhile (/= n) nums
in if null x then -1 else head x

nextGreaterElement nums1 nums2 =
map (findNextGreater nums2) nums1

fib a _ 0 = a
fib a b n = fib b (a+b) (n-1)

climbStairs = fib 1 1  