समस्या
JavaScript फ़ंक्शन जो पहले और एकमात्र आर्गुमेंट के रूप में संख्याओं का एक 2-D सरणी लेता है।
हमारे फ़ंक्शन को 2-D सरणी से पथ खोजने चाहिए जिसमें प्रत्येक पंक्ति से ठीक एक तत्व चुना जाए, और आसन्न पंक्तियों से चुने गए कोई भी दो तत्व एक ही स्तंभ में न हों। इन सभी पथों में से, हमारे फ़ंक्शन को उस पथ का योग वापस करना चाहिए जिसका योग न्यूनतम हो।
उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -
const arr = [ [4, 7, 1], [2, 8, 3], [5, 6, 9] ]
तो आउटपुट होना चाहिए -
const output = 9;
आउटपुट व्याख्या
क्योंकि सभी वैध पथ हैं -
| 4, 8, 9 | 4, 8, 6 | 4, 3, 6 | 4, 3, 5 |
| 7, 2, 6 | 7, 2, 9 | 7, 3, 6 | 7, 3, 5 |
| 1, 2, 6 | 1, 2, 9 | 1, 8, 9 | 1, 8, 5 |
और इन सभी में से, [1, 2, 6] का योग सबसे कम 9 है।
उदाहरण
इसके लिए कोड होगा -
const arr = [
[4, 7, 1],
[2, 8, 3],
[5, 6, 9]
]
const minimumPathSum = (arr = []) => {
let first = [0, null];
let second = [0, null];
for(let row = arr.length - 1; row >= 0; row--){
let curr1 = null;
let curr2 = null;
for(let column = 0; column < arr[row].length; column++){
let currentSum = arr[row][column];
if(column !== first[1]){
currentSum += first[0];
}else{
currentSum += second[0];
};
if(curr1 === null || currentSum < curr1[0]){
curr2 = curr1;
curr1 = [currentSum, column];
}else if(curr2 === null || currentSum < curr2[0]){
curr2 = [currentSum, column];
};
};
first = curr1;
second = curr2;
};
return first[0];
};
console.log(minimumPathSum(arr));
आउटपुट
कंसोल में आउटपुट होगा -
9