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:

globalMaximum = 0

for each subsequence, s, consisting of m elements {
    currentMinimum = 10^18

    for each (x,y) pair of elements in subsequence s {
        absoluteDifference = abs(x - y)

        if absoluteDifference < currentMinimum {
            currentMinimum = absoluteDifference
        }
    }

    if currentMinimum > globalMaximum {
        globalMaximum = currentMinimum
    }
}

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:

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

Output: 3

Explanation:

First find all subsequences of length m.

[2,3,5]
[2,3,9]
[2,5,9]
[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