algoadvance

Leetcode 910. Smallest Range II

Problem Statement

You are given an integer array nums and an integer k. For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k. The score of nums is the difference between the maximum and minimum elements in nums. Return the minimum score of nums after changing the values at each index.

Example

  1. Input: nums = [1, 3, 6], k = 3 Output: 3 Explanation: Change nums to be [4, 6, 3]. The score is 6 - 3 = 3.

Clarifying Questions

  1. What values will the elements of nums take?
    • The elements of nums are integers and can be positive, negative or zero.
  2. What is the size range of nums?
    • The length of nums will be between 1 and 10^4.
  3. Would there be a case when k is zero?
    • Yes, k can be zero in which case we won’t change any elements, but we need to handle that explicitly.

Strategy

To minimize the difference between the max and min values of the transformed array:

  1. Sort the array to make it easier to determine the possible maximum and minimum values after transformation.
  2. After sorting, consider the initial range as nums[n-1] - nums[0] (max - min of the sorted array).
  3. Then explore the minimum possible range after introducing k:
    • If we add k to the minimum element or subtract k from it,
    • If we subtract k from the maximum element or add k to it,
    • This gives different ranges which we must check to find the minimum difference.

Steps:

  1. Sort the array.
  2. Initialize the result with the initial range nums[n-1] - nums[0].
  3. Iterate through each index and calculate the new possible max and min by applying +k or -k to the boundaries:
    • For each index i from 0 to n-2:
      • Calculate potential new max as the maximum of nums[i] + k and nums[n-1] - k.
      • Calculate potential new min as the minimum of nums[0] + k and nums[i+1] - k.
      • Update the result with the minimum range found.

Code

public class SmallestRangeII {
    public int smallestRangeII(int[] nums, int k) {
        // Sort the array
        Arrays.sort(nums);
        
        int n = nums.length;
        // Initial max and min range as it is before any modifications
        int result = nums[n - 1] - nums[0];
        
        // Iterate through the array and calculate the potential new minimum and maximum ranges
        for (int i = 0; i < n - 1; i++) {
            int maxVal = Math.max(nums[i] + k, nums[n - 1] - k);
            int minVal = Math.min(nums[0] + k, nums[i + 1] - k);
            // Update the result with the minimum range
            result = Math.min(result, maxVal - minVal);
        }
        
        return result;
    }
}

Time Complexity

This strategy ensures we explore all possible transformations effectively to find the minimum possible score.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI