LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves Java Solution

Problem Description

• Problem: Minimum Difference Between Largest and Smallest Value in Three Moves

• Description: You need to remove up to 3 numbers from an integer array to minimize the difference between the largest and smallest values of the remaining numbers.

Approach

• Idea:

  • Consider all possible ways to remove 3 numbers.

  • If the list has 4 or fewer numbers, the difference can always be 0 since we can remove all numbers.

  • For lists with more than 4 numbers, removing the most extreme numbers (both smallest and largest) will result in the smallest difference.

  • To easily access the smallest and largest numbers, we sort the list.

  • The numbers we need to consider are the 3 smallest and the 3 largest.

  • After sorting the array, the possible scenarios for removal are:

    1. Removing the last 3 numbers: [1, 2, 3, 4, 5, 6, , , _] Difference = 6 - 1

    2. Removing the first 1 and last 2 numbers: [_, 2, 3, 4, 5, 6, 7, , ] Difference = 7 - 2

    3. Removing the first 2 and last 1 numbers: [_, , 3, 4, 5, 6, 7, 8, ] Difference = 8 - 3

    4. Removing the first 3 numbers: [_, , , 4, 5, 6, 7, 8, 9] Difference = 9 - 4

  • Find the minimum difference among these scenarios.

• Algorithm:

  1. Sort the array.

  2. Calculate the difference for the 4 scenarios:

     1. Difference between the 4th last and the 1st element.

     2. Difference between the 3rd last and the 2nd element.

     3. Difference between the 2nd last and the 3rd element.

     4. Difference between the last and the 4th element.

  3. Return the minimum difference.

Code

class Solution {
    public int minDifference(int[] nums) {
        int n = nums.length;
        if (n <= 4) return 0;

        Arrays.sort(nums);
        int minDiff = Integer.MAX_VALUE;

        for (int i = 0; i < 4; i++) {
            int diff = nums[n - 4 + i] - nums[i];
            minDiff = Math.min(minDiff, diff);
        }

        return minDiff;
    }
}

Conclusion

• Time Complexity:

  • Sorting the array takes O(n log n).

  • Calculating the differences for 4 scenarios takes O(1).

  • Thus, the overall time complexity is O(n log n).

• Space Complexity:

  • Since we are not using any extra space, the space complexity is O(1).