testlaa
NEETNEW
Data Structuresadvanced

Advanced Arrays - படிப்படையாக புரிந்துகொள்வோம்

TT
Testlaa Team
May 1, 2026•5 min read

Advanced Arrays என்றால் என்ன?

நீங்கள் ஏற்கனவே தெரிந்திருக்க வேண்டியது:

  • Array traversal
  • Prefix sum
  • Two pointers

இப்போது நாம் கற்றுக்கொள்ளப் போவது:

  • மிகச் சிறந்த answer கண்டுபிடிப்பது
  • Array-இல் உள்ள pattern புரிந்துகொள்வது
  • வேகமான (optimal) முறையில் தீர்ப்பது

1. Maximum subarray sum - maximum_subarray_problem

Problem

ஒரு array-இல் இருந்து continuous subarray ஒன்றை தேர்வு செய்து, அதன் sum அதிகபட்சமாக இருக்க வேண்டும்.

உதாரணம்

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

ஒரு சரியான உதாரணம்:

[4, -1, 2, 1] → sum = 6

எளிய யோசனை

ஒவ்வொரு இடத்திலும்:

  • Previous subarray-ஐ தொடருவது நல்லதா?
  • அல்லது இப்போது புதிய ஆரம்பம் செய்வதா?

Kadane algorithm

def max_subarray_sum(nums):
    best = nums[0]
    curr = nums[0]

    for i in range(1, len(nums)):
        curr = max(nums[i], curr + nums[i])
        best = max(best, curr)

    return best

Step-by-step

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

ஆரம்பம்: curr = -2, best = -2

  • 1 → curr = 1 → best = 1
  • -3 → curr = -2 → best = 1
  • 4 → curr = 4 → best = 4

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

முந்தைய தொடர் உடன் இணைப்பது curr + nums[i]; இப்போதை உறுப்பு மட்டும் தேர்வு nums[i] - இரண்டில் மேலானது max(nums[i], curr + nums[i]); இதுவே Kadane (negative எண்கள் இருக்கும்போது trace முக்கியம்).

Time complexity

O(n)

2. Peak detection - peak_detection

Peak என்றால் என்ன?

ஒரு element அதற்கு முன் மற்றும் பின் உள்ள neighbor values-களை விட பெரியதாக இருந்தால் அது ஒரு peak (முனை index-களில் boundary விதிகள் கொடுப்பவை மாறலாம்).

உதாரணம்

nums = [1, 3, 2, 5, 4]

Peaks: 3, 5

Check முறை

def is_peak(nums, i):
    if i > 0 and nums[i] <= nums[i - 1]:
        return False
    if i < len(nums) - 1 and nums[i] <= nums[i + 1]:
        return False
    return True

பயன்பாடு

  • Local maximum கண்டுபிடிக்க
  • சில optimization / binary search பாணி கேள்விகளில்

3. Selection algorithm (k-th element) - selection_algorithm

Problem

k-th smallest element (sort செய்த பிறகு 1-based வரிசை) கண்டுபிடிக்க.

உதாரணம்

nums = [7, 2, 5, 3]
k = 2

Sorted:

[2, 3, 5, 7]

Answer:

3

எளிய முறை

nums_sorted = sorted(nums)
print(nums_sorted[k - 1])

மேம்பட்ட யோசனை (quickselect)

  • Pivot தேர்வு செய்
  • Array-ஐ partition செய்
  • k எந்த பக்கம் விழுகிறதோ அந்த பக்கம் மட்டும் தேடு

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

முழு array முழு sort அவசியமில்லை - தேவையான rank அடக்கிய பகுதி போதும்.

Time complexity (average)

O(n)

4. Sequence detection - sequence_detection

Problem

ஒரு sequence order-ஆ இருக்கிறதா (சாதாரணமாக subsequence அடுக்குகளுக்குக் அருகிலும் அதே கேள்வி)?

உதாரணம்

arr = [1, 3, 5, 7, 9]
target = [3, 7]

Answer:

True

Solution

def is_subsequence(arr, target):
    j = 0

    for x in arr:
        if j < len(target) and x == target[j]:
            j += 1

    return j == len(target)

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

  • Order முக்கியம்
  • Continuous அமைய வேண்டும் என்பது வலுக்கட்டாயம் அல்ல (gap இருக்கலாம்)

Time complexity

O(len(arr))

5. Sequence counting - sequence_counting

Problem

எத்தனை valid sequences (பொதுவாக continuous subarrays) ஒரு நிபந்தனை-ஐ பூர்த்தி செய்கின்றன - இருக்கிறதா இல்லையா மட்டும் அல்ல.

பொதுவான pattern: run நீட்டித்து total-இல் சேர்

Array-ஐ ஒருமுறை scan:

  • pattern தொடர்ந்து valid என்றால் run counter-ஐ நீட்டி
  • pattern முறிந்தால் reset
  • ஒவ்வொரு valid extension-க்கும் total-இல் கூட்டு (கேள்விக்கு ஏற்ப விதி மாறும்)

முந்தைய valid முடிவுகள் total,-இல் ஏற்கனவே சேர்ந்துவிடும் - மீண்டும் முழு array scan தேவையில்லை.

உதாரணம்: arithmetic subarrays (நீளம் ≥ 3)

Continuous slice valid ஆகும் என்பதற்கு நீளம் ≥ 3 மற்றும் அடுத்தடுத்த same difference:

nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]

def count_arithmetic_slices(nums):
    if len(nums) < 3:
        return 0

    run = 0
    total = 0

    for i in range(2, len(nums)):
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
            run += 1
            total += run
        else:
            run = 0

    return total


nums = [1, 2, 3, 4]
print(count_arithmetic_slices(nums))  # 3

3 என்பது [1, 2, 3], [2, 3, 4], [1, 2, 3, 4] ஆகிய slice-கள்.

detection vs counting

  • sequence_detection → True / False
  • sequence_counting → எண் (எத்தனை valid)

Time complexity

O(n)

6. Sequence reconstruction - sequence_reconstruction

Problem

கொடுக்கப்பட்ட தகவலின் அடிப்படையில் original order அல்லது array மீண்டும் உருவாக்க வேண்டும்.

உதாரணம் (a before b style)

உதாரணம் விதிகள்:

“a before b”, “b before c”

விளைவு அடுக்குகள் உதாரணம்:

a → b → c

(விவரமான topological order அமைத்தல் தொடர் பயிற்சிக்குத் தனிப் பாட உள்ளடக்கத்தில் அடங்கும்.)

மற்றொரு உதாரணம்

arr = [1, 2, 3, 4]

Reverse செய்தால்:

[4, 3, 2, 1]

Reconstruction என்பது சில சமயத்தில் inverse operation செய்வது போன்றது (மீண்டும் reverse) → பழைய அமைவு கிடைக்கும்.

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

  • விதிகளைத் தொடர்ந்து பின்பற்ற செய்வது (constraints)
  • Step-by-step விடையைத் திரட்டுவது (build)

அனைத்து concepts இணைப்பு

Concept பயன்பாடு
Maximum subarray மிக பெரிய continuous sum
Peak detection Local maximum
Selection k-th element
Sequence detection Pattern check (order)
Sequence counting எத்தனை valid sequences (பொதுவாக incremental run)
Sequence reconstruction Order/array உருவாக்கம்

பொதுவான பிழைகள்

  • Subarray vs subsequence குழப்பம்
  • k-th index off-by-one
  • Kadane negative numbers இருக்கும் போது edge கையாளவும் trace செய்யவும்
  • Edge cases (empty) கண்டுகொள்ளாது

பயிற்சி

  • Kadane trace செய்யுங்கள்
  • Peaks கண்டுபிடியுங்கள்
  • k-th smallest கண்டுபிடியுங்கள்
  • Subsequence check செய்யுங்கள்
  • சிறிய array-இல் arithmetic subarrays எண்ணுங்கள்
  • Order reconstruct சிந்தனை செய்யுங்கள்

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

Advanced arrays என்பது:

  • Smart thinking
  • Unnecessary work இலக்குக்குக் குறைப்பது
  • Patterns கண்டுகொள்வது

Continue here:

/resources/arrays/special-cases

Tags:

ArraysAdvancedBeginner Friendly