When solving algorithmic problems, the first milestone is often earning the green Accepted badge. That is certainly satisfying, but I have always been drawn to something deeper understanding why an algorithm works.
Interestingly, this experience came while I’d solved only around 40 LeetCode problems. Rather than treating the problem as just another submission, I found myself questioning one step of the standard algorithm. That curiosity led me to investigate the LeetCode Next Permutation problem more deeply, test an alternative implementation, discover a counter-example, and eventually contribute feedback that the LeetCode team used to enhance the problem. As recognition, my account was credited with 100 LeetCoins.
This article is not about finding a bug in LeetCode. It is about how questioning a single step of an algorithm became a valuable learning experience.
Table of Contents
What Is a Permutation?
Before discussing the problem itself, it helps to understand what a permutation is.
A permutation is simply an arrangement of elements in a particular order. For example, if we have the numbers [1, 2, 3], then all possible permutations include:
- [1, 2, 3]
- [1, 3, 2]
- [2, 1, 3]
- [2, 3, 1]
- [3, 1, 2]
- [3, 2, 1]
Each of these is a different ordering of the same elements.
If we have n distinct elements, the total number of possible permutations is n! (n factorial). For example:
- 3 elements → 3! = 6 permutations
- 4 elements → 4! = 24 permutations
- 5 elements → 5! = 120 permutations
So as the size of the input grows, the number of possible arrangements increases very quickly.
If the array contains duplicate values, the number of unique permutations is smaller than n!, because some arrangements repeat.
In the LeetCode Next Permutation problem, the goal is to find the next arrangement that is just slightly larger in lexicographic order. In other words, we want the next permutation that would appear if all permutations were sorted like words in a dictionary.
What Is the Next Permutation Problem?
The Next Permutation problem asks us to transform an array into its next lexicographically greater permutation.
For example:
Input:
[1, 2, 3]
Output:
[1, 3, 2]
If the current permutation is already the largest possible, such as:
[3, 2, 1]
the answer becomes:
[1, 2, 3]
The challenge is to perform this transformation in place using constant extra memory.
Read More Articles:
The Standard Algorithm
The accepted algorithm consists of three key steps.
Step 1: Find the Pivot
Starting from the right side of the array, locate the first element that is smaller than the element immediately after it.
This element is called the pivot.
Step 2: Swap the Pivot
Next, find the smallest element greater than the pivot on its right side and swap them.
This guarantees that the new permutation becomes larger than the current one.
Step 3: Reverse the Remaining Suffix
Finally, reverse every element to the right of the pivot.
At first, this looked like a routine step.
But it also made me curious.
Why do we reverse the suffix?
Is reversing always necessary, or could swapping alone produce the next permutation?
Instead of accepting the algorithm as it was, I decided to test that assumption.
My Experiment
To answer my own question, I intentionally modified the implementation.
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
pivot, n = -1, len(nums) # pivot hold the index
# Finding the pivot index
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
pivot = i
break
# Edge case if the permutation is last
if pivot == -1:
nums.reverse()
return
# Swap pivot index value with the minimum number from right of the list
# for i in range(n - 1, pivot, -1):
# if nums[i] > nums[pivot]:
# nums[i], nums[pivot] = nums[pivot], nums[i]
# break
nums[n-1], nums[pivot] = nums[pivot], nums[n-1] # ISSUE!!!
# Reverse the right list of numbers from pivot
nums[pivot + 1:] = reversed(nums[pivot + 1:])Instead of searching for the smallest element greater than the pivot, I simply swapped the pivot with the final element.
The standard implementation looks like this:
for i in reversed(range(pivot + 1, n)):
if nums[i] > nums[pivot]:
nums[i], nums[pivot] = nums[pivot], nums[i]
breakFor my experiment, I replaced it with:
nums[pivot], nums[last_index] = nums[last_index], nums[pivot]Here, last_index means the final position in the array.
Everything else in the algorithm remained unchanged.
The purpose was not to improve the algorithm.
It was simply to test whether my assumption could hold.
Searching for a Counterexample
Initially, the modified implementation appeared to work.
Several common test cases produced the correct answer.
However, passing a handful of examples does not prove an algorithm is correct.
So I started generating and testing different permutations, especially cases involving duplicate values.
Eventually, I found the following input:
[1, 5, 1]
This was exactly the kind of counterexample I had been looking for.
My modified implementation failed, while the standard algorithm produced the correct result.
That single test case demonstrated why the complete algorithm is necessary and why simply swapping with the final element is not sufficient.
More importantly, it reinforced an important lesson:
A few passing examples never prove correctness. A single counterexample is enough to disprove an assumption.
Understanding Why the Reverse Step Matters
Finding the counterexample answered my original question.
After the pivot is swapped, the suffix is still arranged in descending order.
If we leave it unchanged, we obtain a permutation that is larger, but not necessarily the smallest possible larger permutation.
Reversing the suffix converts it into ascending order, producing the smallest arrangement after the pivot.
That is precisely what guarantees the result is the next permutation rather than just another larger permutation.
Understanding this reasoning helped me appreciate the elegance of the algorithm much more than simply memorizing its steps.
Reporting the Findings
Once I verified the behavior, I documented:
- The reasoning behind the experiment
- The modified implementation
- The counterexample
- Why the standard algorithm remains correct
I submitted everything through LeetCode’s public GitHub feedback repository.
After reviewing the report, the LeetCode team responded that my feedback had been used to enhance the problem and credited my account with 100 LeetCoins.
Although LeetCode does not publicly disclose which hidden test cases are added or modified, it was rewarding to know that my investigation contributed to improving a problem used by developers around the world.
Lessons I Learned
This experience taught me several valuable lessons.
1. Curiosity is a powerful learning tool.
The investigation started with a simple question:
Is this step really necessary?
Sometimes, asking why teaches more than simply learning how.
2. Edge cases reveal the truth.
Many incorrect solutions pass common examples.
Carefully chosen counterexamples often expose hidden assumptions that ordinary testing misses.
3. Understanding beats memorization.
I could have memorized the algorithm and moved on.
Instead, investigating its reasoning helped me understand why every step exists.
That understanding will stay with me much longer than the code itself.
4. Technical communication matters.
Finding an interesting result is only part of the process.
Explaining it clearly, documenting the reasoning, and communicating it effectively are equally important skills for every software engineer.
Final Thoughts
This was not a major breakthrough or a revolutionary discovery.
It was simply an example of what can happen when curiosity meets careful experimentation.
By questioning one step of a well known algorithm, testing an alternative implementation, and searching for counterexamples, I gained a much deeper understanding of the problem than I would have by stopping at an Accepted solution.
For me, that is one of the most rewarding aspects of computer science.
Sometimes, the best way to learn is not by accepting an algorithm.
It is by asking why it works in the first place.
