आधुनिक सॉफ्टवेयर इंजीनियरिंग में समस्या समाधान पर हमारी ब्लॉग श्रृंखला में आपका फिर से स्वागत है!

भाग 1 में, हमने फ़्रीक्वेंसी काउंटर पैटर्न की खोज की, जो तत्वों की आवृत्ति को कुशलतापूर्वक गिनकर एल्गोरिदम को अनुकूलित करने की एक शक्तिशाली तकनीक है। यदि आप इसे चूक गए हैं या त्वरित पुनश्चर्या चाहते हैं, तो जारी रखने से पहले बेझिझक इसे जांच लें।

इस भाग में, हम एक और आवश्यक पैटर्न में गोता लगाएंगे: मल्टीपॉइंटर पैटर्न। यह पैटर्न उन परिदृश्यों से निपटने में अमूल्य है जहां एक साथ कई तत्वों की तुलना, खोज या ट्रैवर्स की आवश्यकता होती है। आइए जानें कि यह कैसे काम करता है और आप अपने कोड की दक्षता में सुधार के लिए इसे कहां लागू कर सकते हैं।

02. मल्टीपॉइंटर पैटर्न

मल्टीपॉइंटर पैटर्न एल्गोरिदम डिज़ाइन में उपयोग की जाने वाली एक तकनीक है जहां सरणियों या लिंक की गई सूचियों जैसी डेटा संरचनाओं को पार करने के लिए एकाधिक पॉइंटर्स (या इटरेटर) को नियोजित किया जाता है। एकल पॉइंटर या लूप पर भरोसा करने के बजाय, यह पैटर्न दो या दो से अधिक पॉइंटर्स का उपयोग करता है जो अलग-अलग गति से या अलग-अलग शुरुआती बिंदुओं से डेटा के माध्यम से आगे बढ़ते हैं।

उदाहरण समस्या

sumZero नामक एक फ़ंक्शन लिखें जो पूर्णांकों की सॉर्टेड सरणी स्वीकार करता है। फ़ंक्शन को पहली जोड़ी ढूंढनी चाहिए जहां योग शून्य है। यदि ऐसी कोई जोड़ी मौजूद है, तो एक सरणी लौटाएँ जिसमें दोनों मान शामिल हों; अन्यथा, अपरिभाषित लौटें।

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

बुनियादी समाधान

function sumZero(arr){
    for (let i = 0; i 



समय जटिलता - O(N^2)

मल्टीपॉइंटर पैटर्न का उपयोग कर समाधान

चरण 1: समस्या को समझें

हमें **सॉर्टेड सरणी में दो संख्याएं ढूंढनी होंगी जिनका योग शून्य हो। चूंकि सरणी क्रमबद्ध है, हम समाधान को अधिक कुशलता से खोजने के लिए इस आदेश का लाभ उठा सकते हैं।

चरण 2: दो पॉइंटर्स प्रारंभ करें

दो पॉइंटर्स सेट करें: एक (बाएं) सरणी की शुरुआत से शुरू होता है, और दूसरा (दाएं) अंत से शुरू होता है।

उदाहरण:



Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




चरण 3: पॉइंटर्स पर मानों के योग की गणना करें

योग प्राप्त करने के लिए बाएँ और दाएँ पॉइंटर्स पर मान जोड़ें



Sum = -4   5 = 1




चरण 4: योग की तुलना शून्य से करें

• यदि योग शून्य से अधिक है: योग को कम करने के लिए दाएं सूचक को एक कदम बाईं ओर ले जाएं।

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• यदि योग शून्य से कम है: योग बढ़ाने के लिए बाएं सूचक को एक कदम दाईं ओर ले जाएं।

New Sum = -4   2 = -2
Sum is -2 



चरण 5: प्रक्रिया दोहराएं

पॉइंटर्स को हिलाना और योग की गणना करना तब तक जारी रखें जब तक कि वे मिल न जाएं या कोई जोड़ी न मिल जाए।



New Sum = -3   2 = -1
Sum is -1 



योग शून्य है, इसलिए फ़ंक्शन रिटर्न [-2, 2] देता है।

यदि लूप ऐसी जोड़ी को ढूंढे बिना पूरा हो जाता है, तो अपरिभाषित वापस लौटें।

अंतिम कोड



function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




टिप्पणी:

समय जटिलता: O(n) - फ़ंक्शन कुशल है और सरणी के आकार के साथ रैखिक रूप से स्केल करता है।

अंतरिक्ष जटिलता: O(1) - फ़ंक्शन न्यूनतम मात्रा में अतिरिक्त मेमोरी का उपयोग करता है।

निष्कर्ष

मल्टीपॉइंटर पैटर्न समस्याओं को हल करने के लिए एक शक्तिशाली तकनीक है जिसमें क्रमबद्ध डेटा संरचना में तत्वों को खोजना, तुलना करना या हेरफेर करना शामिल है। एक-दूसरे की ओर बढ़ने वाले कई पॉइंटर्स का उपयोग करके, हम कई मामलों में समय जटिलता को O(n²) से O(n) तक कम करके, एल्गोरिदम की दक्षता में काफी सुधार कर सकते हैं। यह पैटर्न बहुमुखी है और इसे कई प्रकार की समस्याओं पर लागू किया जा सकता है, जिससे यह आपके कोड में प्रदर्शन को अनुकूलित करने के लिए एक आवश्यक रणनीति बन जाती है।

हमारी अगली पोस्ट के लिए बने रहें, जहां हम गतिशील डेटा सेगमेंट से जुड़ी समस्याओं से निपटने के लिए एक और आवश्यक उपकरण स्लाइडिंग विंडो पैटर्न के बारे में जानेंगे। यह एक अविश्वसनीय रूप से उपयोगी पैटर्न है जो आपको और भी जटिल चुनौतियों को आसानी से हल करने में मदद कर सकता है!