15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The two pointer technique keeps two indexes into the same sequence and moves them by a fixed rule instead of using nested loops. In the palindrome check, left starts at index 0 and right at n - 1, and both step inward after each matching pair. It runs in O(n) time and O(1) extra space.
| Pointers | left = 0, right = n - 1, moving inward |
|---|---|
| Loop condition | left < right; a single middle character needs no partner |
| Comparisons | At most floor(n / 2) pairs, 2 for "level" |
| Time | O(n) |
| Extra space | O(1), no reversed copy |
| Early exit | Return false on the first unequal pair |
The lesson uses three ideas:
n, valid indexes run from 0 through n - 1.text[0]."L" and "l" are different characters, and spaces and punctuation are characters too.We will check whether a string is a palindrome. A palindrome has matching mirrored characters from its two ends inward.
For text = "level":
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Character | l | e | v | e | l |
Keep two indexes into the same string:
left starts at the first character.right starts at the last character.The comparison is exact. The algorithm does not change case or skip spaces or punctuation.
Write this input:
1text = "level"Start at the two ends.
1Indexes: 0 1 2 3 4
2Characters: l e v e l
3 ^ ^
4 left rightAt the start:
left = 0right = 4[0, 4].text[0] with text[4].If they differ, the string cannot be a palindrome. Those two positions are mirrors of each other.
If they match, those positions are settled. Move both pointers inward:
1left = left + 1
2right = right - 1Two pointers on "level": the ends match at (0, 4), then (1, 3), and left = right = 2 meets at v, so 2 < 2 is false and the string is a palindrome.
The unprocessed interval is [0, 4].
Compare:
1text[left] = text[0] = l
2text[right] = text[4] = lThe characters match. Indexes 0 and 4 are now a verified mirrored pair.
Move both pointers:
1left = 1
2right = 3(0, 4)[1, 3]Compare:
1text[left] = text[1] = e
2text[right] = text[3] = eThey match. Move both pointers inward:
1left = 2
2right = 21Indexes: 0 1 2 3 4
2Characters: l e v e l
3 ✓ ✓ ^ ✓ ✓
4 left
5 right(0, 4) and (1, 3)[2, 2]Now left equals right. Both pointers point to the middle v.
There is no unmatched mirrored pair left to compare. Return true.
After the first comparison, the algorithm has established more than a match between the first characters.
Every mirrored pair outside the current pointer interval has already been checked and matched.
For example, after comparing indexes 0 and 4 in "level":
(0, 4) is known to match.1 through 3 still need attention.This is the loop invariant:
Before each comparison, every mirrored pair strictly outside the interval
[left, right]has been compared and matched. Only characters inside[left, right]remain to be checked.
The pointers only move inward:
left increases by one.right decreases by one.The inward movement prevents the algorithm from reconsidering already verified outer pairs.
First, handle the empty string.
An empty string has no unequal mirrored pair, so it returns true. Handle the empty-string check before setting right = n - 1, because an empty string has no last valid index.
For a nonempty string:
left to 0.right to n - 1.left < right, there is at least one mirrored pair still to compare.text[left] and text[right].
false immediately.left >= right, no unverified mirrored pair remains. Return true.The loop uses left < right, not left <= right.
When both pointers meet at one middle character, such as v in "level", that character does not need a mirrored partner.
Function contract
text, a string whose characters are compared exactly.true if every mirrored character pair matches; otherwise false.text.true.11 function isPalindromeExact(text) -> boolean
22 n = length(text)
33
44 if n == 0
55 return true
66
77 left = 0
88 right = n - 1
99
1010 while left < right
1111 if text[left] != text[right]
1212 return false
1313
1414 left = left + 1
1515 right = right - 1
1616
1717 return trueThe function compares the actual characters in text. It does not lowercase characters, remove punctuation, or skip spaces.
Use the same input:
1text = "level"| Pseudocode line | State and action |
|---|---|
| 2 | n = length("level") = 5 |
| 4 | Check n == 0. This is false, so do not return. |
| 7 | left = 0 |
| 8 | right = 5 - 1 = 4 |
| 10 | Check left < right: 0 < 4 is true. Enter the loop. |
| 11 | Compare text[0] and text[4]: l != l is false. Do not return false. |
| 14 | left = 0 + 1 = 1 |
| 15 | right = 4 - 1 = 3 |
| 10 | Check left < right: 1 < 3 is true. Enter the loop. |
| 11 | Compare text[1] and text[3]: e != e is false. Do not return false. |
| 14 | left = 1 + 1 = 2 |
| 15 | right = 3 - 1 = 2 |
| 10 | Check left < right: 2 < 2 is false. Leave the loop. |
| 17 | Return true. |
The final pointer state is:
1Indexes: 0 1 2 3 4
2Characters: l e v e l
3 ✓ ✓ ^ ✓ ✓
4 left
5 rightWe show that isPalindromeExact returns true exactly when all mirrored characters in text match.
If text is empty, line 5 returns true. There is no mirrored pair that can be unequal.
Otherwise, lines 7 and 8 set:
1left = 0
2right = n - 1No mirrored pairs lie strictly outside [0, n - 1]. Therefore, before the first comparison, the invariant holds: every mirrored pair outside the interval has been checked and matched, because there are no such pairs yet.
Assume the invariant holds at the start of a loop iteration.
The loop condition left < right means that text[left] and text[right] form an unverified mirrored pair.
text[left] != text[right], line 12 returns false. A palindrome requires every mirrored pair to be equal, so returning false is correct.Each successful iteration increases left and decreases right. Therefore, the interval [left, right] becomes smaller and the loop eventually ends unless a mismatch returns earlier.
When the loop ends, left >= right.
left == right, one middle character remains. It needs no paired comparison.left > right, the pointers have crossed. No characters remain in the unprocessed interval.By the invariant, every mirrored pair outside the interval has matched. Since no unverified mirrored pair remains, line 17 correctly returns true.
The function returns false on the first unequal mirrored pair and returns true exactly when all required mirrored pairs match.
Let n be the length of text.
In each successful loop iteration:
text[left] against text[right].left moves one position right.right moves one position left.Both pointers move inward together. At most floor(n / 2) mirrored pairs can be compared before they meet or cross.
For "level", where n = 5:
1floor(5 / 2) = 2The algorithm compares two pairs:
1(0, 4)
2(1, 3)The middle character is not compared with another character.
A mismatch can stop the algorithm earlier. For example, "ab" fails on its first comparison. In the worst case, the string has matching pairs until the pointers meet or cross, so the running time is:
1O(n)The algorithm stores only a constant number of values:
1n
2left
3rightIt does not create a reversed string or another string-sized structure. Its auxiliary space is:
1O(1)right to the lengthIncorrect line:
1right = length(text)Smallest exposing input:
1text = "aa"Wrong state:
1length(text) = 2
2right = 2
3text[right] means text[2]But valid indexes are only 0 and 1. Index 2 is invalid.
Correction:
1if n == 0
2 return true
3
4right = n - 1Handle the empty case before calculating the last valid index.
left after a matchIncorrect update:
1left = left + 1with no matching update to right.
Smallest exposing input:
1text = "aba"Wrong state:
1left = 0, right = 2
2text[0] = a and text[2] = a match
3
4left becomes 1
5right stays 2
6
7text[1] = b and text[2] = a differThe incorrect update returns false.
Correction:
1left = left + 1
2right = right - 1A matched mirrored pair must be removed from both ends of the unprocessed interval.
true after the first matching outer pairIncorrect assumption:
1If text[left] == text[right], return true.Smallest exposing input:
1text = "abca"Wrong state:
1text[0] = a
2text[3] = aThe outer pair matches, so the incorrect version returns true. But the next mirrored pair is:
1text[1] = b
2text[2] = cThese characters differ.
Correction: after a match, move both pointers and continue until they meet or cross.
Incorrect assumption:
1Convert characters to lowercase before comparing.Exposing input:
1text = "Level"Wrong output:
1trueAfter lowercasing, the text becomes "level", but that is not an exact comparison of the original input.
Correct output under the function’s contract:
1falsebecause:
1text[0] = L
2text[4] = lCorrection: compare actual input characters unless normalization is explicitly part of the function contract.
| Input | Result | Reason |
|---|---|---|
"" | true | No unequal mirrored pair exists. |
"x" | true | The single middle character needs no paired comparison. |
"aa" | true | Indexes 0 and 1 match. |
"ab" | false | Indexes 0 and 1 differ. |
"Level" | false | L and l differ under exact comparison. |
"a a" | true | The outer a characters match; the space is the center character. |
Implement:
1isPalindromeExact(text)Your function must:
true exactly when mirrored characters match.true for empty and one-character strings.The contract will test:
1def is_palindrome_exact(text):
2 n = len(text)
3 if n == 0: # no last index to point at
4 return True
5 left = 0
6 right = n - 1
7 while left < right: # left < right, not <=: the middle needs no partner
8 if text[left] != text[right]:
9 return False
10 left += 1 # move both pointers after a match
11 right -= 1
12 return True
13
14for word in ["level", "abca", "Level", "", "a a", "ab"]:
15 print(word + " " + ("true" if is_palindrome_exact(word) else "false"))1public class Main {
2 static boolean isPalindromeExact(String text) {
3 int n = text.length();
4 if (n == 0) return true; // no last index to point at
5 int left = 0;
6 int right = n - 1;
7 while (left < right) { // left < right, not <=: the middle needs no partner
8 if (text.charAt(left) != text.charAt(right)) return false;
9 left++; // move both pointers after a match
10 right--;
11 }
12 return true;
13 }
14
15 public static void main(String[] args) {
16 String[] words = {"level", "abca", "Level", "", "a a", "ab"};
17 for (String w : words) {
18 System.out.println(w + " " + (isPalindromeExact(w) ? "true" : "false"));
19 }
20 }
21}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6bool isPalindromeExact(const string& text) {
7 int n = (int)text.size();
8 if (n == 0) return true; // no last index to point at
9 int left = 0;
10 int right = n - 1;
11 while (left < right) { // left < right, not <=: the middle needs no partner
12 if (text[left] != text[right]) return false;
13 left++; // move both pointers after a match
14 right--;
15 }
16 return true;
17}
18
19int main() {
20 vector<string> words = {"level", "abca", "Level", "", "a a", "ab"};
21 for (const string& w : words) {
22 cout << w << " " << (isPalindromeExact(w) ? "true" : "false") << endl;
23 }
24}1function isPalindromeExact(text) {
2 const n = text.length;
3 if (n === 0) return true; // no last index to point at
4 let left = 0;
5 let right = n - 1;
6 while (left < right) { // left < right, not <=: the middle needs no partner
7 if (text[left] !== text[right]) return false;
8 left++; // move both pointers after a match
9 right--;
10 }
11 return true;
12}
13
14for (const word of ['level', 'abca', 'Level', '', 'a a', 'ab']) {
15 console.log(word + ' ' + (isPalindromeExact(word) ? 'true' : 'false'));
16}It is a pair of index variables over one sequence. The pointers start at the two ends and move toward each other, or both start at the front and move forward at different speeds. Each pointer only moves in one direction.
Use them when the answer depends on pairs of positions: mirrored characters, a pair that sums to a target in sorted data, or an in-place rewrite. If you can discard one end after each comparison, two pointers replace a nested loop.
Each pointer moves one way and never steps back. Each pointer makes at most n moves in total, so the work is linear. A nested loop over all pairs does about n^2 comparisons.
Use two int indexes over a std::string or vector and a while (left < right) loop, as in the C++ program above. Avoid unsigned indexes for the right pointer, because 0 - 1 wraps around.
A singly linked list has no index to start from the end, so move both pointers forward. Advance slow one node and fast two nodes. When fast reaches the end, slow is at the middle, and if fast meets slow there is a cycle.
When both pointers land on one character, such as v in "level", it has no mirrored partner. Using <= would compare it with itself, which is harmless for a palindrome but wrong for pair problems.