Monday, December 6, 2010

Subarray sorted

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

1 comment:

  1. Trivial solution: create a clone of the array, sort it, and then find first and last difference in the sorted and unsorted arrays. It takes O(n log n).

    Optimal solution (sketch):
    - find first (s) and last (e) index i s.t. arr[i] < arr[i+1]
    - find vs = min(arr[i]) with s<=i vs
    - set e to be the last index i s.t. arr[i] < ve

    it should work (except for some special cases, empty array, etc.)
    Infact, all elements before s are sorted, as well as the ones after e; elements before s are <= than those after s; elements after e are >= than those before e.

    Maurizio (from Cagliari)

    ReplyDelete