Best way to find a number in an array that's out of order?
Data Structures & Algorithms practice on Codemia
Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.
Introduction
Before you choose an algorithm, define what “out of order” means. In most interview and production cases, it means an array that should be sorted except for one misplaced value or one inversion. Once that assumption is explicit, the best solution is usually a linear scan, not a more complicated data structure.
Detect the First Inversion
If the array is supposed to be ascending, the simplest test is to compare each element with the one after it. The first index where arr[i] > arr[i + 1] marks an ordering violation.
This tells you where the sorted order breaks. It is O(n) time and O(1) extra space, which is already optimal for a general array scan because you may need to inspect every value.
Find the Actual Misplaced Value
Sometimes the goal is not just to find the inversion point but to identify which value is wrong in an almost-sorted array. A practical approach is to locate the first and last indices where order is violated and then inspect the surrounding values.
This is a better answer when the real problem is “which subarray must be fixed so the whole array becomes sorted.” It is still linear time.
When a Single Value Is the Obvious Offender
In a nearly sorted array, one element often violates the relation to both neighbors. You can detect that directly.
That result shows an important detail: an inversion usually involves two neighboring values, and the truly misplaced one depends on the context. In the example above, 9 is the value that should move to the right, but 5 also participates in the broken ordering.
Why Sorting First Is Usually the Wrong First Step
A common beginner answer is to sort the array and compare it with the original. That works, but it costs O(n log n) time and extra memory unless the array is modified in place. If you only want to find the anomaly in an already almost-sorted sequence, sorting throws away information that a single pass already exposes.
Use sorting only if you need the corrected final order anyway and the original cost is acceptable. If the task is detection, scanning is simpler and faster.
Common Pitfalls
- Not defining whether the array should be ascending or descending.
- Assuming one bad comparison always identifies one uniquely bad value.
- Sorting the entire array when a linear scan would answer the question.
- Forgetting edge cases at index
0and the last index. - Confusing “first inversion” with “smallest subarray that must be repaired.”
Summary
- For most cases, the best first tool is a linear scan for inversions.
- '
arr[i] > arr[i + 1]is the key test in an ascending array.' - If you need the repair range, find the unsorted window instead of just one bad index.
- Sorting and comparing works, but it is usually more work than necessary.
- Be explicit about the exact definition of “out of order” before you optimize.
Related reading
- Best way to find first non repeating character in a string
- Best way to list files in Java, sorted by Date Modified?
- Best way to reduce sequences in an array of strings
- Best way to retrieve K largest elements from large unsorted arrays?
- Best way to find if an item is in a JavaScript array?
- Best way to find the intersection of multiple sets?
- Best way to Format a Double value to 2 Decimal places
- Best way to get distribute a small lookup file using Distributed Cache

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseData Structures & Algorithms practice on Codemia
Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.