# Smallest Range I and II

## Introduction

This chapter discusses a problem and one of its variations on arrays. Both are very common interview questions, with the former having a simple solution, and the latter being slightly more complex. Both variants however, can be solved by starting from the same idea and using just a handful of lines of code.

## Problem statement

[example:smallest_range:exercice1] Write a function that - given an array of integers $$I$$ and an integer $$K \geq 0$$ - returns the smallest possible difference between the smallest and largest value in $$I$$ after you have added $$-K \leq p \leq K$$ to each of the elements.

[example:smallest_range:example1]
Given $$I = \{3,5,1,7,8\}$$ and $$K=4$$ the function returns $$0$$. You can add $$I$$ to the following values: $$\{1,-1,3,-3,-4\}$$. The modified array becomes: $$B=\{4,4,4,4,4\}$$.

[example:smallest_range:example2]
Given $$I = \{1,9,4\}$$ and $$K=2$$ the function returns $$4$$.

## Clarification Questions

Can you add $$p$$ multiple times to an element of $$I$$?

No, you can only add $$p$$ once to each element of $$I$$.

## Discussion

For this problem it isn’t valuable to discuss the brute-force solution[^46] as it is impractical to actually code it during an interview. Moreover, such a solution is conceptually very different and, time complexity-wise, very far from the one that allows us to solve problem most efficiently. Instead, we will go directly to examining a better approach to the solution.

The problem is asking us to minimize the difference between the largest value ($$M$$) and the smallest value ($$m$$) of $$I$$ after we have processed it by adding to each and every of its element a value in the range $$[-K,+K]$$. Let’s call $$B$$ this post-processed version of $$I$$. We know that if $$K$$ is large enough[^47] so that we can modify $$M$$ and $$m$$ to be the same value by subtracting from $$M$$ and adding to $$m$$ then we make all the elements of $$I$$ equal, thus reducing the difference between $$I$$’s smallest and the largest element to zero (see Figure 51.2). This is possible because $$M-m$$ is the largest difference in $$I$$ and if we can effectively close their gap to $$0$$ then we can do the same with any other difference between any pair of elements of $$I$$. On the other hand, if $$K$$ is not large enough[^48] , then all we know is that we can reduce the difference between $$m$$ and $$M$$ to $$d=(M-K)-(m+K)$$. Note that in this case $$d > 0$$ (see Figure 51.1). Moreover, similar to what we have discussed above, because the difference between any other pair of elements of $$I$$ is smaller than or equal to ($$M-m$$), we also know that their differences can be made at least equal to or smaller than $$d$$. Figure 1: $$m$$ and $$M$$ are the smallest and largest element of $$I$$, respectively. You can bring them closer together by adding $$K$$ to $$m$$ and subtracting $$K$$ to $$M$$. $$d$$ is the difference between these two new values. $$d$$ will always be larger than any other difference you can obtain in the same way. You can see that any other pair $$(I[i], I[j])$$ will have a smaller difference because they are closer together to begin with. Figure 2: $$m$$ and $$M$$ are the smallest and largest element of $$I$$, respectively. If we add $$K$$ to $$m$$ and subtract $$K$$ to $$M$$ then in this case $$(m+K)$$ will be larger than $$(M-K)$$. This means that we can add to $$m$$ and subtract to $$M$$ a number $$p \leq K$$ such that $$m+p = M-p$$. Because any other number in $$I$$ is larger than $$m$$ and smaller than $$M$$ we can do the same with them, so that we bring all the elements to the same value.

[]

Therefore in order to solve this problem we only have to look at $$M$$ and $$m$$ and calculate $$d=(M-K)-(m+K)$$. If $$d \leq 0$$ then it means that we can make all the elements of $$I$$ equal and the function should return $$0$$, otherwise we can safely return $$d$$ as an answer.

You can find an implementation of this idea in Listing [list:smallest_range:solution1] which has $$O(|I|)$$ time and $$O(1)$$ space complexity. The [^49] function returns a pair of iterators pointing to the minimum and maximum element of the input range, respectively.

Listing 1: Solution to the \textit{smallest range} problem.

int smallest_range_I(const vector<int>& I, const int K)
{
const auto& [m, M] = std::minmax_element(std::begin(I), std::end(I));
const int d        = (*M - K) - (*m + K);
return std::max(0, d);
}

## Common Variations

### Smallest range II

This variant is almost identical to the main problem in this chapter (see Exercise [example:smallest_range:exercice1]) except that this time we are only allowed to add either $$-K$$ or $$+K$$ (and not any number in the range $$[-K,K$$) to each element of the input array $$I$$. As we shall see, this complicates things somewhat but, nevertheless, the core solution strategy remains the same.

[example:smallest_range:variation1:exercice1] Write a function that - given an array of integers $$I$$ and an integer $$K$$ - returns the smallest possible difference between the smallest and largest value in $$I$$ after you have added either $$-K$$ or $$K$$ to each of the elements .

[example:smallest_range:variation1:example1]
Given $$I = \{3,5,1,7,8\}$$ and $$K=2$$ the function returns $$3$$. You can modify add to $$I$$ the followings values $$\{2,-2,2,-2,-2\}$$. The modified array finally becomes: $$I'=\{5,3,3,5,6\}$$.

[example:smallest_range:variation1:example2]
Given $$I = \{1,9,4\}$$ and $$K=3$$ the function returns $$3$$. Figure 3: This figure is a visual representation of the Example [example:smallest_range:variation1:example1] where the highlighted boxes represent the input values, the white boxes at the top of the picture represent the values we can get by adding $$K$$ to the corresponding element and the white boxes at the bottom of the picture shows the values we can get by subtracting $$K$$ to them.

## Discussion

Let’s start by noting that the solution to this problem is always smaller than or equal to the difference between the largest ($$M)$$ and smaller $$(m)$$ elements of $$I$$. This is the case because in the worst case scenario we can either add or subtract $$K$$ to all of the elements of $$I$$ and therefore preserve the relative difference between all the elements of $$I$$ (including $$M$$ and $$m$$). We have this case when $$(M-m) \leq K$$ because subtracting and adding $$K$$ to $$M$$ and $$m$$, respectively, would eventually lead to a larger or equal difference[^50].

When $$(M-m) > K$$ then what we can do is to choose one element at index $$j$$ as a pivot point and add $$K$$ to all the elements smaller than or equal to $$I_j$$ and subtract $$K$$ from all of the elements of $$I$$ greater than $$I_j$$. The new gap depends on the new smallest ($$m'$$) and largest elements ($$M'$$). Given $$p$$ is the smallest element larger than $$I_j$$ then $$M'$$ is the largest among $$I_j+K$$ and $$M-K$$ while $$m'$$ is the smallest among $$p - K$$ and $$m+K$$. Therefore for a given $$j$$ we calculate the maximum gap as $$d_j = M'-m'$$. The final answer is the smallest of these gaps calculated for each of index of $$I$$.

This approach relies on being able to quickly identify elements that are smaller or greater than a given value. If the array is sorted this can be achieved quite efficiently. In-fact if $$I$$ is sorted then - for a given $$j$$ - all the elements that are smaller than $$I_j$$ appear at indices smaller than $$j$$ and, similarly, all the elements that are larger appear at indices larger than $$j$$. Therefore, if $$I$$ is sorted then $$m'$$ is the smallest among $$I_{j+1}-K$$ and $$I_0 +K$$ and $$M'$$ is the largest among $$I_j+K$$ and $$I_{|I|-1}-K$$.

We can use these observation to derive the following algorithm:

1. sort the input array $$I$$,

2. for each $$j = 0 \ldots |I|-1$$ calculate $$d_j = \max{(I_j+K,I_{|I|-1}-K)} - \min{(I_{j+1}-K, I_0 +K)}$$,

3. return the smallest $$d_j$$.

An execution of this algorithm for the Example [example:smallest_range:variation1:example1] is shown in the Figure 51.11. The initial input is shown in Figure 51.3 where the smallest and greatest value are $$m=1$$ and $$M=8$$, respectively. The only way for their gap to become smaller is for $$M$$ to be decreased and $$m$$ to be increased by $$K$$. Figure 51.4 shows how $$I$$ would look if we add $$K$$ to all the elements smaller than or equal to $$j=0$$ and subtract $$K$$ from the others. The highlighted boxes show the new array values while the white boxes show the original values. Note that the gap between the new minimum ($$1$$, obtained by subtracting $$2$$ from the original element with value $$3$$) and the new maximum element ($$6$$, obtained by subtracting $$2$$ from $$8$$) is now $$6-3=3$$. Similarly Figure 51.5 shows the resulting array for $$j=3$$. The new array minimum and maximum values are now $$3$$ and $$6$$, respectively. When $$j=2$$ or $$j=3$$, as we can see in Figures [fig:smallest_range:bars4] and 51.9 the gap increases where $$j=1$$. Finally Figure 51.10 shows the case where all the new elements are obtained by adding $$K$$. This scenario leaves the relative distance between the elements unchanged with regard to the original values and therefore, not surprisingly, the gap between the smallest and largest element is $$7$$ (as in Figure 51.3).

Listing [list:smallest_range:solution2] shows an implementation of this idea. Note that in the code $$m'$$ is and $$M'$$ is .

Listing 2: Solution to the \textit{smallest range} problem using sorting.

int smallest_range_II(std::vector<int>& A, const int K)
{
std::sort(std::begin(A), std::end(A));
int ans = A.back() - A.front();
for (size_t i = 1; i < A.size(); i++)
{
const auto m_new = std::min(A.front() + K, A[i] - K);
const auto M_new = std::max(A[i - 1] + K, A.back() - K);
ans              = std::min(ans, M_new - m_new);
}
return ans;
} Figure 4: $$j=0$$ Figure 5: $$j=1$$ [fig:s3mallest_range:bars4] [fig:smallest_range:bars15] [fig:smallest_range:bars6]