Optimal Interval Excitement

Easy

0/40

0 upvote

Problem statement

You are given an array of integers B of size N. Your task is to find an optimal numeric interval [X, Y] that results in the maximum and minimum possible final "excitement levels".

The excitement level starts at 0 and is calculated by iterating through each number in the array B:

1) If a number is within the interval X, Y, the excitement level increases by 1. 2) If a number is outside the interval [X, Y], the excitement level decreases by 1.

You have complete freedom to choose the integers X and Y to define the interval. You need to return the maximum and minimum possible final excitement levels.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'N', the size of the array.

The second line contains 'N' space-separated integers, representing the elements of the array B.

Output Format:

Print a single line containing two space-separated integers: the maximum possible excitement level followed by the minimum possible excitement level.

Note:

The final excitement level only depends on c, the count of numbers from the array that fall within the chosen interval [X, Y].

The formula for the final excitement level is c - (N - c), which simplifies to 2*c - N.

To maximize excitement, you must choose an interval that maximizes c.

To minimize excitement, you must choose an interval that minimizes c.

Sample Input 1:

3
1 5 2

Sample Output 1:

3 -3

Explanation for Sample 1:

The array has N=3 elements. The excitement level is `2*c - 3`.
- To maximize excitement:We need to maximize `c` (the count of numbers inside the interval). We can choose an interval like `[1, 5]` which captures all 3 numbers (`c=3`). The excitement level is `2*3 - 3 = 3`.
- To minimize excitement:We need to minimize `c`. We can choose an interval like `[3, 4]` which captures 0 numbers (`c=0`). The excitement level is `2*0 - 3 = -3`.

Sample Input 2:

4
10 20 30 40

Sample Output 2:

4 -4

Explanation for Sample 2:

The array has N=4 elements. The excitement level is `2*c - 4`.
- To maximize excitement:Choose an interval that captures all 4 numbers (e.g., `[10, 40]`). Here `c=4`. The excitement level is `2*4 - 4 = 4`.
- To minimize excitement:Choose an interval that captures 0 numbers (e.g., `[1, 9]`). Here `c=0`. The excitement level is `2*0 - 4 = -4`.

Expected Time Complexity:

The expected time complexity is O(N) to read the input.        
The calculation itself is O(1).

Constraints:

1 <= N <= 10^5
-10^9 <= B[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Optimal Interval Excitement

Time Complexity

The expected time complexity is O(N) to read the input.
The calculation itself is O(1).

Space Complexity

(100% EXP penalty)

Optimal Interval Excitement

Console