This page needs a newer browser to run its tools. You can still read everything here.

Two pointers interview questions

Interview questions on two pointers: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

16 questions: 2 warm-ups and 14 with model answers · Levels: Fresher to senior

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

Why is the converging pair search on a sorted list O(n), not O(n²)?

Answered in the lesson Two pointers: converging and reader–writer
Fresher

What does the write pointer mean in an in-place compaction?

Answered in the lesson Two pointers: converging and reader–writer

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Fresher to mid

An unsorted array holds a million integers, each up to 10⁹ in size. Return the original positions of two of them that add up to a target. Would you sort and use two pointers, or use a hash map? Compare time, memory and what each approach can return.
What it tests

Choosing between sorting with converging pointers and one hashing pass by time, memory and output, and keeping the original positions through a sort.

First step

Notice that sorting moves the values away from their positions, which are the answer. So the sorting approach must sort (value, position) pairs or the positions themselves. Then cost both: one pass with a hash map is O(n) expected time and O(n) memory; sorting is O(n log n) time and O(n) memory for the pairs.
Follow-ups
- The array is already sorted. What changes?
- Extra memory must be O(1), and you may reorder the array.
- You must return every pair that adds up to the target, not just one.
From the lesson Two pointers: converging and reader–writer
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; nothing renews unless you choose to. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

An array is sorted by absolute value, for example [-1, 2, -3, 4, -6]. Can converging pointers find two values with a given sum directly? If not, how do you still find a pair in O(n) time?
What it tests

Knowing which property makes converging pointers correct, finding a counterexample when it is missing, and recovering sorted order from structure that is already in the input.

First step

Check the property the method needs: moving lo right must never make the sum smaller, and moving hi left must never make it larger. Here moving from 2 to -3 makes it smaller, so try target 1 by hand. Then look for sorted runs hidden in the array: its negative values and its other values.
Follow-ups
- Do it with O(1) extra memory.
- The target is 0.
- Count the pairs instead of finding one.
From the lesson Two pointers: converging and reader–writer
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Fresher to mid

To keep at most k copies of each value of a sorted array in place, a candidate's loop keeps a[r] when r < k or a[r] != a[r − k], and writes kept values forward. Is that right? Find an input that decides it, and explain what the test really checks.
What it tests

Knowing which positions still hold the input during an in-place pass, and turning a doubt about a test into a small counterexample.

First step

Ask what the positions below the writer hold once it has fallen behind the reader: kept values copied forward, not the original items. Then trace k = 2 by hand on a short sorted array with repeats, and watch position r − k at every step.
Follow-ups
- Why does the reader-based test work for k = 1?
- What does each version return for k = 0?
- How would you find such a bug without guessing the input?
From the lesson In-place compaction with reader–writer pointers
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A Python solution removes duplicates from a sorted list by calling del a[i] whenever a[i] equals a[i − 1]. It passes the sample tests and times out on a hidden test with a million items. Explain the cost, estimate the time, and fix it.
What it tests

Seeing the linear cost hidden in one list operation, estimating the total for the worst input, and replacing deletion with an in-place copy.

First step

Find the worst input first: a million copies of one value, so that almost every item is deleted near the front of a long list. Then count how many items each deletion moves, and add the counts.
Follow-ups
- Would a.pop(i) or a.remove(x) be any faster?
- The list must not be changed at all. What do you return?
- Is building a new list with a comprehension acceptable here?
From the lesson In-place compaction with reader–writer pointers
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

The same task on unsorted data: keep at most k copies of each value of an array of a million integers, in place, keeping the original order of the kept items. What changes, what does it cost in time and memory, and what can you offer if extra memory must be O(1)?
What it tests

Recognising the property the sorted look-back depends on, counting copies with a hash map instead, and weighing the alternatives when memory is tight.

First step

Check why the sorted version works: copies of a value are adjacent, so the end of the kept part decides. Without sorting that fails, so you need to know how many copies of each value are kept already: one count per distinct value.
Follow-ups
- The values are known to lie between 0 and 1,000.
- Extra memory must be O(1), and the order must still be kept.
- The array is a stream that does not fit in memory.
From the lesson In-place compaction with reader–writer pointers
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

In the one-pass three-way partition, each swap sends a value to one end of the list. After which swaps may mid move on, and after which must it stay? Derive both rules from the invariant, and find a small input that breaks a version with the wrong rule.
What it tests

Deriving pointer moves from an invariant instead of memorising them, and producing a minimal counterexample.

First step

Write down the four regions and the pointer on each border. Then ask, for each kind of swap, where the value that arrives at mid came from: from the region of values equal to the pivot, or from the region not examined yet.
Follow-ups
- Why is a swap of a value with itself harmless?
- What does the buggy version return for a one-element list?
- How do you test a partition so that this cannot slip through?
From the lesson Dutch national flag: three-way partitioning
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Your hand-written quicksort sorts a million exam marks from 0 to 100 and is far slower than on a million distinct values. Explain why, estimate the comparisons, and fix it. What does your fix cost on distinct values?
What it tests

Connecting how a partition step treats equal keys with the running time of quicksort, estimating with numbers, and knowing the trade-off of the fix.

First step

Find out which partition step the quicksort uses and where it sends keys equal to the pivot. With 101 distinct marks each mark has about 10,000 copies, so work out what the sort costs on one block of 10,000 equal keys.
Follow-ups
- Would a random pivot fix it?
- Does your language's built-in sort have this problem?
- The marks are known to be 0 to 100. Is quicksort the right tool at all?
From the lesson Dutch national flag: three-way partitioning
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

You must group a million order records into overdue, due today and later, in place, keeping the original order inside each group. Can the one-pass swap partition do it? What are your options, and what does each cost?
What it tests

Knowing that the swap partition is not stable, and choosing between extra memory and extra moves for a stable grouping.

First step

Run the swap partition by hand on a short list in which one group has two records in a known order, and see whether they come out in that order. Then list what a stable grouping needs: somewhere to put records, or more moves.
Follow-ups
- Memory allows one extra array of n references.
- Only O(1) extra memory is allowed.
- The groups are only needed one at a time, for printing.
From the lesson Dutch national flag: three-way partitioning
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

Array a holds m sorted values followed by n spare slots, and b holds n sorted values. Merge b into a without a second array. In which order must the slots of a be written so that no value is overwritten before it is read? Prove it with an invariant.
What it tests

Seeing where an in-place merge may write, and justifying the order of the writes with an invariant.

First step

Run the first step of a merge that writes a[0] first on a small case where b's first value is the smallest, and see what it destroys. Then ask which value belongs in each end slot of a, and whether that slot holds anything still unread.
Follow-ups
- What if the spare room were at the front of a?
- Which value do you write on a tie, and why does it matter?
- When b runs out first, what is left to do? And when a runs out first?
From the lesson Merge two sorted arrays in place
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A sorted list of 10⁸ customer IDs is on disk, and a sorted list of 1,000 flagged IDs fits in memory. Find the flagged IDs that are customers. Compare a parallel scan, binary searches and galloping, by comparisons and by disk reads.
What it tests

Choosing an intersection method from the sizes, estimating comparisons, and counting the input and output cost, not only the work of the processor.

First step

Count first: a scan touches all 10⁸ IDs once, while 1,000 binary searches touch about 1,000 × 27 entries. Then ask what one comparison costs when the long list is on disk: a block read, not a memory access.
Follow-ups
- The flagged list grows to 10⁷ IDs.
- The IDs on disk are in blocks of 4 KB. How many block reads does each method need?
- Both lists are streams that arrive in order.
From the lesson Merge two sorted arrays in place
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

You get one log of 10⁶ characters and 10⁵ codes of up to 20 characters. For each code, decide whether it is a subsequence of the log. A two-pointer check costs O(10⁶) per code. What do you precompute, what does it cost in time and memory, and what is the total?
What it tests

Recognising repeated scans of one text, trading memory for query time, and estimating both with numbers.

First step

Multiply first: 10⁵ codes × 10⁶ characters is up to 10¹¹ steps. The work every scan repeats is finding the next occurrence of a letter after a position, so precompute something that answers exactly that question quickly.
Follow-ups
- The alphabet is 26 lowercase letters. Can a query take O(code length) with no binary search?
- Memory is limited to 64 MB.
- The log keeps growing while queries arrive.
From the lesson Merge two sorted arrays in place
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A candidate decides in O(n) whether a string becomes a palindrome after deleting at most one character, by trying only a few deletions. Which deletions must be tried, and why can no other deletion be the only fix? Prove it.
What it tests

Proving a greedy step instead of trusting it, with a case analysis of where the deleted character can be.

First step

Name the first mismatch (lo, hi) and split the possible deleted positions into three groups: strictly between lo and hi, before lo, and after hi. For each group, ask which characters face each other after the deletion.
Follow-ups
- Is it enough to try only the left character?
- What is the cost, and can it be done without slicing?
- How would you test the claim?
From the lesson Two pointers on strings: palindromes and edits
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Generalise the one-deletion palindrome check to at most k deletions, for strings of up to 10⁵ characters and k up to 100. How does the cost grow with k, what does caching change, and what would you use for the largest inputs?
What it tests

Turning a greedy check into a search, bounding its states, and choosing a banded dynamic programme with its cost.

First step

Write the two tries as a search with a budget of k: at each mismatch it branches twice and spends one deletion. Count the branches for k deletions without sharing any work, then ask which states can repeat.
Follow-ups
- How many states does the cache hold?
- k is 1 or 2. Is the recursion fine?
- Return which characters to delete, not just yes or no.
From the lesson Two pointers on strings: palindromes and edits
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A product team wants a palindrome check for display names in any language, ignoring case and punctuation. Where does comparing code points after lower() go wrong, and what would you compare instead? Give concrete inputs.
What it tests

Knowing the traps of comparing text: case folding, normalisation, grapheme clusters and length changes, and turning them into a stated rule.

First step

Ask what a character means to the user: what they see, not a code point. Then try three inputs by hand: a word with ß, a word with an accented letter that can be stored in two ways, and a flag emoji.
Follow-ups
- Which of these can you handle with Python's standard library alone?
- What changes in JavaScript or Java?
- How do you keep it O(n) and avoid building big copies?
From the lesson Two pointers on strings: palindromes and edits
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes

The lessons of this module

Two pointers: converging and reader–writer Free lesson, Pro answers: 25 minutes
In-place compaction with reader–writer pointers Free intro, Pro: 4 of 20 minutes free
Dutch national flag: three-way partitioning Free intro, Pro: 4 of 20 minutes free
Merge two sorted arrays in place Free intro, Pro: 5 of 20 minutes free
Two pointers on strings: palindromes and edits Free intro, Pro: 5 of 25 minutes free

All Coding Interview Patterns interview questions · The Coding Interview Patterns track

Warm-up questions

Why is the converging pair search on a sorted list O(n), not O(n²)?

What does the write pointer mean in an in-place compaction?

Questions with model answers

An unsorted array holds a million integers, each up to 10⁹ in size. Return the original positions of two of them that add up to a target. Would you sort and use two pointers, or use a hash map? Compare time, memory and what each approach can return.

An array is sorted by absolute value, for example [-1, 2, -3, 4, -6]. Can converging pointers find two values with a given sum directly? If not, how do you still find a pair in O(n) time?

To keep at most k copies of each value of a sorted array in place, a candidate's loop keeps a[r] when r < k or a[r] != a[r − k], and writes kept values forward. Is that right? Find an input that decides it, and explain what the test really checks.

A Python solution removes duplicates from a sorted list by calling del a[i] whenever a[i] equals a[i − 1]. It passes the sample tests and times out on a hidden test with a million items. Explain the cost, estimate the time, and fix it.

The same task on unsorted data: keep at most k copies of each value of an array of a million integers, in place, keeping the original order of the kept items. What changes, what does it cost in time and memory, and what can you offer if extra memory must be O(1)?

In the one-pass three-way partition, each swap sends a value to one end of the list. After which swaps may mid move on, and after which must it stay? Derive both rules from the invariant, and find a small input that breaks a version with the wrong rule.

Your hand-written quicksort sorts a million exam marks from 0 to 100 and is far slower than on a million distinct values. Explain why, estimate the comparisons, and fix it. What does your fix cost on distinct values?

You must group a million order records into overdue, due today and later, in place, keeping the original order inside each group. Can the one-pass swap partition do it? What are your options, and what does each cost?

Array a holds m sorted values followed by n spare slots, and b holds n sorted values. Merge b into a without a second array. In which order must the slots of a be written so that no value is overwritten before it is read? Prove it with an invariant.

A sorted list of 10⁸ customer IDs is on disk, and a sorted list of 1,000 flagged IDs fits in memory. Find the flagged IDs that are customers. Compare a parallel scan, binary searches and galloping, by comparisons and by disk reads.

You get one log of 10⁶ characters and 10⁵ codes of up to 20 characters. For each code, decide whether it is a subsequence of the log. A two-pointer check costs O(10⁶) per code. What do you precompute, what does it cost in time and memory, and what is the total?

A candidate decides in O(n) whether a string becomes a palindrome after deleting at most one character, by trying only a few deletions. Which deletions must be tried, and why can no other deletion be the only fix? Prove it.

Generalise the one-deletion palindrome check to at most k deletions, for strings of up to 10⁵ characters and k up to 100. How does the cost grow with k, what does caching change, and what would you use for the largest inputs?

A product team wants a palindrome check for display names in any language, ignoring case and punctuation. Where does comparing code points after lower() go wrong, and what would you compare instead? Give concrete inputs.