algoadvance

Leetcode 910. Smallest Range II

Problem Statement

The problem is defined on LeetCode as follows:

You are given an integer array A and an integer K. For each integer in the array, you can choose to add K to it or subtract K from it.

Return the smallest possible difference between the maximum value and the minimum value of the array after performing up to one of these operations on each array element.

Example:

Input: A = [1, 3, 6], K = 3
Output: 3
Explanation: Choose (1+3), (3+3), (6-3). The resulting array is [4, 6, 3] and the difference between the max and min is 6-3 = 3.

Clarifying Questions

  1. Can the elements in the array have negative values?
    • Yes, the elements can be negative.
  2. Is the array always non-empty?
    • Yes, as per the problem statement, we can assume that the array is non-empty.
  3. What are the constraints for A and K?
    • The length of the array A will be between 1 and 10000.
    • Each element of the array A can be as large as 10^5 in absolute value.
    • K is a non-negative integer less than or equal to 10^4.

Strategy

  1. Sort the Array:
    • Sorting the array helps in evaluating the smallest range because the extremes will change in a predictable manner when K is added or subtracted.
  2. Initial Range Calculation:
    • Calculate the initial difference between the maximum and minimum values of the sorted array without any adjustments. This serves as the baseline.
  3. Evaluate Possible Ranges:
    • Iterate through the sorted array and calculate new potential ranges by considering the effect of adding/subtracting K to each element.
    • Specifically, consider the new extremes (low and high) formed by the middle elements and their potential shifted values.
  4. Determine the Minimum Range:
    • Keep track of the minimum difference between the possibly modified max and min values.

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int smallestRangeII(std::vector<int>& A, int K) {
    if (A.size() == 1) {
        return 0;   // If there's only one element, no range calculation is needed.
    }

    std::sort(A.begin(), A.end());
    int n = A.size();
    int initialRange = A[n - 1] - A[0];

    int result = initialRange;
    for (int i = 0; i < n - 1; ++i) {
        int high = std::max(A[n - 1] - K, A[i] + K);
        int low = std::min(A[0] + K, A[i + 1] - K);
        result = std::min(result, high - low);
    }

    return result;
}

int main() {
    std::vector<int> A = {1, 3, 6};
    int K = 3;
    std::cout << "Smallest Range II: " << smallestRangeII(A, K) << std::endl;
    return 0;
}

Time Complexity

Hence, the total time complexity is O(n log n), dominated by the sorting step.

This approach ensures that we attempt to minimize the difference effectively, considering all possible adjustments with given constraints.

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