FastPrepFastPrep
Problem Brief

Minimum Retailers

OA
See Amazon online assessment and hiring insights

An online marketplace has onboarded n merchants, each operating within a designated geographical range. The operating zone of merchant i is defined by the interval spanning from zoneStart[i] to zoneEnd[i].

A set of k merchants is termed cohesive (inclusive) if there exists at least one merchant whose operational territory overlaps with (or touches) all the other (k-1) merchants’ operational zones.

The marketplace plans to relocate some merchants to new areas. Your goal is to determine the minimum number of merchants that need to be moved so that the remaining merchants form a cohesive subset.

Function Description

Complete the predefined function in the editor.

minimumRetailers has the following parameters:

  1. int zoneStart[n]: the left ends of the operating regions
  2. int zoneEnd[n]: the right ends of the operating regions

Returns

int: the smallest number of merchants that need to be relocated

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ zoneStart[i] ≤ zoneEnd[i] ≤ 10^9 (1 <= i < n)
  • All regions have regions with the same start and end points.

1Example 1

Input
zoneStart = [1, 3, 4, 6, 9], zoneEnd = [2, 8, 5, 7, 10]
Output
2
Explanation
Example 1 illustration

2Example 2

Input
zoneStart = [1, 2, 3, 4], zoneEnd = [2, 3, 5, 5]
Output
1
Explanation
Region 1 (1, 2) intersects only region 2. (move regions 3 and 4) Region 2 (2, 3) intersects regions 1 and 3. (move region 4) Region 3 (3, 5) intersects regions 2 and 4. (move region 1) Region 4 (4, 5) intersects region 3. (move regions 1 and 2) The minimum number of moves is 1, moving region 1 or 4

3Example 3

Input
zoneStart = [1, 2, 4], zoneEnd = [7, 5, 6]
Output
0
Explanation
Will update once find reliable resources. As always.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 10^5
  • 1 <= regionStart[i] <= regionEnd[i] <= 10^9 (1 <= i <= n)
  • There can be multiple regions with the same start and end points
  • Complete constraints was added on 05-14-2025. You can find relevant source image will be uploaded next time..
    • public int minimumRetailers(int[] zoneStart, int[] zoneEnd) {
  // write your code here
}
    Input

    zoneStart

    [1, 3, 4, 6, 9]

    zoneEnd

    [2, 8, 5, 7, 10]

    Output

    2

    Sign in to submit your solution.