loading...

Daily Coding Challenge #79

wingkwong profile image Wing-Kam ・3 min read

Daily Coding Challenge (84 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 82 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58 59) Daily Coding Challenge #59 60) Daily Coding Challenge #60 61) Daily Coding Challenge #61 62) Daily Coding Challenge #62 63) Daily Coding Challenge #63 64) Daily Coding Challenge #64 65) Daily Coding Challenge #65 66) Daily Coding Challenge #66 67) Daily Coding Challenge #67 68) Daily Coding Challenge #68 69) Daily Coding Challenge #69 70) Daily Coding Challenge #70 71) Daily Coding Challenge #71 72) Daily Coding Challenge #72 73) Daily Coding Challenge #73 74) Daily Coding Challenge #74 75) Daily Coding Challenge #75 76) Daily Coding Challenge #76 77) Daily Coding Challenge #77 78) Daily Coding Challenge #78 79) Daily Coding Challenge #79 80) Daily Coding Challenge #80 81) Daily Coding Challenge #81 82) Daily Coding Challenge #82 83) Daily Coding Challenge #83 84) Daily Coding Challenge #84

About

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[0]=1;
        dp[1]=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]=1; // take 1 step
        dp[2]=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!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Daily Coding Challenge (84 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 82 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58 59) Daily Coding Challenge #59 60) Daily Coding Challenge #60 61) Daily Coding Challenge #61 62) Daily Coding Challenge #62 63) Daily Coding Challenge #63 64) Daily Coding Challenge #64 65) Daily Coding Challenge #65 66) Daily Coding Challenge #66 67) Daily Coding Challenge #67 68) Daily Coding Challenge #68 69) Daily Coding Challenge #69 70) Daily Coding Challenge #70 71) Daily Coding Challenge #71 72) Daily Coding Challenge #72 73) Daily Coding Challenge #73 74) Daily Coding Challenge #74 75) Daily Coding Challenge #75 76) Daily Coding Challenge #76 77) Daily Coding Challenge #77 78) Daily Coding Challenge #78 79) Daily Coding Challenge #79 80) Daily Coding Challenge #80 81) Daily Coding Challenge #81 82) Daily Coding Challenge #82 83) Daily Coding Challenge #83 84) Daily Coding Challenge #84

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide
 

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