Special Cases in Arrays — Step by Step Understanding

Why “special cases”?

Real arrays are not always 0 … n−1 in a straight line. You also see:

• Wrap-around (circular / rotate tasks)
• Repeated values
• Block reversals
• O(1) extra memory swaps (in-place) instead of allocating a full copy every time.

This lesson maps possibleSkills:

• circular_array_handling
• circular_traversal
• duplicate_handling
• group_reversal
• in_place_modification

---

Circular array handling — circular_array_handling

Treat index i modulo n:len(arr):

def get_circular(nums, i):
    n = len(nums)
    return nums[i % n]

Rotate thinking: i = (start + k) % n stays legal forever.

Example: read second pass of cyclic buffer—same formula.

---

Circular traversal — circular_traversal

Visit every position starting at start, n steps (each index once) even though indices wrap:

def visit_all(nums, start=0):
    n = len(nums)
    for step in range(n):
        i = (start + step) % n
        # use nums[i]

Contrast: iterating for i in range(n) from 0 is only equivalent when start == 0.

Loop detection / tortoise–hare (fast/slow) appear in different tutorials—here we only emphasize bounded circular walks modulo n.

---

Duplicate handling — duplicate_handling

Goals differ:

Goal	Technique sketch
Remove duplicates (sorted)	Two-pointer slow writer (wi) and fast reader (ri)
Frequency map	Count occurrences (hash map)
Pigeon-hole cyclic sort family	Swap each element to “value slot” when range small (careful)

Stable rule: declare whether you must preserve first occurrence, compact array, or return counts only.

Minimal sorted unique compaction pattern:

def dedupe_sorted_inplace(nums):
    if not nums:
        return 0
    wi = 0
    for ri in range(1, len(nums)):
        if nums[ri] != nums[wi]:
            wi += 1
            nums[wi] = nums[ri]
    return wi + 1  # new length conceptual

---

Group reversal — group_reversal

Reverse array by chunks of k (common exercise): reverse inside each block, handle tail.

Triple reverse trick (rotate entire array) reminder:

Reverse first part → reverse second → reverse whole restores rotation

Group reversal usually means explicit reverse(lo, hi) helper swaps until pointers meet inside each [lo, hi] slice.

Pseudo:

def reverse_range(arr, lo, hi):
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1

---

In-place modification — in_place_modification

Requirements often say O(1) auxiliary space:

• Prefer indices + swaps (Dutch partition, cyclic shifts)
• Avoid building new list proportional to n when forbidden

Safety checklist:

• Maintain meaningful invariant per step (partition region grows correctly).
• Prevent double moves (track visited in cyclic permutations).

---

Quick skill recap

Skill	Nail this sentence
circular_array_handling	Indices wrap via i % n
circular_traversal	Start offset uses (start + step) % n
duplicate_handling	Pick tactic by sortedness + (space vs time)
group_reversal	Local reverse(lo, hi) composes rotations
in_place_modification	Swaps/cycles keep constant extra memory

---

Common pitfalls

• Modulo % with negative indices (language quirks)—normalize first
• dedupe_sorted_inplace length differs from len—truncate logically in platforms that need it
• Off-by-one when last group shorter than k

---

Practice

1. Evaluate nums[(i+k) % n] for i = n−1 and k = 1 (wrap).
2. Reverse [a1 a2 a3 | b1 b2] by three reverses (rotate intuition).
3. Note difference dedupe sorted (two-pointer) vs count duplicates unsorted (hash map).

---