← कोर्सच्या मुख्य पानाकडे परत

⏮️ आधी काय होते & फायदे-तोटे

प्रत्येक साधनाने काहीतरी वाईट गोष्ट बदलली — आणि तेच साधन कुठेतरी चुकीचे ठरते. प्रत्येक मोठ्या कल्पनेसाठी: आधी जीवन कसे होते, प्रामाणिक फायदे ✅ / तोटे ❌, आणि कुठे वापरावी 👍 विरुद्ध कुठे नाही 👎.

🗄️ Array विरुद्ध linked list — धडे 02, 03

⏮️ dynamic arrays आधी

Arrays चा आकार आधीच ठरवावा लागायचा; वाढवणे म्हणजे मोठा array घेऊन copy करणे. वाढू शकणारा container मिळवायचा मार्ग म्हणजे linked lists.

✅ फायदे

  • array: index ने O(1), cache-friendly (contiguous), प्रति item कमी memory
  • linked list: माहीत असलेल्या node वर O(1) insert/remove, मोठी copy कधीच नाही

❌ तोटे

  • array: मध्ये किंवा पुढे घालायला O(n), अधूनमधून O(n) वाढीची copy
  • linked list: i-व्या item पर्यंत O(n), प्रति item एक pointer, cache-विरोधी

👍 वापरा जेव्हा

  • जवळजवळ सगळ्यासाठी arrays (Python lists) — वाचणे, append, sorting
  • queues, LRU caches, सतत पुढे insert साठी linked lists / deque

👎 दोनदा विचार करा जेव्हा

  • नेहमी शेवटी insert करत असताना 'insert O(1) आहे' म्हणून linked list
  • loop मध्ये list.pop(0) — ते linked-list चे काम

🗂️ Hash map विरुद्ध balanced tree — धडे 05, 09

⏮️ hashing आधी (1950 चे दशक)

Lookups म्हणजे क्रमबद्ध arrays आणि binary search, किंवा trees; hashing ने क्रमाच्या बदल्यात constant time घेतला.

✅ फायदे

  • hash map: सरासरी O(1) get/put, सगळ्यात साधे API
  • balanced tree: O(log n) पण क्रमबद्ध — range queries, min/max, शेजारी

❌ तोटे

  • hash map: क्रम नाही, वाईट hash सह worst case O(n), rehash चे थांबे
  • tree: हळू constant, जास्त memory, implement करायला कठीण

👍 वापरा जेव्हा

  • lookup, मोजणी, dedupe, caching साठी dict/set
  • 'A ते M मधले सगळे' हवे तेव्हा sorted container / B-tree

👎 दोनदा विचार करा जेव्हा

  • शब्द मोजायला tree
  • 10 सगळ्यात लहान हवे तेव्हा dict

📶 Merge विरुद्ध quick विरुद्ध Timsort — धडा 07

⏮️ O(n log n) sorts आधी

Bubble आणि insertion हेच sorts होते; दहा लाख records ला तास लागायचे, म्हणून data हाताने क्रमात ठेवला जायचा.

✅ फायदे

  • merge: नेहमी O(n log n), stable, parallel होते, linked lists आणि disks वर चालते
  • quick: व्यवहारात सगळ्यात जलद in-place, O(log n) stack
  • Timsort: stable, क्रमबद्ध किंवा जवळजवळ क्रमबद्ध input वर O(n), Python आणि Java जे देतात ते

❌ तोटे

  • merge: O(n) जास्तीची memory
  • quick: adversarial input वर O(n²), stable नाही
  • Timsort: गुंतागुंतीचे — तुम्ही लिहायचे नाही

👍 वापरा जेव्हा

  • sorted() बोलवा — ते Timsort आहे आणि ते बरोबर आहे
  • stability किंवा external sorting महत्त्वाचे तेव्हा merge sort; memory कमी तेव्हा quick sort

👎 दोनदा विचार करा जेव्हा

  • production मध्ये तुमचा स्वतःचा quick sort
  • धड्याशिवाय कशासाठीही bubble sort

🗺️ BFS विरुद्ध DFS — धडा 10

⏮️ graph algorithms प्रमाणित होण्याआधी

प्रत्येक प्रश्नाला स्वतःचा हाताने लिहिलेला search असायचा; दोन नावांनी सगळ्यांना तीच दोन साधने दिली.

✅ फायदे

  • BFS: hops मध्ये सर्वात लहान मार्ग, पातळी-पातळीने, जवळचे आधी सापडते
  • DFS: छोटा code (recursion), cycles, topological order, mazes साठी नैसर्गिक

❌ तोटे

  • BFS: queue मध्ये अख्खी पातळी असू शकते — memory
  • DFS: सर्वात लहान नाही, recursion खोलीची मर्यादा, आधी दूर भटकू शकतो

👍 वापरा जेव्हा

  • 'सगळ्यात कमी पावले', जवळचा शेजारी, level order साठी BFS
  • reachability, cycle detection, क्रम, backtracking साठी DFS

👎 दोनदा विचार करा जेव्हा

  • सर्वात लहान मार्गासाठी DFS
  • दहा लाख रुंद पातळी आणि memory नसलेल्या graph वर BFS

🧠 Memoisation विरुद्ध tabulation — धडा 11

⏮️ DP आधी (Bellman, 1950 चे दशक)

Optimisation चे प्रश्न सगळे शोधून किंवा हाताने सोडवले जायचे; उप-उत्तरे लक्षात ठेवल्याने exponential चे polynomial झाले.

✅ फायदे

  • memoisation: recursion लिहा, dict जोडा — तुम्ही स्पर्श केलेल्या states च सोडवते
  • tabulation: recursion ची खोली नाही, rolling window ने अनेकदा O(1) जास्तीची जागा

❌ तोटे

  • memoisation: recursion च्या मर्यादा, dict चा भार, क्रम दिसायला कठीण
  • tabulation: गरज नसली तरी प्रत्येक state मोजते, क्रम ठरवावा लागतो

👍 वापरा जेव्हा

  • आधी memoise करा — ती तुम्हाला आधीच समजलेली recursion अधिक cache
  • खोली चावते तेव्हा किंवा तक्ता लहान आणि नियमित असेल तेव्हा tabulate करा

👎 दोनदा विचार करा जेव्हा

  • 100,000 खोल memoised recursion
  • 10⁹ cells चा तक्ता

🏃 Greedy विरुद्ध DP — धडा 11

⏮️ greedy निवडीच्या पुराव्यांआधी

Greedy उत्तरे बरोबर दिसायची आणि कधीकधी चुकीची असायची; DP हा सुरक्षित, हळू मार्ग होता.

✅ फायदे

  • greedy: O(n log n) किंवा O(n), छोटा code, memory नाही
  • DP: sub-problems overlap होतात तेव्हा नेहमी बरोबर, 'चुकीची दिसणारी' optima हाताळतो

❌ तोटे

  • greedy: स्थानिक निवड सुरक्षित आहे असा पुरावा असेल तेव्हाच बरोबर (intervals, Huffman, Dijkstra)
  • DP: जास्त वेळ आणि memory, जास्त विचार

👍 वापरा जेव्हा

  • interval scheduling, canonical नाणे-पद्धती, Dijkstra साठी greedy
  • नाणी [1, 3, 4], knapsack, edit distance साठी DP

👎 दोनदा विचार करा जेव्हा

  • [1, 3, 4] ने 6 बनवायला greedy नाणी (3 देते, उत्तर 2)
  • greedy सिद्धपणे सोडवतो त्या प्रश्नासाठी DP

🪆 Recursion विरुद्ध iteration — धडा 06

⏮️ मुख्य भाषांत recursion येण्याआधी

सगळे loops आणि explicit stacks होते; recursion Algol सोबत आली आणि trees आणि divide-and-conquer वाचनीय झाले.

✅ फायदे

  • recursion: रचनेचा आरसा (trees, graphs, nested data); छोटी, सिद्ध करता येणारी
  • iteration: stack ची मर्यादा नाही, call चा भार नाही, पावलोपावली trace करायला सोपी

❌ तोटे

  • recursion: Python ची ~1000-frame मर्यादा, लपलेली memory, काम दोनदा मोजणे सोपे
  • iteration: explicit stack म्हणजे जास्त code; काही algorithms कुरूप होतात

👍 वापरा जेव्हा

  • trees, DFS, merge sort, backtracking, memo ने DP साठी recursion
  • linear काम, खोल किंवा प्रचंड inputs, hot paths साठी loops

👎 दोनदा विचार करा जेव्हा

  • दहा लाख elements च्या list वर recursion
  • 20-node झाड चालायला हाताने बनवलेला stack