Quick Overview

Assign modules with given difficulty values to three non-empty servers so that the smallest value of |d1 - d2| + |d2 - d3|, over one module picked from each server, is as large as possible. Tests max-min reasoning over partitions, the role of the middle server, and handling of duplicates and large values.

Split Modules Across Three Servers to Maximize the Minimum Deployment Difficulty

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given an integer array `difficulty` of length `n`, where `difficulty[i]` is the difficulty of the `i`-th software module. Assign the modules to three servers, Server 1, Server 2 and Server 3, so that: 1. every server receives at least one module, and 2. every module is assigned to exactly one server. After the assignment, pick one module from each server and call their difficulties `d1` (from Server 1), `d2` (from Server 2) and `d3` (from Server 3). The deployment difficulty of that pick is `|d1 - d2| + |d2 - d3|`. The minimum deployment difficulty of an assignment is the smallest deployment difficulty over all possible picks. Find the assignment that makes this minimum as large as possible, and return that largest possible minimum. ### Function Signature ```python def max_min_deployment_difficulty(difficulty: list[int]) -> int: ``` ### Rules - The servers are labeled, and the labels matter only through the formula: the module picked from Server 2 is the middle term, compared with both of the others. - Modules with equal difficulty are still different modules and may go to different servers. - The result is a single integer, so it is unique even when several assignments achieve it. ### Constraints The reported statement gives no input bounds; these are added so the problem is fully specified. - `3 <= n <= 10^5` - `1 <= difficulty[i] <= 10^9` - The answer can approach `2 * 10^9`, which exceeds `2^31 - 1`; use 64-bit integers in typed languages. ### Examples **Example 1** ```text Input: difficulty = [1, 5, 9] Output: 12 ``` Each server gets exactly one module. Putting `1` on Server 2, `5` on Server 1 and `9` on Server 3 gives `|5 - 1| + |1 - 9| = 12`. Putting `9` on Server 2 also gives `12`, while putting `5` there gives only `8`. **Example 2** ```text Input: difficulty = [100, 1, 3, 2] Output: 196 ``` Server 1 = `{2, 3}`, Server 2 = `{100}`, Server 3 = `{1}`. The cheapest pick takes `d1 = 3`, so the minimum is `|3 - 100| + |100 - 1| = 196`. **Example 3** ```text Input: difficulty = [3, 7, 1, 3] Output: 10 ``` Server 1 = `{3, 3}` (the two modules of difficulty `3`), Server 2 = `{7}`, Server 3 = `{1}`. Every pick gives `|3 - 7| + |7 - 1| = 10`.

Overview: Assign modules with given difficulty values to three non-empty servers so that the smallest value of |d1 - d2| + |d2 - d3|, over one module picked from each server, is as large as possible. Tests max-min reasoning over partitions, the role of the middle server, and handling of duplicates and large values.

You are given an integer array `difficulty` of length `n`, where `difficulty[i]` is the difficulty of the `i`-th software module. Assign the modules to three servers, Server 1, Server 2 and Server 3, so that: 1. every server receives at least one module, and 2. every module is assigned to exactly one server. After the assignment, pick one module from each server and call their difficulties `d1` (from Server 1), `d2` (from Server 2) and `d3` (from Server 3). The deployment difficulty of that pick is `|d1 - d2| + |d2 - d3|`. The minimum deployment difficulty of an assignment is the smallest deployment difficulty over all possible picks. Find the assignment that makes this minimum as large as possible, and return that largest possible minimum. Notes: - The servers are labeled, and the labels matter only through the formula: the module picked from Server 2 is the middle term, compared with both of the others. - Modules with equal difficulty are still different modules and may go to different servers. - The result is a single integer, so it is unique even when several assignments achieve it. ### Constraints - `3 <= n <= 10^5` - `1 <= difficulty[i] <= 10^9` - The answer can approach `2 * 10^9`; return it as a 64-bit integer in typed languages (`long` in Java, `long long` in C++). ### Example 1 ```text Input: difficulty = [1, 5, 9] Output: 12 ``` Each server gets exactly one module. Putting `1` on Server 2, `5` on Server 1 and `9` on Server 3 gives `|5 - 1| + |1 - 9| = 12`. Putting `9` on Server 2 also gives `12`, while putting `5` there gives only `8`. ### Example 2 ```text Input: difficulty = [100, 1, 3, 2] Output: 196 ``` Server 1 = `{2, 3}`, Server 2 = `{100}`, Server 3 = `{1}`. The cheapest pick takes `d1 = 3`, so the minimum is `|3 - 100| + |100 - 1| = 196`.

Constraints

  • 3 <= n <= 10^5
  • 1 <= difficulty[i] <= 10^9
  • The answer can approach 2 * 10^9; return it as a 64-bit integer in typed languages (long in Java, long long in C++).

Examples

Input: ([1, 5, 9],)

Expected Output: 12

Explanation: Example 1: minimum n = 3, one module per server; 1 or 9 on Server 2 gives 12, 5 there gives only 8.

Input: ([100, 1, 3, 2],)

Expected Output: 196

Explanation: Example 2: high outlier 100 alone on Server 2, 1 alone on Server 3, {2, 3} on Server 1: 97 + 99.

Hints

  1. For a fixed assignment, the cheapest pick first chooses a Server 2 module; after that, Server 1 and Server 3 each contribute the module closest in difficulty to it, independently of each other.
  2. Only the relative order of the difficulties decides which modules are closest, so look at the values in sorted order and ask where the smallest and largest values should go.
  3. Equal difficulties may be split across servers, and every server must stay non-empty; check both facts against any assignment you have in mind.

Loading coding console...

Show the approach

Approach

Sort the difficulties into a[0] <= a[1] <= ... <= a[n-1]. For a fixed assignment, the cheapest pick chooses some d2 on Server 2 and then, independently, the Server 1 and Server 3 modules closest to it, so the minimum equals the smallest value of dist(d2, Server 1) + dist(d2, Server 3) over d2 on Server 2.

Candidates. (A) For 0 <= i <= n-3, put a[0..i] on Server 2, a[i+1..n-2] on Server 1 and a[n-1] alone on Server 3. Every Server 2 value is <= a[i] and every other value is >= a[i+1], so the cheapest pick is d2 = a[i], d1 = a[i+1], d3 = a[n-1], worth A(i) = (a[n-1] - a[i]) + (a[i+1] - a[i]). (B) The mirror image: for 2 <= i <= n-1, put a[i..n-1] on Server 2, a[1..i-1] on Server 1 and a[0] alone on Server 3, worth B(i) = (a[i] - a[0]) + (a[i] - a[i-1]). The answer is the largest candidate, found by one linear scan after sorting.

Why no assignment beats the best candidate. Servers 1 and 3 play symmetric roles, and negating every value swaps family A with family B, so it suffices to bound an arbitrary assignment in three cases. (1) If a[0] and a[n-1] are both on Server 2, fix any d1 and d3; the picks d2 = a[0] and d2 = a[n-1] cost 2(a[n-1] - a[0]) in total, so the minimum is at most a[n-1] - a[0] <= A(0). (2) Otherwise, up to the symmetries, a[n-1] is on Server 3; let i be the largest sorted index on Server 2 (so i <= n-2). If some index above i is on Server 1, d2 = a[i] can be paired with a[i+1] on one side and a value <= a[n-1] on the other, costing at most A(i) with i <= n-3. (3) If Server 1 lies entirely below i, let k be its largest index and m the smallest Server 2 index above k. When m = k+1, the pick (a[k], a[m], a[n-1]) costs a[n-1] - a[k] <= A(k). When m > k+1, index m-1 is on Server 3, so the pick (a[k], a[m], a[m-1]) costs at most (a[m] - a[0]) + (a[m] - a[m-1]) = B(m). Every assignment is therefore bounded by some candidate, and every candidate is achievable.

Edge cases: n = 3 leaves one candidate per family (one module per server); an all-equal input gives 0; equal values may be split across servers, which sorted indices handle without special casing. Each term is at most 10^9 - 1, so the answer stays below 2 * 10^9; Java and C++ accumulate it in 64-bit integers as the constraints direct.

Time complexity:
O(n log n)
Space complexity:
O(n)