Problem

You are given an integer array nums of length n and an integer k.

For each index i, define its instability score as max(nums[0..i]) - min(nums[i..n - 1]).

In other words: - max(nums[0..i]) is the largest value among the elements from index 0 to index i. - min(nums[i..n - 1]) is the smallest value among the elements from index i to index n - 1.

An index i is called stable if its instability score is less than or equal to k.

Return the smallest stable index. If no such index exists, return -1.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 109
0 <= k <= 109

Examples:

nums = [5, 0, 1, 4], k = 3 → 3. Instability scores are 5, 5, 4, 1; index 3 is the first ≤ 3.
nums = [3, 2, 1], k = 1 → -1. Every index scores 2, never ≤ 1.
nums = [0], k = 0 → 0. The only index scores 0, which is ≤ 0.

Walkthrough

Observations

The first thing I pick up on here is that you use the index you're at in both the lookup to the left and the right, that's easy to overlook.

The next note is that the question is asking for the smallest stable index. Which means if we're processing the list from left to right we can stop as soon as we find one.

Brute force

As always it can be useful to implement the obvious answer first. We can simply iterate through every element, calculating the max values to the left and the min to the right each time.

class Solution:
  def firstStableIndex(self, nums: list[int], k: int) -> int:
    for idx, value in enumerate(nums):
      # Calculate the left-max and right-min each time
      instability_score = max(nums[:idx + 1]) - min(nums[idx:])
      if instability_score <= k:
        return idx
    # If there are no stable we fall back and return -1
    return -1

Submission result

The main thing to note here is that the list slice for the left elements must be idx + 1 so it includes the value at nums[i].

Every iteration through the nums array we check every number, which means if there are n elements in the list we're doing n * n operations so the complexity of this is O(n^2).

Max-optimisation

Each time we iterate the nums array we calculate the max. However, the max can easily be computed taking the previous max and the new value. If that new value is bigger - that's the new max. This will stop us having to iterate over all the preceding values each time.

class Solution:
  def firstStableIndex(self, nums: list[int], k: int) -> int:
    # nums[i] >= 0 so we just choose a value less than 0.
    left_max = -1
    for idx, value in enumerate(nums):
      # Update our left_max using the new value.
      left_max = max(left_max, value)
      # Calculate the left-max and right-min each time
      instability_score = left_max - min(nums[idx:])
      if instability_score <= k:
        return idx
    # If there are no stable we fall back and return -1
    return -1

Submission result

I've updated the left_max using max(left_max, value) you could equally have written if value > max: left_max = value if that's more intuitive for you.

This cuts down on half of the comparisons we need to do within the loop to n / 2. However, the number of operations is still n * (n / 2) which is O(n^2). So, whilst we've improved the leading constant we've still got a complexity that scales with the square of the length of the array.

Counter

Can we then do something similar with min? We can't use exactly the same trick as with the max because this time the list will start full and we'll be taking items away each time. If the array is [1, 3, 1] then the min is 1, but when we remove the next 1 it's still 1. Whereas that isn't true with [1, 3, 2]. You need to know if that was the last minimum you've removed in order to update it.

To follow this logic we could then use a counter to help track how many of each value there is on the right side. When the counter for the minimum element equals 0 we update the minimum. We're still going to have to do a min over a list but it'll be the list of unique values which generally would be lower. The edge case of [1,2,3,4] would be the worst where each time we remove the min. Let's work this one through anyway:

from collections import Counter

class Solution:
  def firstStableIndex(self, nums: list[int], k: int) -> int:
    # nums[i] >= 0 so we just choose a value less than 0.
    left_max = -1
    # Track counts of all elements
    element_counts = Counter(nums)
    right_min = min(element_counts)
    for idx, value in enumerate(nums):
      # Update our left_max using the new value.
      left_max = max(left_max, value)
      # Calculate the left-max and right-min each time
      instability_score = left_max - right_min
      # We update the right_min after we've checked for the next loop
      # Decrease the count of the number we're removing
      element_counts[value] -= 1
      if element_counts[value] == 0:
        del(element_counts[value])
        # If that number was the minimum and we need to update
        # Guard against last iteration empty element_counts
        if (value == right_min) and element_counts:
          right_min = min(element_counts)
      if instability_score <= k:
        return idx
    # If there are no stable we fall back and return -1
    return -1

Submission result

This is still O(n^2) in the worst case - imagine [1,2,3,4] where every step removes the current min and we have to recompute it from the remaining unique values. The average case is much better though, as we only pay for the min recomputation when we actually drop the current minimum entirely.

Step back

Now if you have been having the same thoughts as I've been outlining here then there are two paths you can take from this point. The first is that you power on - you can clearly see a way forward and if only you ordered the list of minimums you'd not need to do that min and you can finally get it to O(n)... but wait sorting is O(n log n) so even that wouldn't work. etc. etc.

This code is already complex now, bolting on optimisations is only going to make it more so. You have to realise when it's best to abandon a solution and not submit to the sunk-cost fallacy.

Let's go all the way back to the beginning. Hopefully, by now you have a good understanding of what the problem is asking. Maybe, we can reframe the problem in a better light.

As we progress through the list the max value is strictly increasing - it has to be, it's the max. But the min value we see will also be strictly increasing. At the start it's the whole list so it's the global minimum, then as we lose values from the list we'll likely lose this and it'll go up.

Rather than operating on the actual list of numbers we can create copies of this list we'll adapt. We'll use more memory, but we'll get the runtime down. So, what do we want in these list. Obviously, the best place to start is the minimum and maximum values at each point in the list!

If we do one pass from left to right we just record the max up to that point so [1,4,3,6,2] becomes [1,4,4,6,6]. We can do the same thing going from right to left to calculate the minimum, our same list becomes: [1,2,2,2,2]. Now we can simply go over both from left to right calculating the instability score using the pre-computed values!

class Solution:
  def firstStableIndex(self, nums: list[int], k: int) -> int:
    # Calculate our max value at each point.
    maxes = [nums[0]]
    for value in nums[1:]:
      if value > maxes[-1]:
        maxes.append(value)
      else:
        maxes.append(maxes[-1])

    # Calculate our min value at each point
    # Done in reverse so list is back to front.
    mins = [nums[-1]]
    for value in nums[-2::-1]:
      if value < mins[-1]:
        mins.append(value)
      else:
        mins.append(mins[-1])

    # Walk the values to find a solution
    for idx in range(len(nums)):
      if (maxes[idx] - mins[-(idx+1)]) <= k:
        return idx

    # If there are no stable we fall back and return -1
    return -1

Submission result

This is much better, we're now firmly at O(n) complexity as we're just iterating over the loop 3 times. Noting that we need to keep two extra copies of the array in memory.

Optimal

We can go one step further here and remove one of those pre-computed lists. Since we do our final iteration left-to-right looking for our solution we can compute the max as we're going along just like we did originally. So we can apply our original optimisation to this solution too! Well done if you remember that straight away.

class Solution:
  def firstStableIndex(self, nums: list[int], k: int) -> int:
    # nums[i] >= 0 so we just choose a value less than 0.
    left_max = -1

    # Calculate our min value at each point
    # Done in reverse so list is back to front.
    mins = [nums[-1]]
    for value in nums[-2::-1]:
      if value < mins[-1]:
        mins.append(value)
      else:
        mins.append(mins[-1])

    # Walk the values to find a solution
    for idx, value in enumerate(nums):
      # Update our left_max using the new value.
      left_max = max(left_max, value)
      # Check for a stable number
      if (left_max - mins[-(idx+1)]) <= k:
        return idx

    # If there are no stable we fall back and return -1
    return -1

Submission result

So that's our best solution at O(n) using just two passes of the data, and 1 extra copy of it.

3903. Smallest Stable Index I

Problem

Walkthrough

Observations

Brute force

Max-optimisation

Counter

Step back

Optimal