Interview Question: Minimum Jumps
Company Interviews Using C++ Data Structures and Algorithms
int minimumJumps(vector<int> &arr, int n)
{
int maxJump = arr[0];
int step = arr [0];
int jump = 1;
if (n == 1) {
return 0;
} else if(arr[0] == 0){
return -1;
}
for (int i = 1; i < n; i++) {
if (i == n - 1) {
return jump;
}
maxJump = max(maxJump, i+arr[i]);
step --;
if(step == 0){
jump++;
if (i >= maxJump) {
return -1;
}
step = maxJump-i;
}
}
}English :
This C++ code defines a function called `minimumJumps` that takes two parameters:
1. `vector<int> &arr`: A reference to a vector of integers, which represents an array containing information about the maximum jump length you can make from each position.
2. `int n`: An integer representing the size of the array `arr`.
The purpose of this function is to determine the minimum number of jumps required to reach the end of the array while considering the maximum jump length from each position. If it’s not possible to reach the end of the array, the function returns -1.
Here’s a step-by-step explanation of how the code works:
1. Initialize some variables:
— `maxJump`: It represents the maximum jump length reachable from the current position. Initially, it’s set to the first element of the array (`arr[0]`).
— `step`: It represents the remaining steps (jumps) you can take within the current maximum jump length. Initially, it’s set to the first element of the array (`arr[0]`).
— `jump`: It starts at 1, as you’ve made the first jump from the starting position.
2. Check for two special cases:
— If the array has only one element (`n == 1`), you’re already at the end, so the function returns 0 because you don’t need any jumps.
— If the first element of the array is 0 (`arr[0] == 0`), it’s not possible to move forward, so the function returns -1.
3. Use a loop to traverse the array from the second element (`i = 1`) to the last element (`i < n`).
4. Inside the loop:
— Update `maxJump` to be the maximum between its current value and `i + arr[i]`, which represents the farthest position you can reach from the current position.
— Decrease `step` by 1 since you’ve used one step to move to the current position.
5. Check if `step` reaches 0. If it does, it means you need to make a new jump because you’ve exhausted your current maximum jump length:
— Increment `jump` to count the jump.
— Check if it’s not possible to go further (`i >= maxJump`). If so, return -1 because there’s no way to reach the end from this point.
— Reset `step` to the difference between the new `maxJump` and the current position (`maxJump — i`).
6. If the loop finishes without reaching the end of the array, the function returns -1 because it’s not possible to reach the end from the given input.
7. If you successfully reach the end of the loop, the function returns the count of jumps stored in the `jump` variable, which represents the minimum number of jumps required to reach the end of the array.
This code implements a common algorithm for solving the “Minimum Jumps to Reach End” problem, which is a typical interview question in computer science and programming interviews.
Hindi :
यह C++ कोड एक फ़ंक्शन `minimumJumps` को परिभाषित करता है जो दो पैरामीटर लेता है:
1. `vector<int> &arr`: एक पूर्णांकों के वेक्टर का संदर्भ, जो प्रत्येक स्थान से आपके पहुंचने की सर्वाधिक कूद की लम्बाई के बारे में जानकारी रखने वाले एक सरणी को प्रतिनिधित करता है।
2. `int n`: एक पूर्णांक जो सरणी `arr` के आकार को प्रतिनिधित करता है।
इस फ़ंक्शन का उद्देश्य सरणी के अंत तक पहुँचने के लिए आवश्यक कम से कम जंप की संख्या निर्धारित करना है, हर स्थान से सर्वाधिक कूद की लम्बाई को ध्यान में रखकर। अगर सरणी के अंत तक पहुंचना संभव नहीं है, तो फ़ंक्शन -1 को वापस करता है।
यहां कोड कैसे काम करता है की एक-एक स्थान पर स्पष्टीकरण है:
1. कुछ चरणों की शुरुआत करें:
— `maxJump`: यह मौजूदा स्थिति से पहुंचे जा सकने वाली सर्वाधिक कूद की लम्बाई को प्रतिनिधित करता है। प्रारंभ में यह सरणी के पहले तत्व (`arr[0]`) पर सेट होता है।
— `step`: यह मौजूदा सर्वाधिक कूद की लम्बाई के भीतर किए गए शेष कदम (छलां) को प्रतिनिधित करता है। प्रारंभ में यह सरणी के पहले तत्व (`arr[0]`) पर सेट होता है।
— `jump`: यह पहली कूद से प्रारंभ होता है, क्योंकि आपने प्रारंभ स्थिति से पहला कूद मारा है।
2. दो विशेष मामलों की जांच करें:
— अगर सरणी में केवल एक तत्व है (`n == 1`), तो आप पहले से ही अंत में हैं, इसलिए फ़ंक्शन 0 को वापस करता है क्योंकि आपको कोई कूद नहीं करने की आवश्यकता नहीं है।
— अगर सरणी का पहला तत्व 0 है (`arr[0] == 0`), तो आगे बढ़ने का योग्य नहीं है, इसलिए फ़ंक्शन -1 को वापस करता है।
3. स्थान से निकलकर सरणी को दौड़ने के लिए एक लूप का उपयोग करें (`i = 1` से लेकर `i < n` तक).
4. लूप के भीतर:
— `maxJump` को उसके मौजूदा मूल्य और `i + arr[i]` के बीच का अधिकतम रखने के लिए अद्यतन करें, जो मौजूदा स्थिति से पहुँचने की दूरतम स्थान को प्रतिनिधित करता है।
— यह क्योंकि आपने मौजूदा स्थिति पर पहुँचने के लिए एक कदम उठाया ह
ै, `step` को 1 से कम करें।
5. यह जांचें कि `step` 0 तक पहुँच गया है। यदि ऐसा होता है, तो इसका मतलब है कि आपको अपनी मौजूदा सर्वाधिक कूद की लम्बाई को उपयोग करके नया कूद मारना है:
— कूद की गणना के लिए `jump` को बढ़ाएं।
— जांचें कि आगे और नहीं जाना संभव है (`i >= maxJump`). यदि हां, तो इस स्थान से अंत में पहुँचने का कोई तरीका नहीं है, इसलिए -1 को वापस करें।
— `step` को नए `maxJump` और मौजूदा स्थिति के बीच के अंतर को फिर से सेट करें (`maxJump — i`).
6. यदि लूप बिना सरणी के अंत तक पहुँचे समाप्त हो जाता है, तो फ़ंक्शन -1 को वापस करता है क्योंकि दिए गए इनपुट से सरणी के अंत तक पहुँचना संभव नहीं है।
7. यदि आप सफलता से लूप के अंत तक पहुँचते हैं, तो फ़ंक्शन `jump` वेरिएबल में संग्रहित की गई कूद की गणना को वापस करता है, जो सरणी के अंत तक पहुँचने के लिए आवश्यक कम से कम कूदों की संख्या को प्रतिनिधित करता है.
यह कोड “अंत तक पहुँचने के लिए न्यूनतम कूद” समस्या को हल करने के लिए एक सामान्य एल्गोरिथम का पालन करता है, जो कंप्यूटर विज्ञान और प्रोग्रामिंग साक्षारों की सामान्य प्रश्नों में एक प्रकार का सामान्य सवाल है।
Hinglish :
Is C++ code hai, jo ‘minimumJumps’ naamak ek function define karta hai, jismein do parameters liye jate hain:
1. `vector<int> &arr`: Ek reference, jismein integers ki ek vector hai, jo har position se kitni adhikatam koodne ki lambai hoti hai, ye darust karta hai.
2. `int n`: Ek integer, jo `arr` vector ki size ko darust karta hai.
Is function ka maksad yeh hai ki har position se maximum koodne ki lambai ko dhyan mein rakhte hue, array ke ant tak pahuchne ke liye kam se kam koodne ki ginti nikale. Agar ant tak pahuchna sambhav nahin hai, to function -1 ko lautata hai.
Neeche code ka kis tarah se kaam karta hai uska kadamrekhaan:
1. Kuch variables ko shuruaat mein taiyar kiya jata hai:
— `maxJump`: Isse prastavit kiya jata hai ki current sthiti se pahuchne ki adhikatam kood ki lambai kya hai. Shuruaat mein isse array ke pehle element (`arr[0]`) se set kiya jata hai.
— `step`: Isse prastavit kiya jata hai ki current adhikatam kood ki lambai ke bheetar aap kitne koodne kar sakte hain. Shuruaat mein isse array ke pehle element (`arr[0]`) se set kiya jata hai.
— `jump`: Yeh 1 se shuruat karta hai, kyun ki aapne shuruaati sthiti se pahla kood mara hai.
2. Do vishesh sthitiyon ka pata lagane ke liye check kiya jata hai:
— Agar array mein sirf ek element hai (`n == 1`), to aap ant mein pahunch chuke hain, isliye function 0 ko lautata hai kyun ki aapko koodna nahin chahiye.
— Agar array ka pehla element 0 hai (`arr[0] == 0`), to aage badhna sambhav nahin hai, isliye function -1 ko lautata hai.
3. Ek loop ka istemal kiya jata hai jisse array ko doosre element (`i = 1`) se lekar ant ke element (`i < n`) tak traverse kiya jata hai.
4. Loop ke bheetar:
— `maxJump` ko uske current maujooda maan aur `i + arr[i]` ke beech mein maximum hone ke liye update kiya jata hai, jo current sthiti se kitni door tak pahunch sakte hain.
5. Check kiya jata hai ki `step` 0 tak pahunch gaya hai ya nahin. Agar pahunch gaya hai, to iska matlab hai ki aapko ek naya koodna mara jana chahiye, kyun ki aapne apni vartaman adhikatam kood ki lambai ka istemal kar liya hai:
— `jump` ko ek kood gintaane ke liye badhaya jata hai.
— Dekha jata hai ki aage nahin badha ja sakta (`i >= maxJump`). Agar haan, to -1 ko lautaya jata hai kyun ki is sthiti se ant tak pahunchna sambhav nahin hai.
— `step` ko naye `maxJump` aur vartaman sthiti ke beech ke antar ( `maxJump — i`) se reset kiya jata hai.
6. Agar loop array ke ant tak pahunchne se pehle khatam ho jata hai, to function -1 ko lautata hai kyun ki di gayi input se ant tak pahunchna sambhav nahin hai.
7. Agar aap loop ko safaltapoorvak ant tak pahunchte hain, to function `jump` variable mein store ki gayi koodne ki ginti ko lautata hai, jo array ke ant tak pahunchne ke liye kam se kam koodne ki ginti ko darust karta hai.
Yeh code “Ant Tak Pahunchne Ke Liye Kam Se Kam Koodne Ki Ginti” samasya ko hal karne ke liye ek aam prakriya ko anukoolit karta hai, jo computer science aur programming ke interview mein aksar pucha jata hai.
