Puzzles and Seating

In linear arrangement, persons sit in a straight line. Two variants dominate IBPS PO: (1) Single row — all face the same direction (usually North), so the person's LEFT is your RIGHT when you face them. (2) Double row — one row faces North and the other faces South, seated opposite each other.

Key directional rule: if all face North, 'immediate left' moves toward the lower-numbered end. If all face South, directions reverse. In double-row puzzles, two people who 'face each other' sit directly opposite, so a person in the North-facing row and the one opposite in the South-facing row see each other.

Always fix the most concrete clue first (e.g., 'P sits at an extreme end' or 'exactly three persons sit between P and Q'). Convert every clue into a possible-positions diagram and eliminate cases. Track 'gaps' (number of people between two) carefully — 'three between' means 4 seats apart.

Memory aids and shortcuts:

• NEFL rule (North-East / South-West for left): When a person faces North, their LEFT is the West side (your right as observer); their RIGHT is the East side. When facing South, swap.
• 'Exactly N persons between A and B' = A and B are (N+1) seats apart. 'Immediate neighbour' = adjacent (0 between).
• Start point selection: Begin with clues giving ABSOLUTE positions (extreme ends, exact seat) before RELATIVE ones (left of, between).
• Make 2 grids when a clue allows two placements; carry both until a later clue kills one.
• For 'P is to the left of Q' without 'immediate', P can be anywhere left of Q — keep it loose.
• Count total seats from the question stem (8 people = 8 seats); never assume empty seats unless stated.

Linear seating puzzles in IBPS PO Prelims look like a friendly geometry exercise — until the clues quietly contradict each other and the whole arrangement collapses. The skill to learn is not "find the right answer" but "kill wrong cases fast" — and the worked example below shows exactly how an experienced solver does that under exam pressure.

Definition: A linear seating arrangement puzzle places N people in a single row facing a fixed direction (here, North). Clues give relative positions (left/right, between, adjacent, ends), and the solver must place each person at a numbered seat — usually seat 1 on the left and seat N on the right when everyone faces North.

The Setup

Seven friends A–G sit in a row facing North. We are given five clues:
(i) C sits third from the left end.
(ii) Only two persons sit between C and D.
(iii) A sits immediate right of D.
(iv) B is at an extreme end, not adjacent to C.
(v) E sits second to the right of A.

Before touching any clue, draw seven empty seats labelled 1 to 7 with seat 1 on the left:

_ _ _ _ _ _ _
1 2 3 4 5 6 7

Because everyone faces North, the audience's left is also the seated person's left — left = lower seat number, right = higher seat number.

Working the Clues

Clue (i): "C is third from the left." Place C at seat 3.

_ _ C _ _ _ _

Clue (ii): "Only two persons sit between C and D." Two people between seats means |C − D| = 3. C = 3, so D is at seat 6 (option A) or seat 0 (option B). Seat 0 does not exist, so D = 6 is the only option.

_ _ C _ _ D _

Clue (iii): "A is immediately to the right of D." D = 6, so A should be at seat 7.

_ _ C _ _ D A

Clue (v): "E is second to the right of A." If A = 7, "second right" lands at seat 9 — which does not exist.

At this point the candidate has hit a hard contradiction. Two newcomers try to "fudge" — they tell themselves A could be on the left of D, or maybe D could be on the left of C. An experienced solver instead steps back and tests the only other geometric option for clue (ii): D could be on the left of C, meaning D might sit at seat (3 − 3) = seat 0, which still does not exist.

So this configuration has no solution — and that is exactly the takeaway.

Why It Matters

In IBPS PO and SBI PO, examiners often design trap arrangements: sets of clues that seem solvable but actually break inside, and the only "correct" answer is "data insufficient" or a re-interpretation of "to the right" as "anywhere to the right" rather than "immediately to the right". A candidate who notices the contradiction in 90 seconds saves 5 minutes that they would have wasted force-fitting people.

The real value of this worked example is not the seating chart — it is the discipline of elimination:

• Always fix the most-determined clue first (here, C at seat 3).
• Branch only when forced; cut a branch the moment it contradicts another clue.
• Treat impossibility as information, not failure.

Real-world example: A cinema booking app shows seats 1–14 of row K. Your friends say "C is in seat 3, D is three away from C, A is to D's immediate right, E is two seats to A's right." If A is at 7 and E is at 9 — but row K has only 7 seats — the app's seat picker greys out the impossible slot. The puzzle is exactly the same logic the app uses to validate input: a sequence of positional constraints, with the row length as a hard wall.

Common misconception: Beginners assume that if the clues do not fit, they must have miscounted directions. They re-read "left" and "right" twenty times, getting more confused. The truth is simpler — the clue set itself sometimes contradicts. Trust your method: write the seats, count carefully, and if a clue forces a person off the row, the configuration is wrong, not your arithmetic.

Question: Suppose clue (v) is changed to "E is second to the left of A". With every other clue intact, does an arrangement exist?

Solution:
Step 1: From earlier deduction, C = 3, D = 6, A = 7.
Step 2: "E is second to the left of A" puts E at seat 5.
Step 3: Now clue (iv): "B is at an extreme end and not adjacent to C." Seat 1 is the only free extreme (since seat 7 = A). Seat 1 is not adjacent to seat 3 (because seat 2 is in between, but "adjacent" means immediately next). So B = 1 works.
Step 4: F and G fill seats 2 and 4 in either order — the puzzle has two valid completions for F and G.
Conclusion: Yes — with this single tweak the chain becomes consistent: B at 1, C at 3, E at 5, D at 6, A at 7, and F, G fit in seats 2 and 4.

The Method Behind the Madness

Notice the pattern of a strong solver:

1. Anchor — find the clue that nails a single position (here, "C third from left").
2. Distance — apply "between" clues to limit candidates to at most two options.
3. Cascade — let "immediate right/left" and "second to right/left" clues collapse the remaining freedom.
4. Check ends — extreme-end clues come last; they confirm or break the arrangement.
5. Eliminate — the moment any clue forces a seat outside 1–N, abandon that branch.

If you internalise this five-step cycle, you can solve a typical SBI/IBPS linear puzzle (12 marks worth) in 3–4 minutes instead of the 8 minutes most aspirants waste.

:::compare

:::keypoints

• Always draw the numbered seats before reading clues.
• Anchor the most-determined person first; do not start with vague "between" clues.
• "k between" means seat distance is (k + 1).
• "Immediate right" = +1 seat when facing North; "immediate left" = −1.
• An impossible seat is a signal that the branch is wrong — switch the other option of the "between" clue.
• End clues come last; they usually act as a final filter.
• If both branches die, the puzzle is inconsistent or the question expects "no solution".
  :::

:::memory
ADCEE method: Anchor, Distance, Cascade, Edge, Eliminate. Solve every linear puzzle in that exact sequence and you will never get stuck in the wrong branch for more than two minutes.
:::

:::recap

• Linear puzzles reward method over speed — anchor first, branch only when forced.
• North-facing means audience-left equals seated-left, so seat numbers grow toward the right.
• Contradictions are diagnostic; they tell you which clue to re-interpret.
• The takeaway is the method (ADCEE), not memorising a single layout.
  :::

Circular seating puzzles are easy money in IBPS PO — until the question slips in a sentence like "and three of them are facing outward." Suddenly the same diagram that gave you the answer in twenty seconds takes five panicked minutes. The fix is one rule, drilled until it is automatic: the direction of "left" and "right" depends on which way a person is facing.

Definition: A circular arrangement is a seating where a fixed number of persons sit equally spaced around a circle. They may all face the centre, all face outward, or follow a mixed/alternating pattern as specified.

Definition: Facing centre means each person's body is turned toward the centre of the circle, so they look inward at each other.

Definition: Facing outward means each person's body is turned away from the centre, so they look out of the circle.

The left-right rule

Picture yourself in the centre of a Diwali rangoli, with friends seated around its edge in a perfect circle. From above (the puzzle-solver's view), if a friend is facing the centre, raising their left hand points in the clockwise direction of the circle, and their right hand points anticlockwise.

Now turn that friend to face outward. Their left hand swings to point anticlockwise, and their right hand to clockwise. Same person, same circle — opposite arc directions for left and right, because the body has rotated 180°.

So memorise this once:

• Facing centre: LEFT → clockwise, RIGHT → anticlockwise (from the top view).
• Facing outward: LEFT → anticlockwise, RIGHT → clockwise.

If the puzzle says "all eight persons are facing the centre," apply the first rule uniformly. If it says "all eight are facing outward," apply the second. The tricky cases are mixed puzzles, where, say, four face inward and four face outward, or alternate persons face opposite directions. Then you must apply the rule per person, individually — the left of person P might be clockwise while the left of his next-door neighbour Q is anticlockwise.

Drawing the circle, then placing people

Step one in any circular puzzle is to draw the circle and mark the facing direction on each seat with a small arrow (an arrow pointing toward the centre for inward, away for outward). Do not skip this — the arrows are the visual anchor that prevents direction errors halfway through.

Step two is to fix one reference person — often "P sits at the top" or "A is fixed at position 1." Rotating the whole diagram by 60° or 120° does not create a new arrangement (the circle has rotational symmetry), so fixing one person eliminates duplicates and stops you from going in loops.

Step three is to translate every condition using the left-right rule for each person.

Reading position clues

"P sits 3rd to the left of Q." If both face the centre, move clockwise from Q by 3 seats to reach P. Count seats, not gaps — the third seat clockwise of Q is the answer. Many students make off-by-one errors here.

"Two people sit between A and B." In a circle, two arcs connect A and B — the short and the long. Unless the puzzle specifies which side, assume the short/direct arc and the puzzle will be solvable with that reading. If you hit a contradiction, switch arcs.

"R sits immediately to the right of S, S faces outward." Because S faces outward, right means clockwise for S. So R sits at the next clockwise seat from S.

"T sits second to the left of U; U faces the centre, T faces outward." Here U's left is clockwise (U faces in), so T is two seats clockwise from U. But what T sees from his own seat is governed by T's facing direction, which you will need for the next clue about T's neighbours.

Why mixed-facing puzzles are hard — and the fix

In a mixed puzzle the trap is to assume one global "left = clockwise." Different rows of the rough work can quietly use different conventions and the whole arrangement collapses. Defence: write a tiny legend on your scribble pad — "centre-facing: L = CW, R = CCW" and "outward-facing: L = CCW, R = CW" — and consult it every single time you place a person.

Why it matters: Seating arrangement is the largest sub-topic in IBPS PO Reasoning, often worth 5 marks in a single set. Mixed-facing circular puzzles are the standard high-difficulty version examiners use to separate top scorers. Getting the left-right rule wrong does not just cost one answer — it cascades through the whole set.

Real-world example: Think of a family dinner around a round dining table. Most relatives are facing inward toward the food. A grandmother who is helping serve from a side table briefly faces outward. From your seat across the circle, "the spoon to grandma's right" actually points the opposite way along the table's edge compared to "the spoon to your right," even though you are both on the same circle. That is mixed-facing in real life.

Common misconception: "Left is always anticlockwise from above." This is wrong. It is true only when the person faces outward. When the person faces the centre — the default in most puzzles — left is clockwise. The rule is about the person, not the page.

Question: Eight persons A, B, C, D, E, F, G, H sit around a circular table facing the centre. C sits second to the right of A. B sits third to the left of A. Who sits opposite to A?

Solution:
Step 1: All face centre, so for every person: LEFT = clockwise, RIGHT = anticlockwise.
Step 2: Place A at the top. "C is 2nd to the right of A" → move 2 seats anticlockwise from A → C is two seats anticlockwise of A.
Step 3: "B is 3rd to the left of A" → move 3 seats clockwise from A → B is three seats clockwise of A.
Step 4: With 8 seats, the person opposite A is at the 4th seat from A in either direction. From step 3, three seats clockwise is B, so the fourth seat clockwise (one seat past B) is the person opposite A.
Conclusion: The person sitting opposite A is whoever the puzzle places one seat clockwise of B. (In a full puzzle with the rest of the clues, you would substitute the actual name; the procedure is the takeaway.)

:::compare

:::keypoints

• Always draw the circle and mark each seat's facing with an arrow.
• Facing centre: LEFT = clockwise, RIGHT = anticlockwise.
• Facing outward: LEFT = anticlockwise, RIGHT = clockwise.
• In mixed puzzles, apply the rule per person — do not assume a global convention.
• "3rd to the left/right of X" means count 3 seats in the correct direction, not 3 gaps.
• Fix one person (usually at the top) to break rotational symmetry and avoid duplicates.
• "Between A and B" on a circle defaults to the short arc unless contradicted.
  :::

:::memory
"In-look, In-clock: left clocks in." If the person faces in, their left clocks clockwise. Flip every word when they face outward. Or use the hand-on-shoulder trick: imagine putting your left hand on the shoulder of the person facing the centre — your hand moves clockwise around the circle.
:::

:::recap

• Direction of left and right depends on the person's facing, not the page.
• Centre-facing: left = clockwise; Outward-facing: left = anticlockwise.
• Mixed-facing puzzles need a per-person check — write a legend.
• Draw the circle, mark arrows, fix one reference; then translate clues mechanically.
  :::

Square/rectangular tables in IBPS PO usually seat 8: 4 at the MIDDLE of each side and 4 at the CORNERS. Standard setups:

• Corner persons and middle persons often FACE OPPOSITE directions (e.g., corners face centre, middle-of-side face outward) — read the stem carefully.
• For an 8-seat square with people only at corners and mid-sides, adjacency wraps around all 8 seats.

Direction trick (facing centre): LEFT = clockwise, RIGHT = anticlockwise, identical to circle. For mixed-facing square tables, compute each person's left/right separately.

Speed aids:

• 'Nth to the left' (facing centre) = move N steps clockwise.
• Diagonally opposite on a square (8 seats) = 4 seats away.
• Count total seats from the stem; do not assume vacant seats.
• Lock the most rigid clue (corner/mid-side or a fixed pair facing each other) first.

Eight persons A-H sit around a circle facing the centre. Clues: A sits 2nd to the right of B. C sits 3rd to the left of A. D is an immediate neighbour of both C and E. F sits opposite A.

Method: Place B at top. 'A is 2nd to the right of B' (facing centre, right = anticlockwise) → move 2 anticlockwise from B to place A. 'C is 3rd to the left of A' (left = clockwise) → move 3 clockwise from A to place C. F opposite A = 4 seats from A. D neighbours C and E means D sits between C and E. Fill remaining seats with G,H.

The disciplined steps: (1) anchor B, (2) convert each 'left/right' into clockwise/anticlockwise moves, (3) place opposite as 4-away, (4) slot neighbours, (5) put leftover names in remaining seats. This yields a unique circle. Always re-verify each clue against the final diagram before answering — a single mis-counted step invalidates the whole arrangement.

Floor puzzles place persons/items on different floors of a building, numbered bottom-to-top (Floor 1 = lowest). Box/stack puzzles work identically but vertically stacked boxes. The vocabulary is the differentiator:

• 'Above/below' refers to higher/lower floor numbers.
• 'Immediately above' = the next floor up (n+1); 'immediately below' = n-1.
• 'As many floors above X as below Y' creates a symmetric equation — set up the count and solve.

Common clue types: 'Three floors between A and B' (gap of 4 floors apart in number), 'A lives on an even-numbered floor', 'Exactly two persons live between A and B'. Always draw a vertical column with floor numbers labelled. Lock absolute clues (top floor, bottom floor, specific floor number) first, then relative ones. For multi-variable floor puzzles (person + floor + a third attribute like rent or city), build a table with floors as rows.

Shortcuts that save time:

• 'N floors between A and B' → |floor(A) - floor(B)| = N + 1.
• 'A lives immediately above B' → floor(A) = floor(B) + 1.
• 'As many floors above A as below B': if A and B are not extreme, count and equate. Often forces both into the middle.
• For 7-floor buildings, the middle floor is 4; for any odd count n, middle = (n+1)/2.
• Even/odd clue: list even floors {2,4,6...} and odd {1,3,5...}; eliminate fast.
• Box weights/colours: treat the extra attribute as a parallel column tied to box order.
• 'Lowest/topmost' anchors: place these before relative clues.

Memory aid: think of an elevator — bigger number = higher. 'Above' always increases the floor number.

Floor puzzles look intimidating until you realise they are nothing more than the careful elimination of impossible cases. In IBPS PO, the examiner does not want you to guess — they want to see whether you can chase contradictions until only one arrangement survives. Let us walk through a classic six-floor problem the way a calm, disciplined aspirant would.

Definition: A floor puzzle is a logical reasoning puzzle in which people, objects or events must be placed on the floors of a building (usually numbered 1 to 6, with 1 = ground), subject to a set of clues. The candidate must use these clues to determine each placement uniquely.

The setup

Six persons — A, B, C, D, E, F — live on floors 1 to 6, where floor 1 is the bottom. Each person lives on a different floor. The clues are:

(i) A lives on an even-numbered floor.
(ii) There are three floors between A and B.
(iii) C lives immediately above D.
(iv) F lives on the topmost floor.
(v) E lives below D.

Find the floor of each person.

How to read the clues — and why each one is useful

Before solving, pause and categorise the clues. This habit alone wins time in the actual exam.

• Clue (iv) is an absolute fix — F is on floor 6. No casework needed.
• Clue (i) is a constraint set — A is on 2, 4 or 6. With F already on 6, A is on 2 or 4.
• Clue (ii) is a relative distance clue — "three floors between A and B" means |A − B| = 4. (The phrase "three floors between" excludes the two endpoint floors themselves, so we count the gap, which is 4.)
• Clue (iii) is a block — C and D form a pair where C is exactly one floor higher than D. They must be placed together.
• Clue (v) is an ordering clue — E is somewhere strictly below D.

The discipline is: place the strongest clue first, then narrow down the rest.

Step-by-step solution

Step 1: Place F. From clue (iv), F is on floor 6. Done.

Step 2: Test the two possible values of A. From clue (i), A is on 2 or 4. We test each with clue (ii).

Sub-case A = 2: B must satisfy |2 − B| = 4, so B = 6 or B = −2. Floor 6 is taken by F; floor −2 does not exist. Sub-case rejected.

Sub-case A = 4: B must satisfy |4 − B| = 4, so B = 8 or B = 0. Both lie outside floors 1–6. Sub-case rejected.

We have hit a contradiction. The standard examiner's convention in IBPS materials interprets "three floors between A and B" sometimes as a gap of 3 (i.e., |A − B| = 3, with two floors strictly in between also counting as "three floors between" in some phrasings depending on whether endpoints are inclusive). Many real exam keys treat this phrase as |A − B| = 3 when no other interpretation gives a unique solution. Let us therefore re-test with |A − B| = 3 — this is the convention every aspirant should keep in mind as a backup.

Sub-case A = 2 with |A − B| = 3: B = 5 or B = −1. So B = 5. Plausible.

Sub-case A = 4 with |A − B| = 3: B = 7 or B = 1. So B = 1. Also plausible.

We now have two surviving branches. Proceed to clues (iii) and (v) in each.

Step 3: Apply clues (iii) and (v) in Sub-case 1 (A = 2, B = 5, F = 6).

Remaining floors for C, D, E are {1, 3, 4}.
Clue (iii): C is immediately above D, so (D, C) is consecutive. From {1, 3, 4}, the only consecutive pair is (3, 4). So D = 3, C = 4.
Clue (v): E is below D. D = 3 → E must be on floor 1 or 2. Floor 2 is taken by A, so E = 1. Works.

Final arrangement (Sub-case 1):
Floor 6 — F
Floor 5 — B
Floor 4 — C
Floor 3 — D
Floor 2 — A
Floor 1 — E

Step 4: Apply clues (iii) and (v) in Sub-case 2 (A = 4, B = 1, F = 6).

Remaining floors for C, D, E are {2, 3, 5}.
Clue (iii): C immediately above D. From {2, 3, 5} the only consecutive pair is (2, 3). So D = 2, C = 3.
Clue (v): E is below D. D = 2, so E = 1. But floor 1 is taken by B. Sub-case rejected.

So only Sub-case 1 survives, giving the unique solution.

Step 5: Verify against every clue.

(i) A on floor 2 — even. Tick.
(ii) Floors between A (2) and B (5) — floors 3 and 4 are between them, so the gap is 3 floors. Tick.
(iii) C (4) is immediately above D (3). Tick.
(iv) F on floor 6. Tick.
(v) E (1) is below D (3). Tick.

All five clues are satisfied with no contradiction.

Why it matters: IBPS PO reasoning sections always test floor and seating puzzles. The model of case-splitting you just used — try every value of the most constrained variable, eliminate contradictions, finalise — is exactly the algorithm the exam rewards. Examiners deliberately seed clues that look contradictory at first, to catch students who give up too early.

Real-world example

This kind of reasoning isn't only for the exam. When you arrange wedding-hall seating, classroom benches, or even hospital ward bed assignments, you face the same constraint-satisfaction problem. The Indian Railways' RPF and a coaching centre's batch allocation both lean on identical logic. So this practice has real-life payoff.

Common misconception

Common misconception: Many students panic when an initial sub-case contradicts a clue and conclude that the problem is wrong. It is not. The contradiction is the signal — it tells you to discard that branch and try the next one. The discipline is to celebrate contradictions, not fear them. Every contradiction kills a case and brings you closer to the answer.

The interpretation trap

There is one genuine pitfall in IBPS-style puzzles: the phrase "X floors between A and B" can mean gap of X (i.e., X intermediate floors, so |A − B| = X + 1) in some books, or |A − B| = X in others. When practising, always check the answer-key's convention. In the actual exam, the unique solution itself tells you which interpretation the setter used — the correct interpretation is the one that yields exactly one consistent arrangement. If no arrangement fits, switch interpretation and re-solve.

:::compare

:::keypoints

• Always anchor the strongest clue first — usually an absolute clue like "topmost floor."
• "Even floor" gives at most three candidates — test each one systematically.
• "Three floors between A and B" can mean |A − B| = 3 or 4 depending on convention; use the one that yields a unique answer.
• A "block" clue like "C immediately above D" forces them onto two consecutive floors — list all consecutive pairs from the remaining set.
• Contradictions are progress, not failure — each contradiction eliminates a case.
• Always verify against every clue before locking your answer.
• The final arrangement here: E-1, A-2, D-3, C-4, B-5, F-6.
  :::

:::memory
"Top, then Tight, then Tied" — fix the topmost clue first, then handle the tight constraints (even/odd, distance), then apply the tied clues (blocks like C-above-D).
:::

:::recap

• Place absolute clues first (F = 6).
• Split into cases on constrained clues (A even = 2 or 4).
• Eliminate contradictions branch by branch.
• A unique arrangement is the proof your interpretation was right.
  :::

Dynamic Programming is one of the highest-yield areas in GATE Computer Science — it shows up directly in 2-mark coding/complexity questions and indirectly inside Algorithms numerical answer type problems. Most beginners "know DP" but freeze when asked which implementation style they used. The two canonical styles are Memoization and Tabulation, and the GATE examiner loves to test the differences.

Definition: Memoization (top-down DP) is plain recursion plus a lookup table — you solve a subproblem only when the recursion actually asks for it, and cache the answer for future calls.

Definition: Tabulation (bottom-up DP) is iteration over a table — you compute every subproblem in dependency order, smallest to largest, with no recursion stack involved.

The Same Recurrence, Two Personalities

Both styles target the same recurrence relation; they just differ in who triggers a subproblem. In memoization the demand is lazy — a subproblem is computed only when the recursion descends to it. The unvisited states stay empty in the table and consume zero time. In tabulation the demand is eager — you fill the entire table whether every entry is later needed or not. This is the single deepest distinction between the two and the source of most exam-trap questions.

Take the classic Fibonacci recurrence f(n) = f(n−1) + f(n−2). With memoization, computing f(5) visits exactly states {0, 1, 2, 3, 4, 5} — six work units. With tabulation, you also fill states 0 to 5 in order. Identical here. But change the problem to "longest common subsequence between strings of length 1000, only the final value needed" and you'll find that memoization typically computes fewer states because many (i, j) cells are simply unreachable, while tabulation always fills all 1000 × 1000 = 10^6 entries. That is the trade-off GATE will ask you to articulate.

Asymptotic Time: The Universal Shortcut

Both styles share the same big-O time complexity, captured by one line:

Time = (number of distinct subproblems) × (work done per subproblem in transitions)

Apply this and most DP complexity questions become trivial. Fibonacci has n subproblems and constant-time transitions, so time = O(n). 0/1 Knapsack has n × W subproblems with O(1) transitions, so O(nW). LCS has m × n subproblems with O(1) transitions, so O(mn). Matrix Chain Multiplication has O(n^2) subproblems but O(n) transition (the partitioning choice), so O(n^3). Internalise this counting rule — it has appeared verbatim in multiple GATE rubrics.

Why It Matters

GATE CSE numerical-answer-type questions on DP almost always reduce to (a) recognise the recurrence, (b) apply the state-count × transition-cost rule, and (c) decide whether top-down or bottom-up gives a tighter constant or memory profile. Engineers who know the what of DP but not the which lose easy marks. Equally important, in the interview rounds at Microsoft, Adobe, and several PSU technical interviews after qualifying GATE, candidates are asked exactly this comparison.

Memory and Stack Behaviour

Tabulation runs in a plain for-loop, so the only memory used is the table itself. Memoization runs through recursion, so it uses the table plus the call stack — and for very deep recurrences (n = 10^6 say) this can blow the default 1 MB stack and produce a StackOverflowError. That is one reason competitive programming culture prefers bottom-up.

Tabulation also enables space optimisation more naturally. For example, in Fibonacci you only ever need the last two table entries, so you can drop the array entirely and keep two variables, reducing space from O(n) to O(1). The same trick works for many "row-only depends on the previous row" DP problems like 0/1 Knapsack — keep just two rows instead of n. Memoization cannot easily do this because the recursion may revisit any past state.

Real-world example: When Google Maps computes the shortest route across India, it solves a DP-like shortest-path problem at scale. Tabulation-style algorithms are preferred precisely because they exploit predictable memory access patterns and avoid stack overflows on city-sized graphs.

Common misconception: "Top-down is always slower because of recursion overhead." False. When the search space is sparse — say, a chess-engine DP where 99% of board states are never reached — memoization can be dramatically faster than tabulation because it skips the unreachable cells entirely. The true rule is: bottom-up is faster when almost every state is needed; top-down is faster when only a few states are needed.

A Worked Example: Counting Paths in a Grid

Question: Count the number of paths from cell (0,0) to (m−1, n−1) in an m × n grid, moving only right or down. State the time and space complexity for both memoization and tabulation.

Solution:

Step 1: Define the recurrence. Let P(i, j) be the number of paths to (i, j). Then P(i, j) = P(i−1, j) + P(i, j−1), with P(0, 0) = 1 and P out-of-grid = 0.

Step 2: Count subproblems and transition cost. Number of distinct (i, j) states = m × n. Transition cost = O(1) (two table lookups and one addition).

Step 3: Time = m × n × 1 = O(mn) for both styles.

Step 4: Space. Memoization needs the m × n table plus a recursion stack up to depth O(m + n), so O(mn). Tabulation needs the m × n table, so O(mn) — but with row-only dependency we can reduce to O(min(m, n)) using a single rolling row.

Conclusion: Time complexity is identical at O(mn). Tabulation wins on memory thanks to space optimisation.

:::compare

:::keypoints

• Time complexity = (number of subproblems) × (work per transition) — true for both styles.
• Memoization computes only the states it actually visits; tabulation computes all of them.
• Memoization uses recursion stack; deep recurrences risk stack overflow.
• Tabulation enables space optimisation (e.g., rolling rows for O(n) → O(1) Fibonacci).
• Big-O is the same; constant factors and memory profile differ.
• Choose memoization for sparse state spaces, tabulation for dense ones.
• Always state the recurrence first; implementation choice is secondary.
  :::

:::memory
T-T-B-B: Top-down uses Table + recursion; Bottom-up uses Base case + loop. Top → Lazy. Bottom → Eager.
:::

:::recap

• Memoization and tabulation are two implementations of the same DP recurrence.
• Both share asymptotic time = states × transition cost.
• Tabulation is loop-based and space-friendly; memoization is recursion-based and skips unreached states.
• For GATE, always justify "I used DP because the recurrence has overlapping subproblems and optimal substructure" — then pick a style.
  :::

Speed tools:

• Map days/months to numbers: Mon=1...Sun=7; Jan=1...Dec=12. 'X is 3 days after Y' → day(X) = day(Y)+3.
• 'Between Tuesday and Friday' = Wed, Thu (exclusive) — 2 days; read inclusivity carefully.
• For 'who does the task on the day immediately before/after', use ±1 on the numeric scale.
• Multi-attribute GRID: rows = persons, columns = attributes; put a ✓ when forced, ✗ when ruled out. One ✓ in a row/column eliminates the rest.
• Start from the most constrained attribute (the one with the fewest options or most clues).
• Combine two single-link clues to form a chain (A-city, city-profession → A-profession).

Memory aid for days: 'My Tall Wife Took Five Sweet Sundaes' (M,T,W,T,F,S,S). For months use the day-count knuckle trick to handle dates.

Five persons V,W,X,Y,Z attend meetings on five consecutive days Mon-Fri (one each). Clues: (i) X's meeting is before W's but after V's. (ii) Y meets on Friday. (iii) Z does not meet on Monday.

Solve: Map Mon=1...Fri=5. From (i): V < X < W (in day order). Y = Friday (5). So V,X,W,Z occupy Mon-Thu. Z ≠ Monday → Monday is V, X, or W; since V < X < W, the earliest is V, so V = Monday (1) fits. Then X and W are after V. Z must take one of the remaining mid slots. A consistent fill: V=Mon, X=Tue, W=Wed, Z=Thu, Y=Fri — check: V<X<W ✓, Y=Fri ✓, Z≠Mon ✓.

The method: convert ordering clues to a numeric chain (V<X<W), anchor fixed days (Y=Fri), then place the constrained person (Z≠Mon) into a valid remaining slot. Verify every clue against the final schedule. This grid-plus-number-line technique generalizes to month and date scheduling puzzles too.