LeetCode 3903: two solutions - O(n²) vs O(n) Time complexity

Previously, I wrote a post about the trade-offs between space and time complexity. Here is another example where you can see why the fastest algorithm may use more memory, and vice versa: if we want to use less memory, we may have to sacrifice speed.

The LeetCode 3903. Smallest Stable Index I problem.

LeetCode 3903 C++ solution — O(n) Time

class Solution {
public:
  int smallestStableIndex(vector<int>& nums, int k) {
    int n = nums.size();

    vector<int> suffixMin(n);
    suffixMin[n - 1] = nums[n - 1];

    for(int i = n - 2; i >= 0; i--)
      suffixMin[i] = min(nums[i], suffixMin[i + 1]);

    int prefixMax = nums[0];

    for(int i = 0; i < n; ++i)
    {
      prefixMax = max(prefixMax, nums[i]);

      if (prefixMax - suffixMin[i] <= k)
        return i;   
    }

    return -1;
  }
};

In this case we have Time complexity - O(n) and Space complexity is O(n). For this solution, I use the Prefix Maximum and Suffix Minimum patterns.

C++ solution with O(1) Extra Space

If we want to have O(1) for Space complexity, we can find the minimum suffix value from scratch for each i.

class Solution {
public:
  int smallestStableIndex(vector<int>& nums, int k) {
    int n = nums.size();
    int prefixMax = 0;

    for(int i = 0; i < n; i++)
    {
      prefixMax = max(prefixMax, nums[i]);

      int suffixMin = nums[i];

      for(int j = i + 1; j < n; j++)
        suffixMin = min(suffixMin, nums[j]);

      if(prefixMax - suffixMin <= k) return i;
    }

    return -1;
  }
};

But in this case we have Time complexity - O(n²) and Space complexity is O(1) - the brute-force approach uses a nested scan.

The main examples above use C++. Below are implementations of the O(n) solution in other programming languages.

LeetCode 3903 Java solution

class Solution {
  public int firstStableIndex(int[] nums, int k) {
    int n = nums.length;

    int[] suffixMin = new int[n];
    suffixMin[n - 1] = nums[n - 1];

    for(int i = n - 2; i >= 0; i--)
      suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);

    int prefixMax = nums[0];

    for(int i = 0; i < n; i++) {
      prefixMax = Math.max(prefixMax, nums[i]);

      if(prefixMax - suffixMin[i] <= k) return i;
    }

    return -1;
  }
}

LeetCode 3903 JavaScript solution

var firstStableIndex = function(nums, k) {
  const n = nums.length;

  const suffixMin = new Array(n);
  suffixMin[n - 1] = nums[n - 1];

  for(let i = n - 2; i >= 0; i--)
    suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);

  let prefixMax = nums[0];

  for(let i = 0; i < n; i++) {
    prefixMax = Math.max(prefixMax, nums[i]);

    if (prefixMax - suffixMin[i] <= k) return i;
  }

  return -1;
};

LeetCode 3903 TypeScript solution

function firstStableIndex(nums: number[], k: number): number {
  const n = nums.length;

  const suffixMin: number[] = new Array(n);
  suffixMin[n - 1] = nums[n - 1];

  for(let i = n - 2; i >= 0; i--)
    suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);

  let prefixMax = nums[0];

  for(let i = 0; i < n; i++) {
    prefixMax = Math.max(prefixMax, nums[i]);

    if (prefixMax - suffixMin[i] <= k) return i;
  }

  return -1;
};

LeetCode 3903 Python solution

class Solution:
  def firstStableIndex(self, nums: List[int], k: int) -> int:
    n = len(nums)

    suffix_min = [0] * n
    suffix_min[n - 1] = nums[n - 1]

    for i in range(n - 2, -1, -1):
      suffix_min[i] = min(nums[i], suffix_min[i + 1])

    prefix_max = nums[0]

    for i in range(n):
      prefix_max = max(prefix_max, nums[i])

      if prefix_max - suffix_min[i] <= k:
        return i

  return -1