# Daily Coding Challenge #76

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], , , []]
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!

## wingkwong / atcoder

### Discussion   