MinMax Problem Implementation

Question

Problem Statement:

You will be given a list of integers, arr, and a single integer k. You must create an array of length k from elements of arr such that its unfairness is minimized. Call that array subarr.

Unfairness of an array is calculated as: max(subarr) - min(subarr)

Where:

• max denotes the largest integer in subarr
• min denotes the smallest integer in subarr

Complete the maxMin function in the editor below. It must return an integer that denotes the minimum possible value of unfairness.

Solution:

 static int maxMin(int k, int[] arr) {
    int arrLen = arr.length;
    Arrays.sort(arr);
    int[] subArr = Arrays.copyOfRange(arr, 0, k);
    int minUnfairness = subArr[k - 1] - subArr[0];

    for ( int j = 1; j < arrLen - k + 1; j++ ) {

        subArr = Arrays.copyOfRange(arr, j, j+k);

        int tempMinUnfairness = subArr[ k - 1 ] - subArr[0];

        if ( tempMinUnfairness < minUnfairness ) {
            minUnfairness = tempMinUnfairness;
        }
    }

    return  minUnfairness;
 }

  /**
   * Valid Test Case For Reference
   */
   private static void validTest() {
        int[] arr = { 10,100,300,200,1000,20,30 };
        int expected = 20;
        int result = maxMin(3, arr);
        assert (result == expected);
    }

The main function to review is maxMin().

Looking forward to your reviews on -

1. What other improvements can be done?
2. What other ways could be there to the problem, as the current approach is Greedy?

Thank you.

Answer 1

Hello and Welcome to Code Review! There are two main concerns I have with your solution:

---

Side Effects

Your program has side effects outside of its scope: Arrays.sort(arr) When you call this function you are sorting the array object whose reference you have been passed. This means you are sorting the array that exists outside of your method scope, thus transforming any array you have been passed.

Since Arrays.sort() causes side effects, I'd recommend using Arrays.copyOf() to make a local copy, then sort the local copy.

---

Over-copying

You use Arrays.copyOf() inside your for loop, meaning you are frequently copying and making new arrays. These memory operations are expensive, and unnecessary.

You copy a range, but check only the end points of the range. Would it not make more since to simply check the values that would otherwise become those endpoints? Essentially, while looping, maintain two indeces, the head and tail pointers(i and i+k-1), and check those values rather than creating a new copy.

A good way to view this approach: We are essentially maintaining a abstract sliding range of k elements, and starting at 0, we slide our range along the array, checking each endpoint for a minimum without the need to create concrete copies.

---

With the above I reduced your solution to the below

static int maxMin(int k, int[] arr) {
    int arrLen = arr.length;
    //1)Make Sorted Local Copy to prevent Side Effects
    int[] localArr = Arrays.copyOf(arr, arrLen);
    Arrays.sort(localArr);

    int minUnfairness = Integer.MAX_VALUE;
    //2)Loop while maintaining two pointers
    // NOTE: we use J instead to prevent side effects on the int k
    int i = 0;
    int j = k - 1;
    while(j < arrLen){
        int tempMinUnfairness = localArr[j] - localArr[i];
        if ( tempMinUnfairness < minUnfairness ) {
            minUnfairness = tempMinUnfairness;
        }
        i++;
        j++;
    }
    return  minUnfairness;
}