Array searching
Out of order array
Data structures
Algorithm optimization
Programming techniques

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.

Practice algorithms

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.

python
1def first_inversion(nums):
2    for i in range(len(nums) - 1):
3        if nums[i] > nums[i + 1]:
4            return i, nums[i], nums[i + 1]
5    return None
6
7print(first_inversion([1, 2, 3, 7, 5, 6, 8]))
text
(3, 7, 5)

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.

python
1def misplaced_window(nums):
2    n = len(nums)
3    start = -1
4    end = -1
5
6    for i in range(n - 1):
7        if nums[i] > nums[i + 1]:
8            start = i
9            break
10
11    if start == -1:
12        return None
13
14    for i in range(n - 1, 0, -1):
15        if nums[i - 1] > nums[i]:
16            end = i
17            break
18
19    window_min = min(nums[start:end + 1])
20    window_max = max(nums[start:end + 1])
21
22    while start > 0 and nums[start - 1] > window_min:
23        start -= 1
24
25    while end < n - 1 and nums[end + 1] < window_max:
26        end += 1
27
28    return start, end, nums[start:end + 1]
29
30print(misplaced_window([1, 2, 6, 4, 5, 7, 8]))
text
(2, 4, [6, 4, 5])

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.

python
1def offending_values(nums):
2    result = []
3    for i, value in enumerate(nums):
4        left_ok = i == 0 or nums[i - 1] <= value
5        right_ok = i == len(nums) - 1 or value <= nums[i + 1]
6        if not (left_ok and right_ok):
7            result.append((i, value))
8    return result
9
10print(offending_values([1, 2, 3, 9, 5, 6, 7]))
text
[(3, 9), (4, 5)]

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 0 and 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.

Course
Intermediate
27 lessons
15 hours
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 course
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.

Practice algorithms