๐—–๐—ฆ ๐—”๐—น๐—ด๐—ผ ๐Ÿ’ป ๐ŸŒ ใ€Ž๐—–๐—ผ๐—บ๐—ฝ๐—ฒ๐˜๐—ถ๐˜๐—ถ๐˜ƒ๐—ฒ ๐—ฃ๐—ฟ๐—ผ๐—ด๐—ฟ๐—ฎ๐—บ๐—บ๐—ถ๐—ป๐—ดใ€
9.63K subscribers
5.61K photos
3 videos
95 files
10.6K links
๐ŸšฉMain Group - @SuperExams
๐Ÿ“Job Updates - @FresherEarth

๐Ÿ”ฐAuthentic Coding Solutions(with Outputs)
โš ๏ธDaily Job Updates
โš ๏ธHackathon Updates & Solutions

Buy ads: https://telega.io/c/cs_algo
Download Telegram
bool issafe(int i, int j, vector<vector<int>> &a)
{
int rows = a.size();
int cols = a[0].size();
if (i < 0 or j < 0 or i >= rows or j >= cols or a[i][j] == 0)
{
return false;
}
return true;
}
int distanceTraversed(vector<vector<int>> a)
{
int rows = a.size();
int cols = a[0].size();
if (rows == 0)
{
return 0;
}
int finaldist = -1;
if (a[0][0] == 9)
{
return 0;
}
unordered_map<string, bool> visited;
queue<pair<int, pair<int, int>>> q;
int dist;
q.push({0, {0, 0}});
string s = to_string(0) + "@" + to_string(0);
visited[s] = true;
while (!q.empty())
{
pair<int, pair<int, int>> node = q.front();
q.pop();
if (a[node.second.first][node.second.second] == 9)
{
return node.first;
}
int i = node.second.first;
int j = node.second.second;
dist = node.first;

if (issafe(i - 1, j, a))
{
string str = to_string(i - 1) + "@" + to_string(j);
if (visited.find(str) == visited.end())
{
visited[str] = true;
q.push({dist + 1, {i - 1, j}});
}
}

if (issafe(i, j - 1, a))
{
string str = to_string(i) + "@" + to_string(j - 1);
if (visited.find(str) == visited.end())
{
visited[str] = true;
q.push({dist + 1, {i, j - 1}});
}
}

if (issafe(i, j + 1, a))
{
string str = to_string(i) + "@" + to_string(j + 1);
if (visited.find(str) == visited.end())
{
visited[str] = true;
q.push({dist + 1, {i, j + 1}});
}
}

if (issafe(i + 1, j, a))
{
string str = to_string(i + 1) + "@" + to_string(j);
if (visited.find(str) == visited.end())
{
visited[str] = true;
q.push({dist + 1, {i + 1, j}});
}
}
}
if (finaldist == -1)
{
return -1;
}
return dist;
}


Approach :


we are using BFS here and we know that even if we are traversing
a particular level, the distance will always be incremented by 1
only once, ultimately the distance would be minimum.
and if integer representing the minimum distance traversed to remove the
obstacle else return -1.
Time Complexity:- O(mn)
Space Complexity:- O(mn) // for queue

Amazon โœ…
๐Ÿ‘3
๐Ÿ”” Emtec Off Campus Drive 2022 : Hiring for Freshers as Trainee Software Development Engineer With 4.5 LPA

* Job Role : Trainee Software Development Engineer
* Qualification : BE/B.Tech/MCA/M.Sc
* Batch : 2021 & 2022
* Salary : Rs 4.5 LPA

Apply Here

๐Ÿ“ŒDirect & 100% Ads Free Links
โœ… Share with your friends
1642. Furthest Building You Can Reach
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building i to building i+1 (0-indexed),
If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
*/
class Solution
{
public:
int furthestBuilding(vector<int> &heights, int bricks, int ladders)
{
priority_queue<int> maxB;
int i = 0, diff = 0;
for (i = 0; i < heights.size() - 1; i++)
{
diff = heights[i + 1] - heights[i];
if (diff <= 0)
{
continue;
}
bricks -= diff;
maxB.push(diff);
if (bricks < 0)
{
bricks += maxB.top();
maxB.pop();
ladders--;
}
if (ladders < 0)
break;
}
return i;
}
};

Amazon (leetcode) โœ…
๐Ÿ‘4