loading...

Daily Coding Challenge #76

wingkwong profile image Wing-Kam ・3 min read

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.


/*
All Paths From Source to Target

Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, ..., graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.
*/

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        // bfs approach
        vector<vector<int>> ans;
        queue<pair<int, vector<int>>> q;
        // starting from node 0
        q.push({0,vector<int>{0}});
        int goal_node = graph.size();
        while(!q.empty()){
            auto [cur_node, cur_path] = q.front();
            q.pop();
            // check if the current node is the goal node (graph.size()-1)
            if(cur_node == goal_node-1){
                // if so, put the current path to ans
                ans.emplace_back(cur_path);
                continue;
            }
            // if not, traverse those connected nodes
            for(auto next_node: graph[cur_node]){
                vector<int> next_path(cur_path);
                next_path.emplace_back(next_node);
                q.push({next_node, next_path});
            }
        }
        return ans;
    }
};

/*
LeetCode - Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1
Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0
*/

class Solution {
public:
    int findMin(vector<int>& nums) {
        // binary search approach
        // if nums[left] > nums[mid], that means the smaller value is between mid+1 and right
        // else it is located on another side
        int l=0,r=nums.size()-1,m;
        while(l<r){
            m = l+(r-l)/2;
            if(nums[m]<nums[r]) r=m;
            else l=m+1;
        }
        return nums[l];
    }
};

class Solution2 {
public:
    int findMin(vector<int>& nums) {
        return *min_element(nums.begin(),nums.end());
    }
};

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

/*
LeetCode - Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1
Example 2:

Input: [2,2,2,0,1]
Output: 0
Note:

This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?
*/

class Solution {
public:
    int findMin(vector<int>& nums) {
        // binary search approach
        // if nums[left] > nums[mid], that means the smaller value is between mid+1 and right
        // else it is located on another side
        int l=0,r=nums.size()-1;
        while(l<r){
            int m = l+(r-l)/2;
            if(nums[m]<nums[r]) r=m;
            else if(nums[m]>nums[r]) l=m+1;
            else { // handle nums[m]==nums[r]
                if(nums[m]<nums[l]) l++;
                else r--;
            }
        }
        return nums[l];
    }
};

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 πŸ†

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide