Phase 6Days 28-35

Arrays: Easy to Medium to Hard

A deep bag of array techniques: prefix sums, two pointers, Kadane, intervals, matrix moves

Phase Goal

Build the bread-and-butter array toolkit every contest and interview leans on.

Progress

Day 28: Easy array patterns

Largest and second largest in one passCheck if an array is sorted (and rotated-sorted)Remove duplicates from a sorted array in placeLinear search and when it is unavoidable

Left rotate by one and by D (the reversal trick)Move all zeros to the end preserving orderThe two-pointer write-index patternWhy in-place beats making a new array

Union and intersection of two sorted arraysFind the missing number (sum and XOR tricks)Maximum consecutive onesSingle number via XOR

Choose one core problem from LeetCode, Codeforces, AtCoder, or CSES after checking its prerequisites; hide its technique labelSpend 10–20 minutes retrieving one earlier mechanism and one earlier bug before new work; prioritize weak prerequisitesUse a five-task bank: guided warm-up, core, changed constraint, delayed recall, optional stretch; attempt one or two, not all five on a timerBefore a solution, produce a trace or brute-force plan; when stuck take one hint, act on it, then reassessRecord help used, the failing input, the corrected reasoning, and a next review date; start around 1/3/7/14/30 days and adaptReserve a weekly mixed review; after foundation readiness add a short virtual contest and upsolve one task with known prerequisitesProve progress through a delayed blank-editor reconstruction and a changed problem; a same-day quiz is supporting evidence only

Day 29: Prefix sums & subarray sums

Build a prefix-sum array for O(1) range-sum queriesOff-by-one and the prefix[0]=0 convention2D prefix sums for submatrix sumsDifference arrays for range updates

Prefix sum plus a hash map of seen sumsWhy the count of (prefix - k) gives the answerHandling negatives (where sliding window fails)Longest subarray with sum K (positives versus pos+neg)

Largest subarray with 0 sum via the first-seen prefixCount subarrays with XOR = K using a prefix-XOR mapThe prefix + hashmap meta-patternRecognizing the family across problems

Day 30: Kadane & the sign / rearrange family

The running-sum reset intuition (drop a negative prefix)Why resetting to 0 is optimalPrinting the actual subarray (track start and end)Handling an all-negative array

Why product breaks Kadane (negatives flip sign)Tracking both the max and min running productsZeros as resetsThe prefix/suffix product alternative

Rearrange elements by sign (alternating, equal counts)Best time to buy and sell stock (single transaction)Tracking min-so-far and best profitThe linear-scan greedy shape

Day 31: Medium array classics

Majority > n/2 via Boyer-Moore votingWhy the cancellation argument worksMajority > n/3 (at most two candidates)A verification pass to confirm the candidates

Sort 0s, 1s, 2s in one pass with three pointersThe low / mid / high invariantWhy mid does not always advanceGeneralizing to three-way partitioning

Next permutation: find the pivot, swap, reverse the suffixWhy this yields the next lexicographic orderLeaders in an array (scan from the right)Longest consecutive sequence with a hash set

Day 32: Intervals & matrix moves

Sort by start, then merge overlapping intervalsInsert an interval into a sorted setNon-overlapping intervals (greedy removal preview)The sweep intuition

Set matrix zeros in place (using row 0 and col 0 as markers)Rotate a matrix 90 degrees (transpose then reverse)Why the naive extra-matrix approach wastes spaceThe index mapping for rotation

Spiral order traversal with four boundariesShrinking boundaries correctly to avoid double-visitsPascal's triangle (three query types)Generating a row in O(n)

Day 33: Hard array problems — part 1

3Sum: sort plus two pointers, skipping duplicates4Sum: one more loop plus two pointers, with overflow careWhy sorting enables the two-pointer sweepDeduplication without a set

The sorted meet-in-the-middle patternContainer-with-most-water style movesDeciding which pointer to move and whyProving no valid pair is skipped

Merge two sorted arrays in place (the gap method)The insertion-shift approach and its costWhy the gap approach is O((n+m) log(n+m))Trace on small inputs

Day 34: Hard array problems — part 2

Using the sum and sum-of-squares equationsThe XOR-partition methodThe marking-by-index (in-place) methodTrade-offs of each

Framing via merge sort from Phase 4Reverse pairs (a[i] > 2*a[j]) countingOverflow-safe comparisonA different structure will let us do this another way in the advanced phase

Rotate / spiral / zeros recap under time pressureChoosing prefix versus two-pointer versus sort per problemBuilding a decision tree for array problemsSpeed practice mindset

Day 35: Array capstone & mixed set

A flowchart: sorted? sum? subarray? interval? matrix?Prefix versus sliding window versus two pointersWhen hashing beats sorting and vice versaComplexity budgeting from the constraints

Longest consecutive sequence (revisit, O(n))Maximum product subarray under pressureMerge-intervals variantsTime-boxed solving

Keeping a personal pattern catalogRe-deriving one technique from scratchSpotting the reusable core across today's problemsPreparing for the strings phase

Phase Complete!

After this phase, you'll be able to:

Easy array patterns
Prefix sums & subarray sums
Kadane & the sign / rearrange family
Medium array classics
Intervals & matrix moves
Hard array problems — part 1
Hard array problems — part 2
Array capstone & mixed set

After Phase 6, explain a core invariant, reconstruct a solution after a delay, diagnose a bug, and solve one unlabelled variation. Repair a failed prerequisite before advancing; record help separately from independent work.

Back to all phases

Phase Goal

Day 28: Easy array patterns

Scanning basics

In-place rearrangement

Set-like array ops

Practice, delayed recall, and independent transfer

Day 29: Prefix sums & subarray sums

Prefix sum arrays

Subarray sum equals K

XOR subarrays & zero-sum

Practice, delayed recall, and independent transfer

Day 30: Kadane & the sign / rearrange family

Maximum subarray (Kadane)

Max product subarray

Rearrange by sign & stock

Practice, delayed recall, and independent transfer

Day 31: Medium array classics

Majority elements

Dutch national flag

Next permutation & leaders

Practice, delayed recall, and independent transfer

Day 32: Intervals & matrix moves

Merge intervals family

Matrix transformations

Spiral & traversal

Practice, delayed recall, and independent transfer

Day 33: Hard array problems — part 1

k-sum problems

Two-pointer sweeps

Merge without extra space

Practice, delayed recall, and independent transfer

Day 34: Hard array problems — part 2

Find repeating & missing

Count inversions & reverse pairs (revisit)

Grid & consistency drills

Practice, delayed recall, and independent transfer

Day 35: Array capstone & mixed set

Choosing the right technique

Mixed hard problems

Reflection & pattern log

Practice, delayed recall, and independent transfer

Phase Complete!