Advanced Arrays - Step by Step Understanding

What does “Advanced Arrays” mean?

At this stage, you already know:

• How to traverse arrays
• How to use prefix sums
• How to use two pointers

Now we move to:

• Finding the best possible answer
• Understanding patterns inside arrays
• Solving problems in optimal time

---

1. Maximum subarray sum - maximum_subarray_problem (very important)

Problem

Find a continuous subarray with the maximum sum.

Example

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

Possible subarrays include:

[4, -1, 2, 1] → sum 6 (maximum).

Simple thinking

At each position, ask:

• Should I continue the previous subarray?
• Or start a new one?

Kadane's 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 example

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

Start: curr = -2, best = -2

Step	Calculation	curr	best
1	curr = max(1, −2 + 1) = max(1, −1) = **1**	1	1
−3	curr = max(−3, 1 + (−3)) = **−2**	−2	1
4	curr = max(4, −2 + 4) = **4**	4	4

Key idea

If the running sum becomes bad enough that starting fresh beats extending, Kadane resets the extension via max(nums[i], curr + nums[i]).

Time complexity: O(n)

---

2. Peak detection - peak_detection

What is a peak?

An element is a peak if it is greater than its neighbors.

Example

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

Peaks:

• 3 (index 1)
• 5 (index 3)

Simple 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

Why important?

• Optimization problems (local maximum)
• Binary search on unimodal / mountain-style arrays

---

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

Problem

Find the k-th smallest element (1-based rank after sorting).

Example

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

Sorted → [2, 3, 5, 7]

Answer → 3

Simple approach

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

Better idea (quickselect concept)

• Pick a pivot
• Partition the array (like partitioning in quicksort)
• Recurse only into the side that can contain the k-th answer

Intuition

You do not need full sorting - only the bucket containing rank k.

Time complexity (average): O(n)

---

4. Sequence detection - sequence_detection

Problem

Check whether a sequence appears in order (often as a subsequence).

Example

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

Answer: True

Approach

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)

Key idea

Move forward on arr, extend target matches in order.

Time complexity: O(len(arr))

---

5. Sequence counting - sequence_counting

Problem

Count how many valid sequences appear - often contiguous subarrays that satisfy a rule - not just whether one exists.

A common pattern: grow a run, add to total

Walk the array once:

• If the current step keeps the pattern valid, extend a small running counter
• If the pattern breaks, reset the counter
• Add the running counter to a grand total whenever you extend (or at each index - depends on the exact rule)

Past valid endings are already captured in total, so you do not re-scan from scratch.

Example: arithmetic subarrays (length ≥ 3)

A contiguous slice counts if it has length ≥ 3 and every adjacent step has the 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

Those 3 counted slices are [1, 2, 3], [2, 3, 4], [1, 2, 3, 4].

How this differs from detection

• sequence_detection → True / False (does a pattern exist?)
• sequence_counting → a number (how many valid patterns?)

Time complexity

O(n)

---

6. Sequence reconstruction - sequence_reconstruction

Problem

Rebuild an array or ordering from pieces of information.

Example (ordering rules)

You are given pairs: “a comes before b”.

Goal: find one correct order.

Simple thinking

• Use rules
• Build the answer step by step (topological intuition - full treatment is separate)

Another example (reverse operation)

arr = [1, 2, 3, 4]

After reverse:

[4, 3, 2, 1]

Reconstruction can mean undo known operations (inverse steps).

Key idea

Follow constraints and build explicitly - avoid guessing all permutations.

---

How all concepts connect

Concept	Purpose
Maximum subarray	Best continuous segment
Peak detection	Local maximum / structure for search tricks
Selection	k-th order statistic
Sequence detection	Pattern exists in order (subsequence style)
Sequence counting	How many valid sequences (often incremental run counting)
Sequence reconstruction	Build order from clues / inverse ops

---

Common mistakes

• Confusing subarray vs subsequence
• Off-by-one in k-th (0-based vs 1-based)
• Kadane with edge cases (single element / all negatives)
• Ignoring empty array (define behavior)

---

Practice questions

• Trace Kadane's on a printed array row
• Find all peaks manually
• Find k-th largest (variant: k from sorted descending end)
• Check subsequence with mismatched tails
• Count arithmetic subarrays on a small handwritten array
• Reconstruct array from listed operations

---

Final understanding

Advanced arrays is about:

• Thinking smart
• Avoiding unnecessary work
• Using patterns

Continue here:

/resources/arrays/special-cases