🗄️ धडा 02 — Arrays आणि strings: लॉकर्सची रांग

📍 तुम्ही इथे आहात: 12 पैकी धडा 02 · पुढे: lesson-03-linked-lists

📦 या ब्रँचमध्ये काय आहे

धडे 01–02. Python च्या list मागचा structure, तो कशात जलद आणि कशात हळू आहे, आणि मुलाखतीतल्या एक तृतीयांश प्रश्नांची उत्तरे देणारे दोन array patterns.

dsa/algorithms.py — two_sum_sorted, best_window
dsa/demo.py — arrays: एका step मध्ये index, वीस लाख items वर सुरुवातीला insert, एक window, two pointers

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

क्रमांक असलेल्या lockers ची रांग, सगळे समान आकाराचे, शेजारी-शेजारी. locker 17 हवा? थेट तिथे जा — एक step, रांगेत 20 lockers असोत की 2 कोटी, कारण तो कुठे आहे हे तुम्ही मोजू शकता. पण सुरुवातीला एक नवा locker घुसवला तर त्याच्यानंतरचे सगळे एक जागा सरकतात: रांग जितकी लांब, तितकी सरकवासरकवी जास्त. शेवटी जोडणे स्वस्त आहे — रांग भरेपर्यंत; मग काळजीवाहू मोठी रांग बांधतो आणि सगळे हलवतो (क्वचितच, म्हणून सरासरी अजूनही स्वस्त).

🗺️ आकृती

flowchart LR
  L["[0] Aishwarya | [1] Katrina | [2] Dipika | [3] Meera | … | [17] Zoya"]
  L -->|"lockers[17]"| O["one step — O(1)"]
  L -->|"insert(0, x)"| S["everyone shifts — O(n)"]

❓ काय

Array: सलग memory, ठरलेला element आकार → address = base + i × size. Index O(1), append O(1) amortised, मधे insert/delete O(n), search O(n) unsorted / O(log n) sorted.
Python list हा dynamic array आहे; string म्हणजे न बदलणारा (immutable) characters चा array (प्रत्येक बदल copy करतो — list वापरून बनवा आणि ''.join करा).
Two pointers: प्रत्येक टोकाला एक (किंवा दोन्ही पुढे सरकणारे) — sorted array वर two-sum, duplicates काढणे, उलटे करणे, partitioning: O(n), जिथे साधी पद्धत O(n²) असते.
Sliding window: k items ची window पुढे सरकते; नवा item जोडा, जुना काढा — सलग k दिवसांतले सर्वोत्तम, पुनरावृत्ती नसलेली सर्वात लांब substring: O(n).
2-D grids म्हणजे arrays चे arrays: grid[row][col].

🤔 का

Arrays default असतात कारण programs बहुतेक वेळा वाचनच करतात, आणि सलग memory CPUs ना आवडते (caches). कोणती operations O(n) आहेत हे नेमके माहीत असले की list चुकीचे साधन कधी आहे हे कळते — आणि nested loop ऐवजी हे दोन patterns कधी वापरायचे तेही.

🔧 कसे (या repo मध्ये)

two_sum_sorted दोन indices आतल्या दिशेने चालवतो; best_window चालू बेरीज ठेवतो आणि सरकतो. demo.py arrays वीस लाख items वर insert(0, …) आणि append यांचा वेळ मोजतो.

🧪 करून पाहा

python3 dsa/demo.py arrays
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from algorithms import two_sum_sorted, best_window
print(two_sum_sorted([1, 3, 4, 6, 8, 11], 14))        # (1, 5): 3 + 11 — the two monitors met after one step each
print(best_window([2, 1, 5, 1, 3, 2], 3))            # (9, 2): 5 + 1 + 3
s = ""
for i in range(5): s += str(i)                       # each += copies the string: O(n²) in a loop
print(s, "".join(str(i) for i in range(5)))          # join builds once: O(n)
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

lockers[17] = 17 एका step मध्ये; वीस लाख items वर सुरुवातीचा insert milliseconds घेतो तर append microseconds; window चे उत्तर दिवस 1 ला 19; two-sum अशा indices ची जोडी परत करतो ज्यांच्या values ची बेरीज target इतकी होते.

🏁 तुम्ही आत्ताच काय सिद्ध केले

तुम्ही प्रत्येक list operation चा खर्च सांगू शकता, आणि data क्रमाने किंवा रांगेत असेल तेव्हा n² loop ऐवजी two pointers किंवा window वापरू शकता.

⚠️ नेहमीच्या चुका

loop मध्ये list.pop(0) / insert(0, x) — वेषांतर केलेला O(n²); deque वापरा.
loop मध्ये += ने strings बनवणे.
two-sum साठी unsorted array वर two pointers वापरणे. आधी sort करा, किंवा dict वापरा (धडा 05).

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: buffers, batches, rows, pixels, time series — जवळजवळ सगळे array असते, आणि जवळजवळ प्रत्येक hot loop म्हणजे चांगला किंवा वाईट केलेला array pattern.

⏭️ पुढे

धडा 03 — linked lists: खजिन्याचा शोध, जिथे चिठ्ठी जोडणे फुकट आहे आणि शोधणे नाही.

🗄️ Lesson 02 — Arrays & strings: the row of lockers

📍 You are here: Lesson 02 of 12 · Next: lesson-03-linked-lists

📦 What's in this branch

Lessons 01–02. The structure behind Python's list, what it is fast and slow at, and the two array patterns that answer a third of interview questions.

dsa/algorithms.py — two_sum_sorted, best_window
dsa/demo.py — arrays: index in one step, insert-at-front on two million, a window, two pointers

🧒 Explain like I'm 5

A row of numbered lockers, all the same size, side by side. Want locker 17? Walk straight to it — one step, whether the row has 20 lockers or 20 million, because you can compute where it is. But squeeze a new locker in at the front and everyone after it shifts one place: the longer the row, the longer the shuffle. Adding at the end is cheap — until the row is full and the caretaker builds a bigger one and moves everything (rarely, so on average still cheap).

🗺️ Diagram

flowchart LR
  L["[0] Aishwarya | [1] Katrina | [2] Dipika | [3] Meera | … | [17] Zoya"]
  L -->|"lockers[17]"| O["one step — O(1)"]
  L -->|"insert(0, x)"| S["everyone shifts — O(n)"]

❓ What

Array: contiguous memory, fixed element size → address = base + i × size. Index O(1), append O(1) amortised, insert/delete in the middle O(n), search O(n) unsorted / O(log n) sorted.
Python list is a dynamic array; a string is an immutable array of characters (every edit copies — build with a list and ''.join).
Two pointers: one at each end (or both moving forward) — two-sum on a sorted array, removing duplicates, reversing, partitioning: O(n) where the naive way is O(n²).
Sliding window: a window of k items slides along; add the new one, drop the old one — best k consecutive days, longest substring without repeats: O(n).
2-D grids are arrays of arrays: grid[row][col].

🤔 Why

Arrays are the default because reading is what programs mostly do, and contiguous memory is what CPUs love (caches). Knowing exactly which operations are O(n) tells you when a list is the wrong tool — and when to reach for the two patterns instead of a nested loop.

🔧 How (in this repo)

two_sum_sorted walks two indices inward; best_window keeps a running sum and slides. demo.py arrays times insert(0, …) against append on two million items.

🧪 Try it

python3 dsa/demo.py arrays
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from algorithms import two_sum_sorted, best_window
print(two_sum_sorted([1, 3, 4, 6, 8, 11], 14))        # (1, 5): 3 + 11 — the two monitors met after one step each
print(best_window([2, 1, 5, 1, 3, 2], 3))            # (9, 2): 5 + 1 + 3
s = ""
for i in range(5): s += str(i)                       # each += copies the string: O(n²) in a loop
print(s, "".join(str(i) for i in range(5)))          # join builds once: O(n)
EOF

✅ Verify — what you should see

lockers[17] = 17 in one step; the front insert on two million takes milliseconds while append takes microseconds; the window answer is 19 at day 1; two-sum returns a pair of indices whose values add to the target.

🏁 What you just proved

You can name the cost of every list operation and replace an n² loop with two pointers or a window when the data is in order or in a line.

⚠️ Common mistakes

list.pop(0) / insert(0, x) in a loop — O(n²) in disguise; use deque.
Building strings with += in a loop.
Using two pointers on an unsorted array for two-sum. Sort first, or use a dict (lesson 05).

🏭 Why this matters in production: buffers, batches, rows, pixels, time series — nearly everything is an array, and nearly every hot loop is an array pattern done well or badly.

⏭️ Next

Lesson 03 — linked lists: the treasure hunt, where adding a note is free and finding one is not.

← Previouswhy dsa Next →linked lists

This page is the lesson's README from the lesson-02-arrays branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.