# Daily Coding Challenge #88

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 - Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]
*/

class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
// use nums as frequency array
// if it is visited, set it to negative
// if the num has been visited, then the current number occurs twice
for(int num:nums){
num=abs(num);
if(nums[num-1]<0){
ans.emplace_back(num);
}else{
nums[num-1]=-nums[num-1];
}
}
return ans;
}
};


/*
LeetCode - Rotting Oranges
In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid.length <= 10
grid[i][j] is only 0, 1, or 2.

*/

class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int cnt=0, ans=-1;
queue<vector<int>> q;
// count each orange and put rotted oranges to a queue
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]>0) cnt++;
if(grid[i][j]==2) {
q.push({i,j});
}
}
}
vector<vector<int>> dir={{0,1},{1,0},{-1,0},{0,-1}};
// bfs approach to rot the adjacent orange
while(!q.empty()){
ans++;
int n = q.size();
for(int i=0;i<n;i++){
vector<int> c=q.front();
q.pop();
cnt--;
// check 4 directions
for(int j=0;j<4;j++){
int x=c+dir[j], y=c+dir[j];
if(x>=grid.size()||x<0||y>=grid.size()||y<0||grid[x][y]!=1) continue;
grid[x][y]=2;
q.push({x,y});
}
}
}
// if all oranges are rotted, return max(ans,0)
if(cnt==0) return max(ans,0);
// if not, return -1
return -1;
}
};


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

## wingkwong / atcoder

### Discussion   