Geek Answers Handbook

Sort sub array minimaly

This is an interview question. Given an array of integers, write a method to search for indices m and n such that if you sort elements m by n, the entire array will be sorted. Minimize nm. those. find the smallest sequence.

+8
algorithm
source share
2 answers

Observation

Integers up to m must be incrementing and smaller (or equal) integers after.

Algorithm

  • Start with the first element and stop at the first decrease. (sub array SA)

  • Find the minimum after. (MIN)

  • The starting point begins immediately after the maximum number in SA, which is less than (or equal to) MIN. (m found)

Complexity

O (N)

Similarly for n.

+6
source share

You need to track four things:

  • The end of the sorted area at the beginning
  • Start of sorted area at end
  • The minimum number after the starting area
  • The maximum number before the end area

Start by calculating the preliminary value for 1 and 2, by scanning the array from beginning to end until you find an inappropriate value.

Then you scan everything after preliminary 1 to find the minimum number. This is your 3. Find 4 in the same way.

Now you are returned through the starting area of ​​the array until you find the place where the minimum value should be. This is the exact answer to 1, as well as your m .

Find n in the same way, going back through the final region to find where the maximum number should be.

+4
source share

More articles:


All Articles