Command Palette

Search for a command to run...

Hectal

Module 2

Arrays

The most common input in coding problems: walk it once, carry a little state, work in place, and recognise Kadane's algorithm.

Beginner 4 lessons 7 problems ~50 min of lessons
Running State in One PassKadane's AlgorithmIndex as Hash (Cyclic Sort)Matrix Traversal

Arrays look simple, but most of the patterns in this course start here: one pass with a running state, prefix and suffix thinking, in-place updates, and Kadane's algorithm for the best subarray.

Each problem below starts with the obvious slow solution and asks what repeated work makes it slow. That question, more than any formula, is what turns O(n²) into O(n).

Best after: Big-O and Complexity

Part 1

Learn the ideas

  1. 2.1How Arrays WorkWhy reading `a[i]` is instant, why inserting in the middle is slow, and how dynamic arrays like ArrayList grow.12 min
  2. 2.2One Pass with Running StateThe single most common array technique: walk once and keep a few variables that summarise everything so far, instead of looking back.12 min
  3. 2.3Kadane's AlgorithmThe best sum of a contiguous subarray in one pass: at each element, either extend the best subarray ending just before it, or start fresh.15 min
  4. 2.4Matrices and 2D ArraysRows and columns, walking neighbours safely with direction arrays, and the boundary technique for spirals and layers.12 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 2.1Best Time to Buy and Sell StockEasyRunning State in One Pass

    Replace an O(n²) look-back with one variable (the cheapest price so far): the purest example of running state.

  2. 2.2Majority ElementEasyRunning State in One Pass

    Three answers to one question: counting with a map, sorting, and the Boyer-Moore vote that needs only two variables.

  3. 2.3Missing NumberEasyIndex as Hash (Cyclic Sort)

    When values are 0..n, the index itself can act as the hash. Also the arithmetic shortcut, and how to avoid its overflow.

  4. 2.4Maximum SubarrayMediumKadane's Algorithm

    Kadane's algorithm: the best subarray ending here is either this element alone or it plus the best ending just before.

  5. 2.5Rotate ArrayMediumTwo Pointers: Opposite Ends

    The reversal trick: three in-place reverses rotate an array with O(1) extra space.

  6. 2.6Spiral MatrixMediumMatrix Traversal

    The four-boundary technique for walking a matrix layer by layer without revisiting cells.

  7. 2.7First Missing PositiveHardIndex as Hash (Cyclic Sort)

    Using the array itself as a hash table: place each value 1..n at index value − 1, then scan for the first gap.