We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Difference Between Largest and Smallest Value in Three Moves

Number: 1616

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given an array of integers, you are allowed to perform at most three moves, where in each move you can change one element to any value. The goal is to minimize the difference between the largest and smallest values in the array after performing these moves.

Key Insights

  • Only three moves are allowed, so we can only adjust at most three of the extreme (smallest or largest) values.
  • Sorting the array provides an ordered structure making it easier to consider which extremes to change.
  • The problem reduces to picking a combination of moves (modifying some smallest and some largest numbers) such that the difference between the new extremes is minimized.
  • Consider all combinations: change 0 smallest and 3 largest, 1 smallest and 2 largest, 2 smallest and 1 largest, and 3 smallest and 0 largest.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) (or O(1) extra space if sorting in-place).

Solution

The solution starts by sorting the array. Once sorted, we evaluate the effect of changing different combinations of the smallest and largest elements. For each combination, if i moves are used to change the smallest values then (3 - i) moves are used to change the largest values. After these moves, the candidate difference is computed as the difference between the element at index i and the element at index n - (4 - i). The minimum of these candidate differences is the final answer.

Code Solutions

# Python solution with line-by-line comments

def minDifference(nums):
    # Sort the list to access the smallest and largest elements easily.
    nums.sort()
    n = len(nums)
    # If there are 4 or fewer elements, they can all be made equal in at most 3 moves.
    if n <= 4:
        return 0

    min_diff = float('inf')
    # i moves on the smallest values and (3-i) moves on the largest values.
    for i in range(4):
        # Calculate the difference between the new maximum and new minimum after moves.
        current_diff = nums[n - (4 - i)] - nums[i]
        min_diff = min(min_diff, current_diff)
    return min_diff

# Example usage:
print(minDifference([1,5,0,10,14]))  # Expected output: 1
← Back to All Questions