1
\$\begingroup\$

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.

New contributor
Anit Shrestha Manandhar is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Great review. Its a good idea to make a local copy of the array but as the problem does not need any kind of index maintained, I think that would only increase processing time as well as memory constraints. So I would leave that there. I agree with the abuse of Arrays.copyOf() in for loop.The use of two pointers are great. It just skipped my mind and nice to see your implementation. I appreciate your effort. Thank you very much. \$\endgroup\$ – Anit Shrestha Manandhar Apr 15 at 18:00
  • \$\begingroup\$ Your provided solution passed all the test cases. Thanks again. \$\endgroup\$ – Anit Shrestha Manandhar Apr 15 at 18:08

Your Answer

Anit Shrestha Manandhar is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.