FastPrepMinimum Non-Adjacent Selection Capability

Minimum Non-Adjacent Selection Capability

Microsoft logoMicrosoft● MediumFULLTIMEOA
Learn

Problem statement

You are given an array of positive integers values. Choose at least count positions so that no two chosen positions are adjacent.

The capability of a selection is the maximum value among its chosen positions. Return the minimum capability achievable by any valid selection.

Function

minimumSelectionCapability(values: int[], count: int) → int

Examples

Example 1

values = [2,3,5,9]count = 2return = 5

Choosing values 2 and 5 from positions 0 and 2 gives capability 5. No valid pair has a smaller maximum.

Example 2

values = [2,7,9,3,1]count = 2return = 2

Positions 0 and 4 are non-adjacent and hold values 2 and 1, so the minimum capability is 2.

Example 3

values = [10,1,8,2,7,3]count = 3return = 3

Choosing positions 1, 3, and 5 gives values 1, 2, and 3.

Constraints

  • 1 <= values.length <= 10^5.
  • 1 <= values[i] <= 10^9.
  • 1 <= count <= (values.length + 1) / 2.

More Microsoft problems

See Microsoft hiring insights
public int minimumSelectionCapability(int[] values, int count) {
    // Write your code here.
}
values[2,3,5,9]
count2
expected5
Checking account…