#908

Easy

LeetCode Problem Workspace

Smallest Range I

Find the smallest score of an array after applying an operation to each element within a given range.

Problem Statement

You are given an integer array nums and an integer k. In one operation, you can select an index i (0 <= i < nums.length) and change nums[i] by adding an integer x where x is within the range [-k, k]. This operation can only be performed once per index.

The task is to find the smallest score of nums after applying the operation. The score is defined as the difference between the maximum and minimum elements in the array.

Examples

Example 1

Input: nums = [1], k = 0

Output: 0

The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2

Input: nums = [0,10], k = 2

Output: 6

Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.

Example 3

Input: nums = [1,3,6], k = 3

Output: 0

Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

Constraints

1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104

Solution Approach

Operation Impact on Score

Since the goal is to minimize the difference between the maximum and minimum values in nums, it's essential to adjust the largest and smallest values using the available range. Applying the maximum possible change to the maximum element and the minimum possible change to the minimum element will reduce the overall range, minimizing the score.

Optimizing Range Reduction

For the most effective result, adjust the maximum element by subtracting k and the minimum element by adding k. This approach minimizes the potential difference between the max and min values, ensuring the smallest score possible. The rest of the elements should remain as close to their original values as possible, maximizing the effect of the boundary changes.

Edge Case Consideration

When the array has only one element or when k is zero, no operations are needed, and the score will always be zero. These edge cases should be handled explicitly to avoid unnecessary computations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) where n is the length of nums, as we only need to scan through the array once to determine the max and min values. The space complexity is O(1), as we do not use extra space beyond a few variables for tracking the min and max values during the iteration.

What Interviewers Usually Probe

Tests how well the candidate can leverage mathematical operations and array manipulation to minimize a range.
Checks if the candidate can quickly identify the importance of adjusting boundary elements for optimal results.
Evaluates the candidate's ability to handle edge cases like single-element arrays or when k is zero.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution by trying to adjust every element, when only the largest and smallest need to be changed.
Failing to handle edge cases, such as arrays with only one element or k being zero.
Misunderstanding the problem and adjusting elements outside the required range [-k, k].

Follow-up variants

Modifying the problem to allow multiple operations per element.
Adding constraints where k can change dynamically throughout the process.
Introducing additional conditions, like maintaining a specific average of the elements.

FAQ

What is the main challenge in the Smallest Range I problem?

The main challenge is minimizing the score of the array by adjusting only the boundary elements (max and min) using a range of changes.

How does GhostInterview help with solving the Smallest Range I problem?

GhostInterview guides you through the process of optimizing the array score with minimal operations and highlights common pitfalls to avoid.

What is the time complexity of the solution for Smallest Range I?

The time complexity is O(n), where n is the length of the array, since we only need to scan through the array once to find the max and min values.

How do I handle edge cases in Smallest Range I?

Edge cases like arrays with one element or when k is zero should be handled explicitly by returning a score of 0, as no operations are needed.

Can Smallest Range I be solved with a different approach?

While the main approach is efficient, other methods, such as sorting or using heap structures, could also be explored, though they would add unnecessary complexity.

terminal

Solution

Solution 1: Mathematics

According to the problem description, we can subtract $k$ from the maximum value in the array and add $k$ to the minimum value in the array, which can reduce the difference between the maximum and minimum values in the array.

1

2

3

4

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        mx, mi = max(nums), min(nums)
        return max(0, mx - mi - k * 2)

Continue Practicing

#910 smallest range ii #902 numbers at most n given digit set #914 x of a kind in a deck of cards