Data structures & algorithms · Linear consolidation lab

Reading a problem and naming the tool

This module adds no new algorithm. It trains the thirty seconds before you write code: read the constraint line, find the phrase only one tool answers, and say its name out loud.

Narrow six tools down to one →

Six tools on the table

→

Four clues · one left

01 The idea

Problems are written to a template. Learn to read it.

By Stage 2 you already know binary search, two pointers, sliding window, monotonic stack and hash maps. The gap that costs marks is no longer writing them. It is opening a statement you have never seen and knowing, in half a minute, which of the five it wants. That is a reading skill, and it is trainable.

Every online assessment and interview question is written to the same shape: a description, a return line, and a constraint line. The setter chooses each word. When the statement says sorted or contiguous or positive, that word is there because the intended solution uses it. Your job is to spot which words are doing work and which are scenery.

Read the constraint line first: it fixes the complexity you are allowed. Then hunt for the one phrase that only a small set of tools can answer — sorted, contiguous, next greater, seen before. Name the tool before you write a line, then check its precondition actually holds.

TellA phrase in the statement that only a small set of tools can answer. “Contiguous subarray” is a tell. “Given an array” is scenery — every problem starts that way.

Constraint lineThe line giving the range of n. It fixes your time budget, so it deletes whole families of solutions before you have finished reading the question.

PreconditionThe property a tool needs to be correct. Binary search needs sorted order; a sliding window needs a sum that only grows as the window widens. A tell proposes a tool; the precondition confirms it.

02 Hand trace

One statement, four clues, one tool left

Here is the statement this whole lesson runs on. Given an array of n positive integers and a value k. Return the length of the longest contiguous subarray whose sum is at most k. 1 ≤ n ≤ 100000, 1 ≤ arr[i] ≤ 10000.

Six tools start on the table, one per box below: brute (two nested loops), hash (hash map), win (sliding window), 2ptr (two pointers converging on a sorted array), mono (monotonic stack), bsrch (binary search). A rose box is ruled out and stays ruled out. Watch which clue kills which box.

startbrutehashwin2ptrmonobsrch6 live · nothing read yet

n ≤ 100000brutehashwin2ptrmonobsrchn² = 10¹⁰ steps — 100× over budget

“the length”brutehashwin2ptrmonobsrchone answer for the array, not one per index

“contiguous”brutehashwin2ptrmonobsrchmay not sort — no sorted range to halve or converge on

“positive”brutehashwin2ptrmonobsrchsum only grows — no prefix map needed

verdictbrutehashwin2ptrmonobsrchsliding window · O(n) time · O(1) space

Notice the order you read in. The constraint line is at the bottom of the statement and you read it first, because n ≤ 100000 squared is 10¹⁰ operations against a budget of roughly 10⁸ per second — about a hundred seconds for a one-second limit. That single line deletes brute force before you understand the question.

Then each phrase removes more. The length of the longest asks for one number for the whole array, so a monotonic stack — which produces one answer per index — has nothing to do. Contiguous is the loudest word: the elements must sit next to each other, so you may not sort, and both binary search and the converging two-pointer walk are sorted-only. That leaves a hash map and a window. Positive integers decides it: every value is at least 1, so widening the window can only raise the sum and shrinking from the left can only lower it. That is exactly the rule a window needs. You never had to recall a similar problem.

One honest footnote, because a tell names a favourite, not the only legal move. Binary search is not completely dead here. Every value is at least 1, so the prefix sums of this array come out strictly increasing — a sorted range appears that was never in the input — and you could binary search it for each right edge and get a correct answer in O(n log n) time and O(n) memory. It would pass. The window is cheaper on both axes, so the trace rules binary search out as the intended tool, not as an impossible one. Say the alternative out loud in an interview; being able to price two correct solutions is worth more than producing one.

03 The procedure

Four questions, always in this order

The trace was one statement. Here is the general routine it followed, and then the lookup table that turns a phrase into a tool. Ask the four questions in this order every time — the order matters, because question one is the cheapest and eliminates the most.

What is the limit on n?Read the constraint line before the description. Multiply your candidate complexity out at the largest n and compare it against roughly 10⁸ simple operations per second.n ≤ 100000 → n² = 10¹⁰ → too slow → you need O(n) or O(n log n)

What am I returning?One number for the whole array, one answer per index, a boolean, or a rebuilt array. This alone splits the aggregate tools from the per-index tools.“the length of the longest…” → one aggregate → not a per-index tool

What does the statement promise about the input?Sorted, positive, distinct, lowercase only, contiguous. Every promise is a permission or a prohibition. Contiguous forbids sorting; sorted permits halving.“contiguous” → do not sort → no sorted range to halve or converge on

Does my candidate’s precondition hold?This is the step people skip, and it is where wrong answers come from. Name the property the tool needs and find the words in the statement that grant it.window needs: widening cannot lower the sum → “positive integers” → holds

✓

Say it out loudName the tool, the time cost and the space cost in one sentence, before you write any code.Sliding window · O(n) time · O(1) extra space

The recognition table

Phrase in the statement	What it is telling you	Tool	Typical cost
“sorted”, “non-decreasing”, “in increasing order”	Order is free information the setter expects you to spend.	Binary search to find one thing; two pointers converging from both ends to find a pair.	`O(log n)` / `O(n)`
“contiguous subarray”, “substring”, with a sum or length condition	The answer is one span, and both of its edges only ever move forward.	Sliding window	`O(n)`
“next greater”, “previous smaller”, “days until a warmer one”, “span”	Each index is answered by the nearest unresolved index behind it.	Monotonic stack	`O(n)`
“seen before”, “count”, “frequency”, “distinct”, “duplicate”	Position does not matter; membership and counts do.	Hash map or hash set	`O(n)` average
“a pair adding to X” on an unsorted array	You need a complement lookup, not a scan.	Hash set, or sort first and then converge two pointers	`O(n)` / `O(n log n)`
1 ≤ n ≤ 100000 with a one-second limit	Anything quadratic is already too slow, whatever the wording says.	Forces a single pass or a sort	`O(n²)` is out

The trap. Every row above names a candidate; not one of them confirms it. “Contiguous subarray with sum at most k” points at a sliding window every time, but the window is only correct while widening cannot lower the sum — change “positive integers” to “integers” and the same tell now points at the wrong tool. Row one is just as soft: sorted does not mean binary search. Sorted means order is available. Whether you spend it on halving, on converging from both ends, on a merge, or on nothing at all depends on what the return line asks for, and a sorted array whose question is “the longest run of equal values” wants a plain scan. Read the tell, then read the return line, then check the precondition.

05 Cheat sheet

The constraint ladder

Assume a judge does roughly 10⁸ simple operations per second. Find your n on the left and read across — that is the most expensive thing you are allowed to write.

n up to	Complexity that fits	Steps at that n	What you would reach for
10	`O(n!)`	3,628,800	Permutations, full enumeration, backtracking
20	`O(2ⁿ)`	1,048,576	Every subset, bitmask DP
500	`O(n³)`	125,000,000	Three nested loops, Floyd–Warshall
5000	`O(n²)`	25,000,000	Two nested loops, simple DP table
100000	`O(n log n)`	~1,700,000	Sort, binary search, heap
1000000	`O(n)`	1,000,000	Sliding window, hash map, monotonic stack
1000000000	`O(log n)`	~30	Binary search on the answer, direct maths

10⁸ per secondThe one number to memorise. Multiply your complexity out at the largest n before you commit. 100000 squared is 10¹⁰, which is about a hundred seconds, not one.

Sorted is never an accidentIf the statement promises sorted, distinct, positive or lowercase-only, the setter put it there to be used. A promise you never used usually means you picked the wrong tool.

Contiguous forbids sorting“Contiguous subarray” and “substring” mean positions matter, so sorting destroys the problem. “Any subsequence” or “any subset” means positions do not matter and sorting is allowed.

06 Where & why

A tell is a hypothesis, not an answer

Reading tells gets you to a candidate in thirty seconds. It does not prove the candidate is correct, and it is not a substitute for knowing the five tools. What it buys you is a direction, so the rest of your thinking goes into checking one precondition instead of staring at a blank page.

Reach for it when…

The statement has a constraint lineOnline assessments, contest problems and most interview questions are written to a template with a return line and a limit on n. Those two lines carry most of the signal.

The input comes with a promiseSorted, positive, distinct, lowercase only. Setters do not add these for decoration, so each one narrows the candidate set immediately.

You are stuck between two candidatesChecking each tool’s precondition against the wording usually kills one outright. That is faster and safer than coding both and seeing which passes.

You have to explain your choiceIn an interview the reasoning is what is marked. “Contiguous, values positive, n is 10⁵, so sliding window” is a complete answer before a line of code exists.

Use something else when…

Situation	Better choice	Why
The tell fires but the precondition fails — “contiguous sum” with values that can be negative	Prefix sums — with a hash map when the target sum is exact, with a monotonic deque when it is “at most k”	The window shrink rule assumes widening can only raise the sum. With negatives it can fall, so the left edge has no safe rule and the window is simply wrong: on 3, −2, 1 with k = 2 it returns 2 when the whole array is a legal answer of length 3.
No tell fires at all	Write the brute force, then remove its repeated work	A correct `O(n²)` scores; a half-remembered `O(n)` scores nothing. The brute force also shows you exactly which work to cache.
The constraint is small — n ≤ 2000 or n ≤ 20	Nested loops, or full enumeration	A small limit is the setter saying the clever solution is not required. `O(n²)` at n = 2000 is 4 million steps and passes comfortably.
Two tools both fit the budget	The one with less extra memory, or the one you can write correctly under pressure	Equal time is not equal cost: `O(1)` space beats `O(n)` space, and a working window beats a buggy hash map.

Nobody is testing whether you have memorised two hundred problems. There are hundreds of thousands of problems and about a dozen tells, so memorising does not scale and reading does. The sentence that gets you the offer is “contiguous plus a sum condition, values are positive, n is 10⁵ — that is a sliding window, O(n) time and O(1) space”, said before you touch the keyboard.

07 Interview questions

Say these out loud

These are asked as a live reading exercise: the interviewer reads a statement and watches how you narrow it. Practise the reasoning, not the answer.

How do you decide which technique a problem needs?

I read the constraint line first, because it fixes the complexity I am allowed. Then I look for the one phrase only a small set of tools can answer — sorted, contiguous, next greater, seen before. That gives me a candidate in about thirty seconds, and then I check the tool's precondition against the statement before I write anything.

What does the constraint line actually tell you?

Roughly how many operations I am allowed, assuming about 10⁸ simple steps per second. At n ≤ 10⁵ an O(n²) solution is 10¹⁰ steps and will time out, so the intended answer is O(n) or O(n log n). At n ≤ 2000 the same O(n²) is 4 million steps and passes easily — that limit is the setter telling me not to be clever.

You see the phrase “contiguous subarray”. What do you reach for, and what do you check first?

A sliding window, and the first thing I check is whether the window has a legal shrink rule. That needs the quantity I am tracking to move in one direction as the window widens — an all-positive array for a sum, or values of at least 1 for a running product. If the values can be negative, widening can lower the sum and the left edge has no safe rule, so I fall back to prefix sums.

What is the difference between two pointers and a sliding window?

A sliding window is two indices walking forward over one contiguous span, and it needs no sorting at all. The classic two-pointer walk starts at both ends of a sorted array and converges, and it is useless without that sorted guarantee. Both are O(n), but the tells differ: contiguous plus a condition means window, sorted plus find-a-pair means converging pointers.

When does a hash map beat sorting?

When the question is about membership, counts or duplicates and the order of the data does not matter. Sorting costs O(n log n); a hash map answers the same question in O(n) average time, at the cost of O(n) memory. I sort instead when I need the order afterwards — the k smallest, a converging two-pointer walk, or grouping equal values together.

What phrase makes you think monotonic stack?

Anything shaped like nearest greater or nearest smaller: how many days until a warmer one, the previous taller building, how far a bar can stretch. The signal is that each element is answered by the closest unresolved element behind it, and since every element is pushed once and popped once it comes out O(n). If the question wants one aggregate for the whole array instead of one answer per index, it is usually not a stack.

Longest subarray with sum at most 2: the window is right on 3, 2, 1 and wrong on 3, −2, 1. Why?

Because the shrink rule assumes the sum can only grow as the window widens, and the second array breaks that. The whole of 3, −2, 1 sums to 2, so the answer is 3 — but the window sees 3 at the first element, decides it is over budget, pulls its left edge past it and never recovers, reporting 2. On 3, 2, 1 abandoning the first element is genuinely safe, so the same code is right. With a negative present, a window that is currently too big can become valid by growing, and moving the left edge in is no longer the right response. The fix is prefix sums, which turns it into a search over prefix values rather than a window.

n is 2000 and the time limit is one second. What changes?

O(n²) becomes acceptable, because 4 million operations is nothing. So I stop hunting for the linear trick and write the two nested loops, which are shorter and much harder to get wrong. A small limit is deliberate — it usually means the straightforward solution is the intended one.

Sorted array — binary search or two pointers?

Binary search when I want one thing and can test it with a yes-or-no question: does this value exist, where does it first appear, what is the smallest capacity that works. Two pointers when the answer is a pair or a span and the comparison tells me which end to move — a pair summing to a target, or removing duplicates in place. Binary search is O(log n); the two-pointer sweep is O(n).

You read the statement and no tell fires. What do you do?

Hard

Given an array of n positive integers and a value k, return how many contiguous subarrays have a sum strictly less than k. 1 ≤ n ≤ 10⁵. Name the tool, give the expression that turns one window position into a count of subarrays, and say why the scan is still linear.

Follow-up

The answer itself can be about 5 × 10⁹, which overflows a 32-bit integer, while the algorithm producing it never makes more than 2n pointer moves. The size of an answer and the cost of computing it are different things, and here the return type has to change too.

Show the hint

Fix the right end at index r with the smallest legal left end l, and count how many valid subarrays end at r.