For each of the following problems, give an algorithm that finds the desired
numbers within the given amount of time. To keep your answers brief, feel free to
use algorithms from the book as subroutines. For the example, S = {6, 13, 19, 3, 8},
19 − 3 maximizes the difference, while 8 − 6 minimizes the difference.
(a) Let S be an unsorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(n) worst-case time.
(b) Let S be a sorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(1) worst-case time.
(c) Let S be an unsorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run in O(n log n)
worst-case time.
(d) Let S be a sorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run in O(n)
worst-case time.
package avdongre.adm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
/**
* For each of the following problems, give an algorithm that finds the desired
* numbers within the given amount of time. To keep your answers brief, feel
* free to use algorithms from the book as subroutines. For the example,
* S = {6, 13, 19, 3, 8}, 19 − 3 maximizes the difference, while 8 − 6 minimizes the
* difference.
*
* (a) Let S be an unsorted array of n integers. Give an algorithm that finds
* the pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(n)
* worst-case time.
*
* (b) Let S be a sorted array of n integers. Give an algorithm that finds the
* pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(1)
* worst-case time.
*
* (c) Let S be an unsorted array of n integers. Give an algorithm that finds
* the pair x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run
* in O(n log n) worst-case time.
*
* (d) Let S be a sorted array of n integers. Give an algorithm that finds the
* pair x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run in
* O(n) worst-case time.
*
* @author adongre
*
*/
public class MaxMinVariations {
private class Pair {
public int first;
public int second;
public Pair(int x, int y ) {
first = x;
second = y;
}
@Override
public String toString() {
return String.format(first + "," + second);
}
}
private int [] generateInputArray(int size) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 1; i < size; i++) {
list.add(new Integer(i));
}
Collections.shuffle(list);
int[] result = new int [ list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i).intValue();
}
return result;
}
public Pair getMaxPairFromUnsortedArray(int [] input) {
if ( input == null) {
return null;
}
int largest = Integer.MIN_VALUE;
int smallest = Integer.MAX_VALUE;
for ( int i = 0; i < input.length; i++) {
if (input[i] > largest) {
largest = input[i];
} else if (input[i] < smallest) {
smallest = input[i];
}
}
Pair p = new Pair(smallest, largest);
return p;
}
public Pair getMaxPairFromSortedArray(int [] input) {
if ( input == null) {
return null;
}
Arrays.sort(input);
Pair p = new Pair(input[0], input[input.length - 1]);
return p;
}
public Pair getMinPairFromUnsortedArray(int [] input) {
if ( input == null) {
return null;
}
if ( input.length < 2) {
return null;
}
Arrays.sort(input);
int smallest = 0;
int largest = 0;
int currentMinimum = Integer.MAX_VALUE;
for ( int i = 1; i < input.length; i++) {
if ( currentMinimum > (input[i] - input[i-1])) {
currentMinimum = input[i] - input[i-1];
smallest = input[i -1];
largest = input[i];
}
}
Pair p = new Pair(smallest, largest);
return p;
}
public Pair getMinPairFromSortedArray(int [] input) {
if ( input == null) {
return null;
}
if ( input.length < 2) {
return null;
}
Arrays.sort(input);
int smallest = 0;
int largest = 0;
//Pair p = new Pair(input[0], input[1]);
int currentMinimum = Integer.MAX_VALUE;
for ( int i = 1; i < input.length; i++) {
if ( currentMinimum > (input[i] - input[i-1])) {
currentMinimum = input[i] - input[i-1];
smallest = input[i -1];
largest = input[i];
}
}
Pair p = new Pair(smallest, largest);
return p;
}
public static void main(String[] args) {
MaxMinVariations mm = new MaxMinVariations();
{
int [] inputArray = mm.generateInputArray(10);
System.out.println(Arrays.toString(inputArray));
System.out.println(mm.getMaxPairFromUnsortedArray(inputArray));
}
{
int [] inputArray = mm.generateInputArray(10);
System.out.println(Arrays.toString(inputArray));
System.out.println(mm.getMaxPairFromSortedArray(inputArray));
}
{
int [] inputArray = mm.generateInputArray(10);
System.out.println(Arrays.toString(inputArray));
System.out.println(mm.getMinPairFromUnsortedArray(inputArray));
}
{
int [] inputArray = mm.generateInputArray(10);
System.out.println(Arrays.toString(inputArray));
System.out.println(mm.getMinPairFromSortedArray(inputArray));
}
{
int [] inputArray = new int[] {5,10,11,12};
System.out.println(Arrays.toString(inputArray));
System.out.println(mm.getMinPairFromSortedArray(inputArray));
}
}
}
Avi's Programming Blog 