Leetcode 909 Snakes and Ladders | Google Meta | Backtracking template | SDE Sheet below

Here is the solution to "Snakes and Ladders " leetcode question. Hope you have a great time going through it.
🎉Question:leetcode.com/problems/snakes-...
👉 Solution : github.com/Sunchit/Coding-Dec...
🔴 Connect with me here:
🔅Telegram Link for Chrome: telegram.me/codingdecoded
🔅Telegram Link for phone : t.me/codingdecoded
🔅My Linkedin(Sunchit Dudeja): bit.ly/3Qnk0L0
🔅Linkedin: bit.ly/3n65udU
🔅Don't click: bit.ly/32XIXbU
🔅Insta: bit.ly/31TV5ur
🔅 Twitter: / sunchitdudeja
------------------------------------------------------------------------------------------------------------------------------------------------
Success Stories/Placement Diaries: • Playlist
------------------------------------------------------------------------------------------------------------------------------------------------
Master Data Structures and algorithms 🔽🔽🔽🔽
🔴 Coding Decoded SDE revision Sheet: bit.ly/3MG7d4D
🔥 Coding Decoded Binary Search TreeMap revision Sheet: bit.ly/3kUsiMa
🔥 Coding Decoded Trie revision Sheet: bit.ly/392YOJH
🔥 Coding Decoded Graph SDE sheet: bit.ly/3sfp8H4
🔥 Coding Decoded Stacks/Monotonic Stacks sheet: bit.ly/38tm0Ri
🔥 Coding Decoded Bit Manipulation sheet:bit.ly/3LkVNSe
🔥 Coding Decoded Backtracking SDE sheet: bit.ly/3FCzMwQ
🔥 Coding Decoded DP SDE sheet: bit.ly/38HgY3E
🔥 Coding Decoded Heaps SDE Sheet: bit.ly/3GQqBK7
🔥 Coding Decoded Maps/Sets SDE Sheet: bit.ly/3xfBemu
🔥 Coding Decoded Two Pointer SDE Sheet: bit.ly/3trJCwX
🔥🔥🔥🔥👇👇👇 For discussion/feedback/humour/doubts/new openings
Feel free to join discord / discord
🔴 Checkout the series:
👉 Leetcode Interview experiences and tips : • Playlist
👉 Leetcode contests: www.youtube.com?list=PLEI-q7w3s9gRwAEYzYkvVTsYHDi2-ffdL
👉 Leetcode System Design: • System Design
👉 Leetcode LinkedList: • Coding Decoded LinkedL...
👉 Leetcode Stack: • Coding Decoded Stack S...
👉 Leetcode Binary Search: • Coding Decoded BinaryS...
👉 Leetcode Tree: • Coding Decoded Tree Se...
👉 Leetcode Dyanmic Programming: • Coding Decoded Dynamic...
👉 Leetcode Hard: • LeetCode Hard Problems
👉 Leetcode Heap: • Coding Decoded Heap Se...
👉 Building Coding Aptitude: • Building Coding Aptitude
👉 Leetcode Map: • Coding Decoded Map Ser...
👉 Leetcode Two Pointer: • Coding Decoded Two Poi...
👉 Leetcode Backtracking: • Leetcode Backtracking ...
👉 Leetcode Graph Traversal: • Coding Decoded Graph T...
👉 Leetcode Trie: • Coding Decoded Trie Se...
👉 Leetcode Union Find: • Coding Decoded Union F...
👉 Leetcode BFS Graph Problems: • Coding Decoded BFS Ser...
👉 Leetcode Matrix Problems: • Coding Decoded Matrix ...
👉 Leetcode Easy: • Leetcode Easy Problems
👉 Leetcode Bit Manipulation: • Coding Decoded Bit Man...
✨ Hashtags ✨
#CodingDecoded #ProductBased #SoftwareEngineering #FAANGM #FAANG #NSIT #NSUT #engineering #internship #college #Freshers #amazon #apple #coding #algorithms #programming #LearnCoding​ #CodingPractice #leetcode #college #Jee #engineering #leetcode #UseLeetcodeEffectively #dailychallenge
#CareerSwami #Freshers #lifeatmicrosoft #microsoft #softwareengineering #lifeatoci #ocicompensation #ocisalary #softwareengineeringexperience
#dsa #coding #gate #coding #jeemains #iit #jeemains2022 #inspiration #india #firstvlog #motivation
#dsa #datastructure #dsapatterns #google #amazon #amazonsde #softwareengineering #codinginterview #codinginterviewquestions #binarysearch
#microfrontends #frontenddeveloper #softwareengineer
#recession #layoffs #SoftwareIndustry

[@CostaKazistov]

Excellent walkthrough of LC 909

[@vineetsaini8399]

Finally, Thanks for the Nice explanation.

[@CodeWithSunchitDudeja]

You're welcome!

[@Bibhukalyan_iitkgp_21]

excellent explanation

[@krateskim4169]

Awesome explanation bro

[@phoenix_1_3]

thanks a lot bro. from mrng, i was struggling with this prblm, even after watching other videos and solutions in leetcode, i was unclear with the solution code. great explanation.
And one small request, it would be great if you tell the time and space complexity for your code along with the reason of it

[@CodeWithSunchitDudeja]

You are most welcome

[@LemonCoders1]

My Notes:
1. This can be implemented using queue. (BFS)
2. add 1 to the queue and mark visited[n-1][0]=1;
Formula to convert the number in board to board[i][j]
Build this formula by taking few examples.
1 => (n-1,0)
2 => (n-1,1)
6 => (n-1,n-1)
7 => (n-2,n-1)
12 => (n-2,0)
13 =>(n-3,0)
pair findCoordinates(x,n)
{
x--;
int row=n-1-x/n;
int col=x%n;;
if((x/n)&1)
{
col=n-1-col;
}
return {row,col};
}
3. let size=q.size(). Pop the front element of the queue (let pos=1)
4. then iterate through dice=(1 to 6) and add (let x=pos+dice)
let k=findCoordinates(x,n);
push (board[k.first][k.second]) into queue if -1 then push (pos+dice).
5. Do this until size is 0.
6. if size==0 then ans++;
Repeat from step 3 until q is empty.
Return ans;

[@jayneversettle]

this question should be in hard it's like above average of medium category

[@LemonCoders1]

C++ Code
class Solution {
public:
pair findCoordinates(int x,int n) {
x--;
int row=n-1-x/n;
int col=x%n;
// If row is odd then the numbers are reverse in order.
if((x/n)&1)
{
col=n-1-col;
}
return {row,col};
}
int snakesAndLadders(vector& board) {
// It is a nxn board.
int n=board.size();
// Initialize visited array and push 1 to the queue.
vector visited(n,vector(n,0));
visited[n-1][0]=1;
queue q;
q.push(1);
int ans=0;
// Start BFS.
while(!q.empty())
{
int size=q.size();
// If all numbers in queue is used then we have taken one step so ans++
while(size>0)
{
size--;
int curr=q.front();
q.pop();
for(int dice=1;dice