Citadel OA | Global Maximum | Citadel Online Assessment Question

Consider an array of distinct positive integers where elements are sorted in ascending order. We want to find all the subsequences of array consisting of exactly m elements. For example, given array a=[1,2,3,4], the subsequences consisting m=3 elements are [1,2,3], [1,2,4], [1,3,4], and [2,3,4]. Once we have all of the m-element subsequences, we find the value of globalMaximum using the following pseudocode:

1globalMaximum = 0
2
3for each subsequence, s, consisting of m elements {
4    currentMinimum = 10^18
5
6    for each (x,y) pair of elements in subsequence s {
7        absoluteDifference = abs(x - y)
8
9        if absoluteDifference < currentMinimum {
10            currentMinimum = absoluteDifference
11        }
12    }
13
14    if currentMinimum > globalMaximum {
15        globalMaximum = currentMinimum
16    }
17}

Relevant Citadel OA Problems:

• Triplets
• Ways to Sum
• Consecutive Sum
• Disk Space Analysis
• Do They Belong?
• Global Maximum
• Initial Public Offering
• Inversions
• Portfolio Balances
• Prime Factor Visitation
• Profit Targets
• Sprint Training
• Throttling Gateway
• Birthday Card Collection

Input

• arr: a sorted array of distinct integers
• m: an integer, the subsequences' length

Output

the global maximum calculated per the pseudocode

Examples

Example 1:

Input:

1arr = [2,3,5,9]
2m = 3

Output: 3

Explanation:

First find all subsequences of length m.

1[2,3,5]
2[2,3,9]
3[2,5,9]
4[3,5,9]

The final answer is globalMaximum=3 for subsequence [2,5,9].

Constraints

• 2<=n<=10^5
• 1<=a[i]<=10^9
• The array consists of distinct positive integers sorted in ascending order.
• 2<=m<=n

Try it yourself

Solution