Press → to begin. That starts the clock
The gap between these two is the whole job.
Somewhere in year two or three, something rewires. It isn't syntax. It's how a problem looks to you.
"I know the answer. I just can't write it." Your solutions arrive as whole thoughts: find the biggest one, sort it, check if it's in there. All correct. All impossible to type.
You stop trying to make the computer think like you, and start thinking like the computer.
The question changes from what is the answer to what are the steps. What do I look at? What must I remember? When do I stop?
Problems fall apart on their own: a loop here, a variable there, a comparison, an edge case. The code almost writes itself, because you were already thinking in it.
One mechanism. Every tooth in a fixed order.
The machine is never going to meet you halfway. It cannot learn your intuition or guess what you meant. So the move is not to teach it to think like you. It is to think like it.
Five numbers. Which is biggest? Click it and I'll time you. Then I take away the thing that made it easy.
Leave Nabatieh, deliver to Saida, Beirut and Tripoli. Shortest route? Click the cities. Distances are straight-line km.
No. You just watched all three. Same answer, 129 km, but look at what each one had to do to get there.
Exact, and it checks all (n−1)! routes whether they look promising or not. Dies at about 12 cities.
Also exact. It solves each set of cities once and reuses the answer, so it never re-walks a sub-route. Barely worth it at four cities. At fifteen it is 7 million steps against 87 billion routes.
Give up on perfect. Grab the closest city and never look back. Three times less work than brute force here, and it scales to millions. This is the method your eyes used on the map.
| map | routes | time |
| 10 cities | 362,880 | instant |
| 15 cities | 87 billion | 15 min |
| 20 cities | 1.2×1017 | 38 years |
| 25 cities | 6.2×1023 | 196 Myr |
Nobody knows a fast exact method, and nobody has proved one is impossible. That is the P vs NP question, with $1,000,000 attached.
So the question stops being "what is the answer?" and becomes "do I need it exact, or good and fast?"
Tracing that route, you followed one rule: from where I am, drive to the nearest place I have not been. Does it always work?
start → A → B → C = 1 + 4 + 13 = 18 km
start → B → A → C = 3 + 4 + 9 = 16 km
No. It took the cheap step in front of it and paid for that later.
On random maps it lands 20 to 25% over the best. On the Lebanese map it happened to be right, which is why it feels trustworthy.
It answers a different question. You asked for the shortest. This gives you a route.
Checking a route is under 20 km takes two additions. Checking it is the shortest means ruling out every other one. That gap is P vs NP.
Your eyes search in parallel. A CPU looks at one item at a time.
for (int i = 0; i < dots.length; i++)
if (dots[i] == "red")
return i;
return -1;
The dots are in no order. The only way to be sure is to look at every single one. Unsorted data costs you a look at all N.
Pick a number 1–100. Don't tell me. I'll find it in 7 guesses or fewer.
Doubling the data costs you one extra guess. Not double the work. One guess.
21 is bigger, so four of them are now impossible
21 is bigger, so… nothing. It could still be anywhere.
| list size | guesses | because |
| 100 | 7 | 27 = 128 |
| 1,000 | 10 | 210 = 1,024 |
| 1,000,000 | 20 | 220 ≈ 106 |
| 1,000,000,000 | 30 | 230 ≈ 109 |
"Can't I bin everything under 9 anyway?" Only after looking at all eight. And by then you have walked past 21.
Sorted data lets you discard what you never looked at. That is the whole saving.
So the sort is what buys the fast search. Pay once, search forever.
You sort it first. Shout at me and I'll swap two bars. Then we'll name what you invented.
Everyone in this room invents one of the first three. Nobody invents Quick Sort by accident.
Same job, same answer. Here is what each one actually costs as the list grows, counted in comparisons.
| 10 items | 1,000 | 1,000,000 | |
| Bubble | 45 | 500,000 | 5×1011 |
| Selection | 45 | 500,000 | 5×1011 |
| Insertion | ~25 | 250,000 | 2.5×1011 |
| Quick | ~24 | ~10,000 | ~20,000,000 |
At ten items they are all the same and none of it matters. At a million, the first three are not "slow". They are impossible. 5×1011 comparisons is about an hour and a half. Quick Sort finishes in a fifth of a second.
The first three all compare every item against every other item. Double the list and you do four times the work.
Quick Sort splits the list in half, then halves the halves. Double the list and you do a bit more than twice the work. That is the same halving trick that beat the guessing game.
That difference, four times versus twice, is the only thing that matters at scale. Not the language, not the machine, not how tidy the code is.
These numbers are getting awkward to say out loud. Engineers gave the shapes names.
You have been counting operations all evening. Big O is just the shorthand. It names the shape of the growth, and throws away everything else.
| shape | what it means | where |
| O(1) | always the same, however big the input | read a[7] |
| O(log n) | halve it each step, so log2 | guessing game |
| O(n) | look at each item once | red dot |
| O(n log n) | halve it, and touch everything at each level | quick sort |
| O(n²) | every item against every item | bubble sort |
| O(n!) | every possible ordering | delivery driver |
n is the size of the input: how many numbers, cities, dots or characters you were handed.
O(…) means "grows like". It is not a time in seconds. Two O(n) programs can differ by 50× and still both be O(n).
So it never answers "how fast is this?". It answers the only question that survives contact with real data: "what happens when n gets big?"
Careful with log. On a calculator log(100) is 2, because that is base 10. Halving means base 2: log2(100) ≈ 6.6, so 7 guesses. Big O writes no base at all, because changing base only multiplies by a constant and constants get dropped.
You already know all six. Five of them you did tonight, in this room, and the sixth is every array index you have ever written. This slide only gives them their names.
Big O is not "how fast". It is how much worse it gets when the data grows.
You can work out any complexity on paper with just these.
Because at real input sizes they stop mattering. At N = 1,000,000:
| a sloppy O(n), 10× slow | 10,000,000 | 0.1 s |
| a perfect O(n²) | 1012 | 2.8 hours |
The badly written linear solution beats the beautifully tuned quadratic one by a factor of 100,000. The shape wins. Always.
One second of CPU time is about 108 operations. That is the budget for anything that has to feel instant: a page load, an API call, a contest submission. Take the biggest N you will be handed and see what survives.
Use it backwards: you see N ≤ 200,000, so O(N²) is dead, so you need sorting or a hash map, before writing one line of code.
Shout it out.
Algorithms cost memory as well as time. It rarely decides the answer, but every machine you ship to has a ceiling.
int tmp = a[i]; // one spare variable, a[i] = a[j]; // whether the array holds a[j] = tmp; // 10 items or 10 million
int[] out = new int[a.length]; // a whole new
for (int i = 0; i < a.length; i++) // array, as big
out[i] = f(a[i]); // as the input
int is 4 bytes. A million of them is 4 MB.A hash map turns an O(n²) scan into an O(n) pass by storing n things. That is a bargain, and it is the move you will reach for again and again.
Four ways to hold your data. Forget the code for a minute: each one is a physical object, and each one makes a different question easy to ask.
You already own all four in real life. Each one now gets a slide to explain it, a slide to watch it work, and a slide to practise it.
A row of boxes, all the same size, sitting next to each other. Numbered from 0, and the number is the whole trick.
One unbroken block of memory cut into equal boxes. Because they are equal and touching, the machine can work out where box 2 lives instead of looking for it. That is why the index is free and the content is not.
int[] a = new int[5]; // fixed size a[2] = 85; int n = a.length; List<Integer> b = new ArrayList<>(); b.add(85); // grows itself int m = b.size();
The characters of a String. A board or grid, which is an array of arrays. The args handed to main. Every list you have looped over.
The simplest one there is: a numbered row of boxes, all the same size, side by side. Every other structure tonight is built out of this.
Every box is the same size and they sit side by side, so the machine can calculate where box 6 is. That is also why inserting at the front is expensive: everything after it has to shuffle up to make room.
Ten boxes. For each job, say the number out loud before I run it.
Four one-line jobs. Two of them are free. Two of them are not. Nothing in the source code tells you which is which, so you have to know the structure.
A box of labelled drawers. You look things up by name instead of by number. If you have used a dictionary in Python or an associative array in PHP, you already know this one.
Hand it a key and it hands back the value filed under that key, without opening any other drawer. Ten entries or ten million, the answer costs the same.
Map<String,Integer> n = new HashMap<>();
n.put("Ali", 4); // file it
n.get("Sara"); // 3
n.containsKey("Rita"); // true
n.getOrDefault("Zak", 0); // 0 if new
About to write a loop that searches a list? Ask whether a map deletes the loop. It fixes more slow solutions than anything else tonight.
An array can only be asked "what is in box 7?". A hash map can be asked "what is under the word grape?" and answers just as fast.
int slot = key.hashCode() % 8;
A hash map is an array. The only new part is the function that turns your key into an index. Nothing is ever searched, which is why it does not matter whether the map holds six words or six million.
Forget the hashing now, the library does it. Nine times out of ten a hash map is for one job: how many times did each thing turn up?
put(k, v) store it, or overwrite itgetOrDefault(k, 0) read it, or 0 the first timecontainsKey(k) is it in there yet?keySet() every key, to loop over at the endFourteen numbers, find the first one that repeats. Same loop both times. The only difference is where you keep what you have already seen.
One line different, and the shape of the whole program changes. This exact pattern turns up in more contest problems than any other.
Last in, first out. A pile of plates. You put one on the top, you take one off the top, and the plate at the bottom is the one you get back last.
Both arrows point at the same end. You add at the top, you remove at the top, and you cannot touch anything else. That restriction is the whole point.
Deque<String> st = new ArrayDeque<>();
st.push("A");
st.push("B");
st.peek(); // "B", look, don't take
st.pop(); // "B", take it
st.isEmpty();
Whenever the most recent thing must be dealt with first: undo, the back button, closing the bracket you opened last. And every recursive call you have made, because Java keeps this exact pile for you.
Last in, first out. A pile of plates. Only the top one is reachable, and that limit is the whole feature.
int fact(int n) {
if (n == 1) return 1;
return n * fact(n - 1);
}
Valid or not? Vote first, then we step through it with a stack.
Stack<Character> st = new Stack<>();
for (char c : s.toCharArray()) {
if (isOpen(c)) st.push(c);
else {
if (st.isEmpty()) return false;
char open = st.pop();
if (!pairs(open, c))
return false;
}
}
return st.isEmpty();
Counting the brackets is not enough. You have to remember which one you opened last and give it back first. That is a stack.
First in, first out. The line at a bakery. You join at the back, you are served from the front, and nobody jumps.
The two arrows point at opposite ends. That is the only difference from a stack, and it changes everything: a stack deals with the newest first, a queue deals with the one that has waited longest.
Queue<String> q = new ArrayDeque<>();
q.add("A"); // join the back
q.add("B");
q.peek(); // "A", look, don't take
q.poll(); // "A", take it
q.isEmpty();
Anything served in the order it arrived: print jobs, requests, whose turn it is. And the one that wins contests: spreading out in waves, which is how you find a shortest route.
First in, first out. A bread line. You join the back, you are served from the front.
int[] q = new int[n]; int head = 0, tail = 0; q[tail++] = x; // join the back int y = q[head++]; // serve the front
The trap: list.remove(0) shifts everyone left, so inside a loop it is quietly O(n²). Use ArrayDeque.
A maze. You start at S, the way out is E. The only decision in the whole algorithm: which cell do you look at next?
One word decides it. Take the oldest and the search spreads evenly, so the first time it touches the exit it has come the shortest way. Take the newest and it charges down one corridor until it is stuck. The data structure is the algorithm.
The problem: somewhere in this row, exactly two numbers add up to 17. Find which two, and report their positions.
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (a[i] + a[j] == T)
return new int[]{i, j};
Map<Integer,Integer> seen = new HashMap<>();
for (int i = 0; i < n; i++) {
int need = T - a[i];
if (seen.containsKey(need))
return new int[]{seen.get(need), i};
seen.put(a[i], i);
}
Never jump from the idea straight to the syntax. Pseudocode is where you catch your own vagueness, before Java makes you commit to types.
Click the line you think is broken.
More points are lost to broken parsing than to bad algorithms. Copy your template now.
2 5 1 2 3 4 5 3 10 20 30
Line 1: how many test cases. Then per case: N, then N numbers.
long, not intScanner is fine to about 105 numbers. Past that use BufferedReader"Answer: "int / int truncates. Cast before you divideFind the contiguous block with the largest sum. Three minutes on paper. Go.
It isn't only who codes best. It's who spends their time best.
Anything from tonight, or anything you have been stuck on all semester.
Six exercises tonight use five patterns. You already know the thinking. This is just the spelling.
int[] a = {4, 2, 6};
int first = a[0];
int n = a.length;
Arrays.sort(a); // ascending, in place
return new int[]{i, j}; // return two indices
Map<String,Integer> count = new HashMap<>();
count.put("Ali", 1);
count.getOrDefault("Ali", 0); // 0 if missing
count.containsKey("Ali"); // true / false
for (String key : count.keySet())
System.out.println(key + " " + count.get(key));
Deque<Character> st = new ArrayDeque<>();
st.push('(');
st.peek(); // look, don't remove
st.pop(); // remove the top
st.isEmpty();
a.equals(b); // same letters? a.compareTo(b); // negative = a comes first
a == b on String compares references, not letters. Always .equals()int silently. Use long