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 in nums and add or subtract k from it. The task is to return the smallest possible difference between the maximum and minimum elements of the array nums after performing this operation any number of times for each element.

Clarifying Questions

  1. What are the constraints on the values in the array and on k?
    • The array nums will have at least one element, and k is a non-negative integer.
  2. Can the array contain negative values?
    • Yes, the elements in the array can be negative.
  3. Should the result account for situations where no operations are needed?
    • Yes, the result should be the smallest possible difference, whether or not any operations are performed.

Strategy

  1. Find the initial minimum (minNum) and maximum (maxNum) of the array.
  2. After applying the operations, the new possible values for any element x are in the range [x - k, x + k].
  3. The smallest possible maximum value (newMax) is maxNum - k and the largest possible minimum value (newMin) is minNum + k.
  4. Therefore, the smallest possible range will be newMax - newMin, but it should not be less than zero (as the range cannot be negative).

Code

```java public class SmallestRangeI { public int smallestRangeI(int[] nums, int k) { int minNum = Integer.MAX_VALUE; int maxNum = Integer.MIN_VALUE;

    for (int num : nums) {
        minNum = Math.min(minNum, num);
        maxNum = Math.max(maxNum, num);
    }

    // Calculate the new maximum and minimum values after adding/subtracting k
    int newMin = minNum + k;
    int newMax = maxNum - k;

    // The smallest possible range, ensuring it's not negative
    return Math.max(0, newMax - newMin);
}

public static void main(String[] args) {
    SmallestRangeI solution = new SmallestRangeI();
    int[] nums = {1, 3, 6};
    int k =

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