TADM2E 4.2

From Algorithm Wiki
Revision as of 22:33, 14 January 2018 by Rdc5174 (Talk | contribs)

Jump to: navigation, search

(a) Iterate over the array once, keeping track of the max and min values respectively for x and y. This will have $ O(n) $ worst-case time.

(b) The answer is straight forward: $ S[1] $ and $ S[n], $ since they are the two extreme values.

(c) Sort the array with any $ n\log(n) $ method. Then scan through the sorted array to find the smallest gap, thus the desired pair.

(d) Same as above.