Topic notebook / 01
Arrays & hash maps
Start with a list of values. A hash map lets you remember earlier work instead of scanning the same list again.
What to look for
- Choose what to store as the key.
- Check before inserting when the same item cannot be used twice.
- Trade extra memory for fewer repeated scans.
Work through a question
16 availablePack a Two-Item Parcel
A packing belt carries items with positive integer weights. Find the first pair completed while scanning left to right that exactly fills a parcel. Return their zero-based positions; if several earlier partners fit, use the earliest one. Return [] if no pair fits.
Easy / Hash map / interactiveCount Balanced Shipment Runs
A depot records signed stock changes: arrivals are positive and departures are negative. Count every nonempty contiguous run whose total equals the requested change. Overlapping runs count separately.
Medium / Prefix sums + frequency map / interactiveTime a Single Market Trade
A market posts one price per day. Buy once, then sell on a later day. Return the largest possible profit; choosing not to trade is allowed and earns 0.
Easy / Running minimum / interactiveMultiply Every Other Sensor
For every sensor position, return the product of all other readings. Do not divide. Negative readings and zeros are allowed.
Medium / Prefix and suffix products / interactiveChoose the Strongest Energy Run
Signed readings represent energy gained or lost at consecutive stations. Return the largest sum of a nonempty continuous run. At least one reading is required.
Medium / Kadane's algorithm / interactiveTurn a Camera Frame Clockwise
A square camera frame contains integer pixel labels. Return a new frame rotated 90° clockwise. Keep the original unchanged; this variant deliberately uses an output matrix rather than an in-place rotation.
Medium / Matrix coordinate mapping / interactiveScan Labels Around the Border
Read a rectangular label matrix clockwise from its top-left corner, peeling one outer border at a time. Return the labels in reading order without changing the matrix.
Medium / Shrinking matrix boundaries / interactiveClear Faulty Sensor Lines
A zero sensor reading means its entire row and column are faulty. Return a new matrix with those lines zeroed based only on the original zeros. Do not let newly written zeros trigger more clearing.
Medium / Matrix marking in two passes / interactivePay with the Fewest Voucher Tokens
Voucher tokens have positive integer values and unlimited supply. Return the fewest tokens that pay an exact amount, or -1 when it cannot be paid. Amount 0 needs no tokens.
Medium / Dynamic programming / interactiveReach the Last Platform
Each platform lists the maximum forward jump from it. Start at position 0 and choose any jump from 1 up to that limit. Return whether the last platform is reachable.
Medium / Greedy reachability / interactiveCatch the First Repeated Badge
A gate logs integer badge IDs. Return [earliest previous position, current position] for the first repeat completed while scanning left to right, or [] if every badge is new. Variant: report the first repeated pair instead of a boolean.
Easy / First-occurrence hash map / interactiveChoose a Strong Amplifier Chain
Signed integer gain settings form a line of amplifiers. Choose a nonempty continuous chain and return its largest product. Negative settings reverse the sign and zero resets a chain. Original scenario; the maximum-product task is unchanged.
Medium / Running minimum and maximum / interactiveLocate the Dispatch Restart
Distinct dispatch numbers were sorted increasingly, then cyclically rotated. Return the zero-based position of the smallest number, the restart point. Variant: return its position rather than its value.
Medium / Binary search for the pivot / interactiveFind a Dispatch in the Shifted Log
Distinct dispatch numbers form a cyclic rotation of an increasing list. Return the position of the requested number, or -1 if it is absent. Original dispatch-log scenario; the search contract is unchanged.
Medium / Binary search with a sorted half / interactiveBalance Three Calibration Readings
Choose three different positions whose signed readings sum to the requested calibration total. Return unique value triples, each increasing, in lexicographic order. Variant: the target is configurable, not always zero. Equal readings may be used only when enough separate positions exist.
Medium / Sorted anchors and two pointers / interactiveSpan the Largest Rain Reservoir
Vertical posts stand one unit apart. Choose two posts and return the largest rectangular water area: their separation times the shorter height. Original rain-reservoir scenario; the area contract is unchanged. Fewer than two posts gives 0.
Medium / Opposing two pointers / interactiveWhere this leads
Keep following the branch when this pattern feels familiar.