FastPrep
Problem · Array

Maximum Shown Segments

Learn this problem
● MediumTiktokFULLTIMEOA
See Tiktok hiring insights

Problem statement

A student is given a sequence of TikTok video clips. The duration of the i-th clip is arr[i].

There are q questions. Question i specifies an inclusive duration range [l[i], r[i]]. For each question, split the entire sequence into the maximum possible number of non-empty contiguous segments such that every segment satisfies both rules:

  1. The number of clips whose durations lie inside [l[i], r[i]] is strictly greater than the number whose durations lie outside that range.
  2. Every clip belongs to exactly one segment, and the original order of the clips is preserved.

If no valid partition exists for a question, its answer is 0.

The function findMaximumShorts receives:

  • arr: the clip durations;
  • l: the lower bound for each question;
  • r: the upper bound for each question.

Return an integer array containing the answer to every question in order.

Function

findMaximumShorts(arr: int[], l: int[], r: int[]) → int[]

Examples

Example 1

arr = [6, 4, 5, 1, 7]l = [4, 1]r = [8, 5]return = [3, 1]

For [4, 8], one optimal partition is [6], [4], and [5, 1, 7]. Their inside-versus-outside counts are 1 > 0, 1 > 0, and 2 > 1, so the answer is 3.

For [1, 5], the whole array has three clips inside the range and two outside it. It is valid as one segment, and no partition into more valid segments exists, so the answer is 1.

Example 2

arr = [5, 6, 7, 8, 9]l = [1]r = [4]return = [0]

No clip duration lies inside [1, 4]. Therefore no segment can contain more inside-range clips than outside-range clips.

Example 3

arr = [7, 8, 2, 11, 9, 6, 5]l = [2, 5]r = [8, 8]return = [3, 1]

For [2, 8], five clips are inside the range and two are outside it, giving a maximum of 3 valid segments. For [5, 8], four clips are inside and three are outside, so the maximum is 1.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= l.length = r.length <= 10^5
  • 1 <= arr[i], l[i], r[i] <= 10^9
  • l[i] <= r[i]

More Tiktok problems

drafts saved locally
public int[] findMaximumShorts(int[] arr, int[] l, int[] r) {
  // Write your code here.
}
arr[6, 4, 5, 1, 7]
l[4, 1]
r[8, 5]
expected[3, 1]
checking account