1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Problem Description
You are given an array nums
which consists of integers. The main task is to find out how to minimize the difference between the largest and smallest numbers in the array, after you're allowed to perform at most three modifications. Each modification lets you select one number from the array and change it to any value you wish (this could be any integer, not necessarily one that was already in the array).
Essentially, you want to make the array elements closer to each other in value while having at most three opportunities to adjust any of the elements. The goal is to return the smallest possible difference (also known as range) between the maximum and minimum values after doing these changes.
Intuition
The intuition behind the solution is drawn from the understanding that the largest difference in values within the array is between the lowest and highest numbers. If the array has fewer than 5 elements, no modification is needed because you can at most delete all four elements to make them equal, resulting in a difference of 0.
For arrays with 5 or more elements, the strategy to minimize the range would be to either raise the value of the smallest numbers or lower the value of the largest numbers. Since we can make at most three moves, it leaves us with a few scenarios on which numbers to change:
- Change the three smallest numbers: This would make the smallest number to be the one that was initially the fourth smallest.
- Change the two smallest numbers and the largest number: This can potentially bring down the largest number and increase the smallest ones, possibly narrowing the range even further.
- Change the smallest number and the two largest numbers: Similar rationale as above but with a different balance between how much you adjust the lowest and highest numbers.
- Change the three largest numbers: The largest number become the one that was initially the fourth largest.
By sorting the array first, we can easily access the smallest and largest values. Trying out all four scenarios should give us the minimum possible difference since they encompass all possible ways we can use our three moves to minimize the range of the array.
The solution iterates through the sorted array and computes the difference for each scenario, always keeping track of the smallest difference found. Finally, the smallest difference computed signifies the least possible range achievable after three or fewer modifications.
Solution Approach
The implementation of the solution makes use of basic concepts like sorting and iterating through arrays in Python.
Firstly, the array is sorted to organize the integers in increasing order. Sorting allows easy access to the smallest and largest values, which are the targets for potential changes. The sort()
method is used for this purpose, which sorts the array in place.
After sorting, the algorithm checks the length of the array (stored in variable n
). If the array has fewer than 5 elements (n < 5
), it returns 0
immediately because, with three moves, we can create at least four equal values (which is the whole array if its length is less than 5), resulting in a minimum difference of zero.
If there are 5 or more elements, the algorithm considers four possible scenarios for amending the array using at most three moves:
- Change the three smallest numbers (
nums[3] - nums[0]
). - Change the two smallest numbers and the largest number (
nums[n - 1] - nums[2]
). - Change the smallest number and the two largest numbers (
nums[n - 2] - nums[1]
). - Change the three largest numbers (
nums[n - 3] - nums[0]
).
These scenarios are checked within a loop that runs four times (since range(4)
yields 0, 1, 2, 3
). Within the loop, the variable l
represents the index of the small end and n - 1 - r
, where r = 3 - l
, represents the index of the large end of the array.
The difference between the selected elements for each scenario is calculated and compared using the min()
function. The ans
variable keeps track of the minimum difference found at any point in the loop.
At the end of the loop, ans
holds the smallest possible difference between the largest and smallest values of nums
after at most three moves. It is then returned as the result of the function.
1class Solution:
2 def minDifference(self, nums: List[int]) -> int:
3 n = len(nums)
4 if n < 5:
5 return 0
6 nums.sort()
7 ans = inf
8 for l in range(4):
9 r = 3 - l
10 ans = min(ans, nums[n - 1 - r] - nums[l])
11 return ans
In the given Python code, inf
represents an infinitely large value. This initialization ensures that any difference calculated will be smaller than inf
, and thus ans
will be set properly after the first iteration of the loop.
Overall, the solution is straightforward but effective, combining sorting with simple arithmetic operations and a loop that leverages the problem constraints smartly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Suppose we have the following array of integers:
1nums = [1, 5, 10, 20, 30]
Firstly, this array is already sorted, but in practice, we would sort it to make it easier to find the smallest and largest numbers. Since we are allowed at most three modifications, and there are more than four elements in the array (5 in this case), we apply the following four scenarios to find the minimum range:
-
Change the three smallest numbers:
- After changing, the new smallest number would be
nums[3]
, which is20
. - The largest number would remain
nums[4]
, which is30
. - The difference between the largest and smallest is
30 - 20 = 10
.
- After changing, the new smallest number would be
-
Change the two smallest numbers and the largest number:
- After changes, the smallest number would be
nums[2]
, which is10
. - The largest number would now be
nums[3]
, which is20
. - The difference between the largest and smallest is
20 - 10 = 10
.
- After changes, the smallest number would be
-
Change the smallest number and the two largest numbers:
- The new smallest number would be
nums[1]
, which is5
. - The new largest number would be
nums[2]
, which is10
. - The difference is
10 - 5 = 5
.
- The new smallest number would be
-
Change the three largest numbers:
- The smallest number would stay
nums[0]
, which is1
. - The new largest number would be
nums[1]
, which is5
. - The difference is
5 - 1 = 4
.
- The smallest number would stay
We then find the smallest of all these differences, which in this case is 4
from the last scenario. This is our answer: by changing the three largest numbers in the array, we minimize the difference to just 4.
The actual Python function would work as follows:
1nums = [1, 5, 10, 20, 30]
2n = len(nums) # Here, n = 5
3if n < 5:
4 return 0
5else:
6 nums.sort() # The array is already sorted but this step is necessary.
7 ans = float('inf')
8 for l in range(4): # We iterate four times to check every scenario.
9 r = 3 - l
10 ans = min(ans, nums[n - 1 - r] - nums[l]) # This finds the smallest range
11 # The answer here would be 4 after the loop
12 return ans
This approach efficiently considers the possibilities using the allowed number of modifications to find the minimal difference between the maximum and minimum elements of the array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minDifference(self, nums: List[int]) -> int:
5 # Determine the length of the input list
6 num_len = len(nums)
7
8 # If the list has less than 5 elements, return 0 as per problem statement,
9 # because we can remove all elements to minimize difference to zero
10 if num_len < 5:
11 return 0
12
13 # Sort the list to easily find the smallest difference
14 nums.sort()
15
16 # Initialize minimum difference to infinity, as we are looking for the minimum
17 min_diff = float('inf')
18
19 # We can remove 3 elements either from the beginning, the end, or both.
20 # We loop through scenarios where we take from 0 to 3 elements from the start,
21 # and respectively 3 to 0 elements from the end to balance out the total removed elements count.
22 for left in range(4):
23 right = 3 - left
24 # Calculate the difference between the current left-most element we are considering
25 # and the current right-most element we are considering
26 current_diff = nums[num_len - 1 - right] - nums[left]
27 # Update the minimum difference if the current difference is smaller
28 min_diff = min(min_diff, current_diff)
29
30 # Return the smallest difference we found
31 return min_diff
32
1class Solution {
2 public int minDifference(int[] nums) {
3 // Get the length of the nums array
4 int length = nums.length;
5
6 // If there are less than 5 elements, return 0 since we can remove all but 4 elements
7 if (length < 5) {
8 return 0;
9 }
10
11 // Sort the array to make it easier to find the minimum difference
12 Arrays.sort(nums);
13
14 // Initialize the minimum difference to a very large value
15 long minDiff = Long.MAX_VALUE;
16
17 // Loop through the array and consider removing 0 to 3 elements from the beginning
18 // and the rest from the end to minimize the difference
19 for (int left = 0; left <= 3; ++left) {
20 int right = 3 - left;
21 // Calculate the difference between the selected elements
22 long diff = (long)nums[length - 1 - right] - nums[left];
23 // Update the minimum difference if the current one is smaller
24 minDiff = Math.min(minDiff, diff);
25 }
26
27 // Return the minimum difference as an integer
28 return (int) minDiff;
29 }
30}
31
1#include <vector>
2#include <algorithm> // Include algorithm header for std::sort and std::min
3
4class Solution {
5public:
6 // Function to find the minimum difference between the largest and smallest values
7 // after at most 3 elements are removed from the array.
8 int minDifference(std::vector<int>& nums) {
9 int numElements = nums.size(); // Store the number of elements in nums
10
11 // If there are fewer than 5 elements, return 0 since we can remove all but one element
12 if (numElements < 5) {
13 return 0;
14 }
15
16 // Sort the array in non-decreasing order
17 std::sort(nums.begin(), nums.end());
18
19 // Initialize the answer to a large number
20 long long answer = 1LL << 60;
21
22 // Try removing 0 to 3 elements from the start and from the end in such a way
23 // that the total number of elements removed is 3 and find the minimum difference
24 for (int leftRemoved = 0; leftRemoved <= 3; ++leftRemoved) {
25 int rightRemoved = 3 - leftRemoved; // Ensure total of 3 elements are removed from both ends
26 // Update the answer with the minimum of the current answer and the difference
27 // between the current largest and smallest values
28 answer = std::min(answer, static_cast<long long>(nums[numElements - 1 - rightRemoved] - nums[leftRemoved]));
29 }
30
31 // Return the final answer
32 return static_cast<int>(answer);
33 }
34};
35
1// Importing the 'sort' utility method from a library like Lodash could be helpful.
2// In TypeScript, arrays have a built-in sort method, eliminating the need for a separate import.
3
4// Function to find the minimum difference between the largest and smallest values
5// after at most 3 elements are removed from the array.
6function minDifference(nums: number[]): number {
7 // Store the number of elements in nums.
8 let numElements: number = nums.length;
9
10 // If there are fewer than 5 elements, return 0 since we can remove all but one element.
11 if (numElements < 5) {
12 return 0;
13 }
14
15 // Sort the array in non-decreasing order (ascending).
16 nums.sort((a, b) => a - b);
17
18 // Initialize the answer to a large number.
19 let answer: number = Number.MAX_SAFE_INTEGER;
20
21 // Try removing 0 to 3 elements from the start and from the end in such a way
22 // that the total number of elements removed is 3 and find the minimum difference.
23 for (let leftRemoved = 0; leftRemoved <= 3; ++leftRemoved) {
24 let rightRemoved: number = 3 - leftRemoved; // Ensure total of 3 elements are removed from both ends.
25
26 // Update the answer with the minimum of the current answer and the difference
27 // between the current largest and smallest values.
28 answer = Math.min(answer, nums[numElements - 1 - rightRemoved] - nums[leftRemoved]);
29 }
30
31 // Return the final answer.
32 return answer;
33}
34
35// Example usage:
36// const result = minDifference([1,5,0,10,14]);
37// console.log(result); // Output would be the minimum difference obtained.
38
Time and Space Complexity
Time Complexity
The time complexity of the algorithm is determined primarily by the sorting operation. The sort method in Python is implemented using Timsort, which has an average and worst-case complexity of O(n log n)
, where n
is the number of elements in the list.
The for loop iterates a constant 4 times, which does not depend on the size of the input, so it contributes an additional O(1)
to the time complexity.
Therefore, the total time complexity of the code is O(n log n)
due to the sort operation, which is the dominant factor.
Space Complexity
The space complexity is the amount of additional memory space required by the algorithm as the size of the input changes. In this case, the sorting operation can generally be done in-place with a space complexity of O(1)
.
However, Python's sorting algorithm may require O(n)
space in the worst case because it can be a hybrid of merge sort, which requires additional space for merging. Since nums
is sorted in-place, and no other data structures depend on the size of n
are used, the space complexity is O(1)
in the best case and O(n)
in the worst case.
Therefore, the overall space complexity of the code is O(n)
in the worst case due to the potential additional space needed for sorting.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.