Educative

Solution - Edge Cases not handled and can be optimized

def find_minimum_deletions(nums):
  # subtracting the length of LIS from the length of the input array to get minimum number of deletions
  return len(nums) - find_LIS_length(nums)


def find_LIS_length(nums):
  n = len(nums)
  dp = [0 for _ in range(n)]
  dp[0] = 1

  maxLength = 1
  for i in range(1, n):
    dp[i] = 1
    for j in range(i):
      if nums[i] > nums[j] and dp[i] <= dp[j]:
        dp[i] = dp[j] + 1
        maxLength = max(maxLength, dp[i])

  return maxLength

The solution provided will fail for empty nums as well as the maxLength calculation inside inner for loop can be avoided for optimisation as dp[i] will always increase in the inner loop. So we can directly take it up at the end.

My approach -

def find_minimum_deletions(nums):
  lis = 0 #longest_increasing_subsequence
  n = len(nums)
  dp = [0 for _ in range(n)]

  for curr in range(n):
    dp[curr] = 1
    for prev in range(curr):
      if nums[curr] > nums[prev] and dp[curr] <= dp[prev]:
        dp[curr] = dp[prev] + 1
  
    lis = max(lis, dp[curr])

  return n - lis