Coding interview Essentials

45. Smallest Range I and II

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

image [fig:s3mallest_range:bars4]

image [fig:smallest_range:bars15]

Figure 6: Execution of the algorithm presented in Section 51.5 for j=0 (Figure 51.4), j=1 (Figure 51.5), j=2 (Figure [fig:smallest_range:bars4]), j=5 (Figure [fig:smallest_range:bars4]) and j=5 (Figure 51.9). The highlighted boxes contains the values obtained from the original elements shown in the white boxes. [fig:smallest_range:bars6]