algoadvance

Leetcode 908. Smallest Range I

Problem Statement

You are given an integer array nums and an integer k. In one operation, you can choose any element from nums and either increase it or decrease it by k.

Your goal is to minimize the difference between the maximum and minimum values of the array after performing any number of operations.

Return the minimum difference between the maximum and minimum values of the array after performing the operations.

Example:

Clarifying Questions

  1. Q: Are all numbers in the array positive? A: The problem statement does not impose restrictions on the nature of the numbers, so they can be positive, negative, or zero.

  2. Q: Can k be zero? A: Yes, k can be zero, in which case no changes can be made to the array elements.

  3. Q: What is the size range of the array? A: The problem does not specify, but we can assume that it falls within typical limits for a coding interview, perhaps up to several thousand elements.

Strategy

Considering the operation allowed (increasing or decreasing each element by k), the key point is to understand how this affects the range of the array. By either increasing or decreasing each number by k, you can potentially reduce the difference between the maximum and minimum numbers.

  1. Find the Initial Range: Compute the maximum and minimum of the array, and calculate the initial range as max - min.
  2. Adjust the Range: To find the minimum difference, recognize that the smallest value can be increased by k and the largest value can be decreased by k, reshaping the array values into a range of [min + k, max - k].

The minimum difference will be affected by these bounded values: [ \text{new_range} = \max(0, \text{initial_max} - \text{initial_min} - 2 \times k) ]

The use of max(0, ...) ensures that we do not have a negative range since the minimum possible difference is zero (all elements being the same).

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int smallestRangeI(std::vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        
        int min_val = *std::min_element(nums.begin(), nums.end());
        int max_val = *std::max_element(nums.begin(), nums.end());
        
        int initial_range = max_val - min_val;
        
        // Calculate the new range after the allowed operations
        int adjusted_range = std::max(0, initial_range - 2 * k);
        
        return adjusted_range;
    }
};

Time Complexity

Overall, the time complexity is (O(n)), making this solution efficient for reasonably large inputs.

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