Subarrays - அடிப்படையில் இருந்து புரிந்துகொள்வோம்

Subarray என்றால் என்ன?

ஒரு array-இல் உள்ள values-இல் இருந்து தொடர்ச்சியாக (continuous) எடுத்த பகுதி தான் subarray.

உதாரணம்:

nums = [10, 20, 30]

இந்த array-இல் இருந்து கிடைக்கும் subarrays:

• [10]
• [20]
• [30]
• [10, 20]
• [20, 30]
• [10, 20, 30]

முக்கிய விதி

Subarray எப்போதும் தொடர்ச்சியான (continuous) values ஆக இருக்க வேண்டும்.

இது subarray அல்ல:

• [10, 30] (நடுத்தில் 20 இல்லை)

---

Subarray எப்படி உருவாக்கப்படுகிறது?

நாம் இரண்டு விஷயங்களை தேர்வு செய்கிறோம்:

• தொடக்க இடம் (start index) → l
• முடிவு இடம் (end index) → r

அதற்குள் உள்ள அனைத்தும் subarray.

nums = [10, 20, 30, 40]

l = 1
r = 3

Subarray:

[20, 30, 40]

---

Subarray Length

Formula:

length = r - l + 1

உதாரணம்:

l = 1
r = 3

length = 3 - 1 + 1 = 3

---

Subarray indexing - subarray_indexing

Subarray indexing என்பது: continuous window-ஐ வரையறுக்கும் இரண்டு boundary index-களை (l, r) தெளிவாக வைத்து நிர்வகிப்பது.

இரண்டு எல்லைகள் (inclusive)

• l → subarray-இன் முதல் index (உட்பட)
• r → subarray-இன் கடைசி index (உட்பட)

l முதல் r வரை (இரண்டும் உட்பட) தான் subarray.

நீளம்

length = r - l + 1

Python: loop vs slice (off-by-one)

range மற்றும் slice-இன் முடிவு exclusive ஆகும்:

for i in range(l, r + 1):
    print(nums[i])

window = nums[l : r + 1]

தவறாக nums[l:r] எழுதினால் nums[r] விடுபடும்.

செல்லுபடியான bounds

n = len(nums) என்றால் பொதுவாக:

0 <= l <= r < n

l > r என்பது காலி window - சில algorithms-இல் தொடக்க நிலை; problem என்ன எதிர்பார்க்கிறது என்பதை தெளிவாக்கவும்.

Algorithms-இல் boundaries நிர்வாகம்

• Enumerate: l நிலையாக, r ஐ l முதல் n-1 வரை நகர்த்துதல்
• Sliding window: நிபந்தனை முறிந்தால் l முன்செல், அனுமதித்தால் r நீட்டி

l மற்றும் r இரண்டும் inclusive என்ற ஒரே முறையை பின்பற்றினால் off-by-one பிழை குறையும்.

---

அனைத்து Subarrays-ஐ உருவாக்குவது

nums = [1, 2, 3]

for l in range(len(nums)):
    for r in range(l, len(nums)):
        print(nums[l:r+1])

விளக்கம்

• முதல் loop → தொடக்கம் l
• இரண்டாவது loop → முடிவு r

இதனால் அனைத்து subarrays கிடைக்கும்.

---

Subarray sum analysis - subarray_sum_analysis

Subarray sum analysis என்பது: l மற்றும் r நகரும்போது sum எப்படி மாறுகிறது என்பதை புரிந்து, பிரச்சினைக்கு போதுமான வேகமான முறையை தேர்வு செய்வது.

உதாரணம் (சிறிய array)

nums = [1, 2, 3]

Subarrays மற்றும் sum:

• [1] → 1
• [1, 2] → 3
• [1, 2, 3] → 6
• [2] → 2
• [2, 3] → 5
• [3] → 3

ஒரு (l, r)-க்கு நேரடி loop

l = 0
r = 2

s = 0
for i in range(l, r + 1):
    s += nums[i]

print(s)

நிலை 1 - naive முறை (மெதுவானது)

மூன்று nested loop: ஒவ்வொரு (l, r)-க்கும் l முதல் r வரை மீண்டும் கூட்டுதல்:

nums = [1, 2, 3]
n = len(nums)

for l in range(n):
    for r in range(l, n):
        s = 0
        for i in range(l, r + 1):
            s += nums[i]
        # s-ஐ analyze செய்யலாம்

அனைத்து windows-க்கும் சுமார் O(n³) - சிறிய n-க்கு மட்டும் பொருத்தமானது.

நிலை 2 - r நீட்டும்போது s += nums[r] (மிக மேம்பட்டது)

l நிலையாக இருக்கும்போது r ஒரு படி அதிகரித்தால் sum-இல் nums[r] மட்டும் சேர்க்கப்படும்.

nums = [1, 2, 3]
n = len(nums)

for l in range(n):
    s = 0
    for r in range(l, n):
        s += nums[r]
        # nums[l … r] sum = s

இது பொதுவாக O(n²) enumeration template.

new_sum = old_sum + nums[r]

நிலை 3 - array மாறாது, பல range-sum கேள்விகள் (prefix sum)

Array static-ஆக இருந்து பல முறை “l முதல் r வரை sum?” என்றால்:

• Prefix sum ஒருமுறை O(n)-இல் கட்டு
• ஒவ்வொரு query-யும் O(1)-இல் subtraction மூலம்

விரிவான பாடம்:

/resources/arrays/prefix-sum

சிந்தனை

Analysis = சரியான கருவி:

• மீண்டும் மீண்டும் கூட்டல் → எளிது, பொதுவாக O(n³)
• s += nums[r] → O(n²) enumeration
• Prefix sums → repeated range sums-க்கு சிறந்தது

---

Subarrays எண்ணிக்கை (Counting)

சில கேள்விகளில்:

“எத்தனை subarrays condition satisfy செய்கிறது?” என்று கேட்கப்படும்.

உதாரணம்: sum > 3 உள்ள subarrays எண்ணிக்கை

nums = [1, 2, 3]

count = 0

for l in range(len(nums)):
    s = 0
    for r in range(l, len(nums)):
        s += nums[r]
        if s > 3:
            count += 1

print(count)

---

Longest Subarray

சில கேள்விகளில்:

“Condition satisfy செய்யும் மிக நீளமான subarray எது?” என்று கேட்கப்படும்.

nums = [1, 2, -1, 2, 3]

யோசனை

• இடது பக்கம் இருந்து தொடங்கு
• வலது பக்கம் விரிவு செய்
• condition உடைந்தால் → இடது பக்கம் நகர்த்து

இந்த அணுகுமுறை பின்னர் sliding window என அழைக்கப்படும்.

---

முக்கிய புரிதல்

Subarray:

• எப்போதும் continuous
• (l, r) மூலம் வரையறுக்கப்படும் (inclusive indexing - subarray_indexing)

பயன்பாடு:

• Sum analysis (subarray_sum_analysis) - sum-ஐ வேகமாக கணக்கிட / ஒப்பிட / எண்ண
• count செய்ய
• longest segment கண்டுபிடிக்க

---

பொதுவான தவறுகள்

• subarray மற்றும் subsequence குழப்பம்
• continuity மறந்து விடுதல்
• nested loops-இல் ஒவ்வொரு window-க்கும் மீண்டும் முழு கூட்டல் (O(n³) பொதுவான வலை) - s += nums[r] போதுமான இடத்தில்
• nums[l:r] மற்றும் nums[l:r+1] குழப்பம்

---

பயிற்சி

• [2, 4, 6] இன் அனைத்து subarrays-ஐ எழுதுங்கள்
• sum > 5 உள்ள subarrays எண்ணிக்கை
• மூன்று nested sum loop-ஐ s += nums[r] முறையாக மாற்றி ஏன் வேகம் அதிகம் என்று விளக்கவும்
• length = 2 உள்ள subarrays
• l, r கொடுத்தால் nums[l:r+1] print செய்து length = r - l + 1 சரிபார்க்க
• positive numbers மட்டும் உள்ள longest subarray

---

இறுதி கருத்து

Subarray பிரச்சினைகள் சிக்கலாக தோன்றலாம்.

ஆனால் எப்போதும்:

1. தொடக்கம் தேர்வு செய்
2. முடிவு தேர்வு செய்
3. condition பயன்படுத்த

இந்த மூன்று படிகள் போதுமானது.