Part 2 · Lesson 11 · 20 min read
How to Read a Problem
Input, output, constraints, examples and edge cases — and solving it by hand before writing any code.
On this page
- Most wrong answers start with a misread question
- The five parts of every problem
- Reading the constraints
- Clarifying questions
- Solve the examples by hand
- Listing edge cases
- Brute force first, then improve
- Traced: the one-pass solution
- The eight-step method
- Explaining your thinking out loud
- Practice questions (7)
- Make it stick
- What's next
Most wrong answers start with a misread question
Part 1 gave you the tools: loops, functions, arrays, strings and Maps. Part 2 is about using these tools on problems you have never seen before. The first skill is not coding. It is reading the problem well.
In interviews, many candidates who fail could have written the code. They made one of three mistakes. They solved a slightly different problem from the one asked. They forgot the empty array. Or they started typing before they understood the examples.
This lesson gives you a fixed routine that prevents all three mistakes. It takes about five minutes, and it saves much more time than it costs.
The five parts of every problem
Interview problems and LeetCode problems all have the same shape. (LeetCode is a website with coding practice problems.) Here is one problem that we will use for the whole lesson:
Second largestGiven an array of numbers nums, return the second largest value.Example 1: nums = [4, 9, 7, 2] → 7Example 2: nums = [10, 5] → 5Constraints: 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9| Part | What it tells you | In this problem |
|---|---|---|
| Statement | The task in words | Find the second largest value |
| Input | What your function receives, and its type | nums, an array of numbers |
| Output | What your function must return, and its type | One number |
| Examples | Real input and output pairs. Use them to check that you understood the problem | [4, 9, 7, 2] → 7 |
| Constraints | Limits on the size and on the values of the input | Up to 100,000 numbers, negatives allowed, can be empty |
Before anything else, write the input and output as a function signature. A function signature is the function's name, its inputs and what it returns. It turns a paragraph of text into something concrete:
function secondLargest(nums) { // nums: number[] → returns a number // ...}Reading the constraints
Constraints are the rules about what input is allowed. Many people skip them, but they are the most useful part of a problem. Each line answers a question that you would otherwise have to guess:
| Constraint | What it means for your code |
|---|---|
0 <= nums.length | The array can be empty. Your code must return something sensible for []. |
nums.length <= 10^5 | Up to 100,000 values. Two nested loops (a loop inside a loop) would do about 100,000 × 100,000 = 10 billion steps. That is too slow. Lesson 12 shows how to judge this quickly. (10^5 means 10 to the power 5, which is 100,000.) |
-10^9 <= nums[i] | Values can be negative. Starting a “largest so far” variable at 0 would be a bug. (10^9 is one billion.) |
nums[i] <= 10^9 | Values fit easily in a JavaScript number. Even the sum of all of them (at most 1014) stays exact. JavaScript numbers are exact for whole numbers up to about 9 × 1015. |
“sorted”, “distinct” (all different), “non-negative” (0 or more), “exactly one answer”, “in place” (change the original array) and “any order”. Each of these words either removes a case that you would have to handle, or adds a rule that you must follow. Underline them.
Clarifying questions
Read the statement again and try [5, 5, 3]. Is the second largest value 5 (the second item in sorted order) or 3 (the second different value)? The problem does not say. Also, what should the function return for [] or [5]?
When a problem is not clear, ask. These are called clarifying questions. Interviewers often leave gaps on purpose, to see if you notice them. For this lesson, assume that the interviewer answered like this:
- “Second largest” means the second largest distinct value, so
[5, 5, 3]→ 3. - If there is no such value, return
null. (nullis a special value that means “nothing”.) Returning-1would be a bad choice here, because -1 can be a real value in the array.
The same kinds of questions are worth asking again and again:
| Ask about | Example question |
|---|---|
| Empty or tiny input | Can the array be empty? What should I return then? |
| Duplicates | Can values repeat? Do repeated values count separately? |
| Value range | Can numbers be negative or zero? Can they be very large? |
| Order | Is the input sorted? Does the order of my output matter? |
| No answer | What if no valid answer exists? Is there always exactly one? |
| Changing the input | May I modify the array, or must I leave it unchanged? |
Solve the examples by hand
Before you think about code, solve an example yourself, slowly. Then notice how you did it. Your own method is usually the first algorithm. (An algorithm is a list of clear steps that solves a problem.)
Most people scan the list once and keep the two biggest values in their head. This observation is the key: “I only need to remember two numbers.” It will become the efficient solution.
Listing edge cases
An edge case is a valid input at the very limit of what the problem allows. It is often the input that breaks a solution. Write the edge cases down before you code, and write the expected answer next to each. Then they become your tests.
| Input | Expected | Why it is tricky |
|---|---|---|
| [] | null | nothing to compare |
| [5] | null | only one value |
| [5, 5, 5] | null | all values equal |
| [7, 9] | 7 | largest is last |
| [9, 7] | 7 | largest is first |
| [-3, -1, -2] | -2 | all negative |
| [4, 9, 7, 9, 2] | 7 | the largest is repeated |
The same few edge cases fit almost every array problem: empty, one element, all equal, all negative, and the answer at the very start or very end.
Brute force first, then improve
A brute force solution is the simplest solution that is correct, even if it is slow. It tries everything. Always find one first, for three reasons. It proves that you understand the problem. It gives you something to test a faster solution against. And in an interview, a working slow answer is much better than an unfinished fast one.
Brute force here: sort the values from largest to smallest. Then take the first value that is smaller than the maximum.
function secondLargest(nums) { const sorted = [...nums].sort((a, b) => b - a); // largest first for (let i = 1; i < sorted.length; i++) { if (sorted[i] < sorted[0]) return sorted[i]; // first value smaller than the max } return null; // no second distinct value}console.log(secondLargest([4, 9, 7, 9, 2])); // 7console.log(secondLargest([5, 5, 5])); // nullconsole.log(secondLargest([])); // nullIt is correct, but sorting does more work than we need. It puts every value in order, and we only care about the top two. To improve a brute force, ask: what work is wasted or repeated? Here, the wasted work is the sorting. Our by-hand method needed only two variables and one pass. (A pass is one trip through the whole array.)
Traced: the one-pass solution
-Infinity is smaller than any number, so the first value we see will replace it. Starting at 0 would break on input with only negative numbers.
1function secondLargest(nums) {▶ let first = -Infinity;3 let second = -Infinity;4 for (const x of nums) {5 if (x > first) {6 second = first;7 first = x;8 } else if (x < first && x > second) {9 second = x;10 }11 }12 return second === -Infinity ? null : second;13}14console.log(secondLargest([4, 9, 7, 9, 2]));| nums | [4, 9, 7, 9, 2] |
| first | -Infinity |
Now test it against every row of the edge-case table. This is called a dry run: you follow the code by hand with an example input, and you do not run it on a computer. For [], the loop never starts. So second stays -Infinity and the function returns null. For [5, 5, 5], first becomes 5, and the two other 5s are skipped. So it also returns null. All seven rows pass.
The eight-step method
Use the same steps for every problem, from the easiest to the hardest:
- Restate the problem in your own words.
- Write down the input, the output and the constraints.
- Ask clarifying questions about anything unclear.
- Solve the examples by hand and notice your own method.
- List edge cases with their expected answers.
- Describe the brute force and how much work it does.
- Improve it by removing wasted or repeated work, then write the code.
- Test with a dry run on one example and on each edge case.
Steps 1 to 6 happen before you write any code. This is on purpose. If you write code before you understand the problem, you usually have to write it again.
Explaining your thinking out loud
In an interview, the interviewer judges your thinking, not only your final code. If you work in silence, they cannot help you. They also cannot give you credit for good ideas that you did not say. So talk through the eight steps. Simple sentences are enough:
| Step | What you might say |
|---|---|
| Restate | “So I need to return the second largest distinct value, or null if there isn't one.” |
| Ask | “Can the array be empty? Should duplicates of the maximum count?” |
| Brute force | “The simplest approach is to sort and scan. That works, but sorting is more than we need.” |
| Improve | “I only need the top two values, so I can track them in one pass.” |
| Code | “first holds the largest so far, second the runner-up…” |
| Test | “Let me dry-run [4, 9, 7, 9, 2], then check the empty array.” |
Practise this even when you are alone. When you say your reasoning out loud, you also notice your own mistakes sooner.
Practice questions
For each question, go through the eight steps on paper before you open any hint. Pay special attention to the constraints. Several of these questions change completely if you misread one line.
nums contains n distinct numbers taken from the range 0 to n (where n is the length of the array). Exactly one number from the range is missing. Return it.
Hint 1
0 to n, where n is the array length. Exactly one number is missing.Hint 2
Hint 3
n * (n + 1) / 2. Subtract the actual sum from it.Show all 3 solutions with explanations
For each number from 0 to n, check whether it is in the array. The first number that is not in the array is the answer.
function missingNumber(nums) { const n = nums.length; for (let k = 0; k <= n; k++) { if (!nums.includes(k)) return k; }}console.log(missingNumber([3, 0, 1])); // 2console.log(missingNumber([0, 1])); // 2console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8This is the brute force. It is correct, but includes is itself a loop over the array. So this is a loop inside a loop. Look at k <= n, not k < n. The second example shows that the answer can be n itself.
Put every value into a Set (a collection of unique values). Then check each number from 0 to n against the Set.
function missingNumber(nums) { const present = new Set(nums); for (let k = 0; k <= nums.length; k++) { if (!present.has(k)) return k; }}console.log(missingNumber([3, 0, 1])); // 2Each check is now very fast, so the work is two simple passes. The cost is extra memory for the Set.
- The full range 0…n adds up to
n * (n + 1) / 2. - Add up the values that are really in the array.
- The difference is the missing number.
function missingNumber(nums) { const n = nums.length; let expected = (n * (n + 1)) / 2; let actual = 0; for (const x of nums) actual += x; return expected - actual;}console.log(missingNumber([3, 0, 1])); // 2console.log(missingNumber([0, 1])); // 2console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8| Step | Value |
|---|---|
| n | 3 |
| expected = 3 × 4 / 2 | 6 |
| actual = 3 + 0 + 1 | 4 |
| return 6 − 4 | 2 |
Approach 3 is the best answer. It needs one pass and no extra memory. It works only because of the constraints: distinct values from exactly 0 to n. If the statement allowed duplicates, the sum trick would fail, and you would use the Set. (LeetCode 268.)
Return the average of the numbers in nums. If the array is empty, return 0.
Hint 1
Hint 2
0 / 0 in JavaScript?Show all 2 solutions with explanations
Add everything up and divide by the length.
function average(nums) { let sum = 0; for (const x of nums) sum += x; return sum / nums.length;}console.log(average([2, 4, 9])); // 5console.log(average([])); // NaN (wrong, it should be 0)For an empty array, sum is 0 and nums.length is 0. In JavaScript, 0 / 0 is NaN (“not a number”). JavaScript does not throw an error, so this bug is easy to miss. Only a test of the edge case finds it.
Return early for the empty array. Then do the normal calculation.
function average(nums) { if (nums.length === 0) return 0; let sum = 0; for (const x of nums) sum += x; return sum / nums.length;}console.log(average([2, 4, 9])); // 5console.log(average([])); // 0The early return (Lesson 7) keeps the edge case apart from the main logic, so both are easy to read.
The lesson here is the habit, not the code. Write the edge cases down first, with their expected answers, and test each one. A bug that throws no error is the hardest kind to notice.
Choose two different positions i and j and return the maximum value of (nums[i] - 1) * (nums[j] - 1).
Constraints: 2 ≤ nums.length ≤ 500, 1 ≤ nums[i] ≤ 1000.
Hint 1
2 <= nums.length <= 500 and 1 <= nums[i] <= 1000. Can nums[i] - 1 ever be negative?Hint 2
Hint 3
Show all 3 solutions with explanations
Use two nested loops over all pairs i < j. Keep the best product.
function maxProduct(nums) { let best = 0; for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { best = Math.max(best, (nums[i] - 1) * (nums[j] - 1)); } } return best;}console.log(maxProduct([3, 4, 5, 2])); // 12console.log(maxProduct([1, 5, 4, 5])); // 16This is correct. With at most 500 values it is fast enough (about 125,000 pairs). Starting best at 0 is safe only because the constraints guarantee that no product is negative.
Sort in increasing order. Then the two largest values are the last two.
function maxProduct(nums) { const s = [...nums].sort((a, b) => a - b); const n = s.length; return (s[n - 1] - 1) * (s[n - 2] - 1);}console.log(maxProduct([3, 4, 5, 2])); // 12console.log(maxProduct([1, 5, 4, 5])); // 16This is short and clear. Copying with [...nums] leaves the caller's array unchanged.
Scan the array once. Keep the largest and the second largest values.
function maxProduct(nums) { let first = 0; let second = 0; for (const x of nums) { if (x > first) { second = first; first = x; } else if (x > second) { second = x; } } return (first - 1) * (second - 1);}console.log(maxProduct([3, 4, 5, 2])); // 12console.log(maxProduct([1, 5, 4, 5])); // 16console.log(maxProduct([3, 7])); // 12Compare this with secondLargest from the lesson. There, we skipped a value equal to first. Here, that value must go into second, because two equal values at different positions form a valid pair. The pattern is the same, but the rule is different. The examples told us which rule to use.
Approach 3 does the least work. Approach 2 is fine for 500 values. Both depend on the constraint that every value is at least 1. Question 4 shows what happens when this constraint is removed. (LeetCode 1464.)
Given an array of at least two integers, which may be negative, return the largest product of two numbers at different positions.
Hint 1
Hint 2
Hint 3
Show all 3 solutions with explanations
Use the same nested loops as before. But best cannot start at 0 now.
function maxPairProduct(nums) { let best = -Infinity; for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { best = Math.max(best, nums[i] * nums[j]); } } return best;}console.log(maxPairProduct([-10, -9, 1, 3])); // 90console.log(maxPairProduct([-5, 2])); // -10The brute force still works. This is why it is useful: you can check a faster solution against it. If best started at 0, the last example would wrongly return 0.
After sorting, the two smallest values are at the start and the two largest values are at the end. Compare the two products.
function maxPairProduct(nums) { const s = [...nums].sort((a, b) => a - b); const n = s.length; return Math.max(s[0] * s[1], s[n - 1] * s[n - 2]);}console.log(maxPairProduct([1, 5, 4, 5])); // 25console.log(maxPairProduct([-10, -9, 1, 3])); // 90console.log(maxPairProduct([-5, 2])); // -10Every other pair gives a smaller product than one of these two. When the array has only two items, both products are the same pair, so the answer is still correct.
Track the two largest and the two smallest values in one scan.
function maxPairProduct(nums) { let max1 = -Infinity, max2 = -Infinity; let min1 = Infinity, min2 = Infinity; for (const x of nums) { if (x > max1) { max2 = max1; max1 = x; } else if (x > max2) { max2 = x; } if (x < min1) { min2 = min1; min1 = x; } else if (x < min2) { min2 = x; } } return Math.max(max1 * max2, min1 * min2);}console.log(maxPairProduct([-10, -9, 1, 3])); // 90console.log(maxPairProduct([-5, 2])); // -10There are two separate “top two” trackers in the same loop. Notice the two separate if chains. One value can update both the maximums and the minimums.
Compare this with Question 3. One changed line in the constraints (values can be negative) made the earlier solution wrong. This is why step 2 of the method (write down the constraints) comes before any code.
Return the third largest distinct number in nums. If it does not exist, return the largest number.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Remove duplicates. Sort from largest to smallest. Pick position 2 (the third item) if it exists.
function thirdMax(nums) { const distinct = [...new Set(nums)].sort((a, b) => b - a); return distinct.length >= 3 ? distinct[2] : distinct[0];}console.log(thirdMax([3, 2, 1])); // 1console.log(thirdMax([1, 2])); // 2console.log(thirdMax([2, 2, 3, 1])); // 1This is a direct translation of the statement. Each phrase becomes one piece of code. “Distinct” becomes a Set. “Third” becomes index 2. “Otherwise the maximum” becomes index 0.
Keep the three largest distinct values in a ≥ b ≥ c. When a bigger value arrives, move the old values down one place.
function thirdMax(nums) { let a = -Infinity, b = -Infinity, c = -Infinity; for (const x of nums) { if (x === a || x === b || x === c) continue; // already counted, so skip it (continue starts the next loop round) if (x > a) { c = b; b = a; a = x; } else if (x > b) { c = b; b = x; } else if (x > c) { c = x; } } return c === -Infinity ? a : c;}console.log(thirdMax([3, 2, 1])); // 1console.log(thirdMax([1, 2])); // 2console.log(thirdMax([2, 2, 3, 1])); // 1| x | a | b | c | what happened |
|---|---|---|---|---|
| 2 | 2 | -Infinity | -Infinity | new largest |
| 2 | 2 | -Infinity | -Infinity | equal to a, so skipped |
| 3 | 3 | 2 | -Infinity | new largest, 2 moves down |
| 1 | 3 | 2 | 1 | fills c |
c is set, so the answer is c = 1.
Approach 1 is easier to get right and is fine for interviews. Approach 2 uses only three variables. It is a good follow-up if the interviewer asks you to avoid extra memory. (LeetCode 414.)
String t is made by shuffling string s and then adding one more letter at a random position. Return the added letter. Both contain lowercase letters only.
Hint 1
Hint 2
Hint 3
Show all 3 solutions with explanations
Count every letter of s. Then walk through t and use up the counts. The first letter that has no count left is the extra one.
function findTheDifference(s, t) { const freq = new Map(); for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1); for (const ch of t) { const left = freq.get(ch) ?? 0; if (left === 0) return ch; freq.set(ch, left - 1); }}console.log(findTheDifference("abcd", "abcde")); // econsole.log(findTheDifference("", "y")); // yconsole.log(findTheDifference("a", "aa")); // aThis is the frequency map from Lesson 10. Example 3 shows why we count and do not only check if a letter is there: “a” is in s, but t has one more “a”.
Sort the letters of both strings. They match at every position until the extra letter.
function findTheDifference(s, t) { const a = [...s].sort(); const b = [...t].sort(); for (let i = 0; i < a.length; i++) { if (a[i] !== b[i]) return b[i]; } return b[b.length - 1]; // the extra letter sorts to the end}console.log(findTheDifference("abcd", "abcde")); // econsole.log(findTheDifference("a", "aa")); // aThe last line handles the case where every letter of s matched. Then the extra letter is the last one in the sorted t.
Add up the codes of t. Subtract the codes of s. Everything cancels out except the extra letter.
function findTheDifference(s, t) { let total = 0; for (const ch of t) total += ch.charCodeAt(0); for (const ch of s) total -= ch.charCodeAt(0); return String.fromCharCode(total);}console.log(findTheDifference("abcd", "abcde")); // econsole.log(findTheDifference("", "y")); // yThis is the “expected sum minus actual sum” idea from Question 1, used on letters. It needs no extra memory at all.
Approach 1 is the most general and the easiest to explain. Approach 3 is the shortest and uses no extra memory. Mention it as an improvement. (LeetCode 389.)
A pair of positions (i, j) is good if nums[i] === nums[j] and i < j. Return the number of good pairs.
Hint 1
i < j. Write it first.Hint 2
Hint 3
Show all 2 solutions with explanations
Use two nested loops. Count the pairs that have equal values.
function numIdenticalPairs(nums) { let pairs = 0; for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] === nums[j]) pairs++; } } return pairs;}console.log(numIdenticalPairs([1, 2, 3, 1, 1, 3])); // 4console.log(numIdenticalPairs([1, 1, 1, 1])); // 6The brute force follows the statement word for word, so it is easy to trust. Use it to check the faster version.
For each value, add the number of times you have already seen it to the total. Then increase its count by 1.
function numIdenticalPairs(nums) { const seen = new Map(); let pairs = 0; for (const x of nums) { const before = seen.get(x) ?? 0; pairs += before; // pairs with every earlier equal value seen.set(x, before + 1); } return pairs;}console.log(numIdenticalPairs([1, 2, 3, 1, 1, 3])); // 4console.log(numIdenticalPairs([1, 1, 1, 1])); // 6console.log(numIdenticalPairs([1, 2, 3])); // 0| x | seen before | pairs |
|---|---|---|
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| 1 | 2 | 3 |
| 1 | 3 | 6 |
This is the “brute force, then improve” step in action. The nested loop repeats work, because it scans the earlier values again and again. The Map remembers them instead. Lesson 12 shows how to measure the difference exactly. (LeetCode 1512.)
Make it stick
- Write the eight steps from memory, in order.
- List five clarifying questions you could ask about almost any array problem.
- Take any LeetCode problem you have not solved and do only steps 1–6 for it, without writing code.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
Several times in this lesson we said that a solution was “too slow” or “more work than needed”. Lesson 12 makes this exact with Big-O. Big-O is a simple way to count how much work code does. With it, you can decide from the constraints alone which approach will be fast enough.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series