Sort sub array minimaly

Question

This is an interview question. Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n-m. i.e. find smallest sequence.

Answer 1

Observation

The integers before m should be ascending and smaller than (or equal to) any integers after.

Algorithm

1. Start from the first element, and stop upon first decreasing. (sub array SA)

2. Find minimum after. (MIN)

3. The start point is just after the maximum integer in SA that is smaller than (or equal to) MIN. (m is found)

Complexity

O(N)

---

Do similar for n.