Smallest and Largest

Medium

Use the least number of comparisons to get the largest and smallest number in the given integer array. Return the largest number and the smallest number.

Assumptions

• The given array is not null and has length of at least 1

Examples

• {2, 1, 5, 4, 3}, the largest number is 5 and smallest number is 1. return [5, 1].

Solution: pair swaps

Turn array into n / 2 pairs, swap the smaller of each pair to the left side. Once done, we now have the smaller numbers on the left, larger numbers on the right.

Iterate through both sides for smallest and largest

public class Solution {
  public int[] largestAndSmallest(int[] array) {
    int n = array.length;

    for (int i = 0; i < n / 2; i++){
      if (array[i] < array[n - 1 - i]){
        swap(array, i , n - 1 - i);
      }
    }
    int largest = largest(array, 0, (n - 1)/ 2);
    int smallest = smallest(array, n / 2, n - 1);
    return new int[]{largest, smallest};
  }

  private int largest(int[] array, int left, int right){
    int largest = array[left];
    for(int i = left + 1; i <= right; i++){
      largest = Math.max(largest, array[i]);
    }
    return largest;
  }

  private int smallest(int[] array, int left, int right){
    int smallest = array[left];
    for (int i = left + 1; i <= right; i++){
      smallest = Math.min(smallest, array[i]);
    }
    return smallest;
  }

  private void swap(int[] array, int left, int right){
    int tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;
  }
}

TC: O(2N) = O(N)

SC: O(1)