You are given a sequence of n TikTok videos, each represented by a unique rating in the array videoRatings, reflecting the order in which the videos are presented to the user.
A sequence of videos is considered coherent if:
videoRatings forms an increasing order.The TikTok algorithm aims to suggest a coherent sequence to the user by potentially removing some videos, effectively selecting a subsequence of the original sequence.
Given the array videoRatings of length n, determine the minimum number of videos that must be discarded so that the remaining sequence is coherent.
Note: A subsequence is a sequence derived from another sequence by deleting some or no elements, without changing the order of the remaining elements.
Example 1:
Input: videoRatings = [1, 10, 4, 5, 3]
Output: 1
Explanation:The given
videoRatingsis not coherent because removing any single video from the sequence does not result in an increasing order.However, if we remove the video at index 1, where
videoRatings = 10, the remaining sequence becomes[1, 4, 5, 3]. By removing the video withvideoRatings = 3, the sequence becomes[1, 4, 5], which is an increasing order. Thus[1, 4, 5, 3]is coherent and the minimal removal required is 1.Alternatively, if we remove the video at index 4, where
videoRatings = 3, the sequence becomes[1, 10, 4, 5], which is also coherent. Thus, the minimum number of videos that must be removed in this case is 1.
🍉
input:
output: