Is Maximum Gap Between Stations easy or hard?

It is rated Medium on FleetCode with a 53.2% acceptance rate. The problem is straightforward once you realize it only requires finding the maximum adjacent difference, but it can trick you if you overcomplicate it.

How to solve Maximum Gap Between Stations in O(n)?

If the station positions are already sorted, iterate through the array once, compute each adjacent difference, and update a running maximum. This gives O(n) time and O(1) space without any additional data structures.

Maximum Gap Between Stations Python/Java solution?

In Python, initialize max_gap = 0 and loop for i in range(1, len(stations)): max_gap = max(max_gap, stations[i] - stations[i-1]). In Java, use a for loop starting at index 1 and Math.max to update the result. Both run in O(n) time.

What is the best approach for Maximum Gap Between Stations?

The best approach is a greedy single pass that computes the difference between every pair of consecutive stations and keeps track of the maximum. This runs in O(n) time and O(1) space, which is optimal because you must examine each gap at least once.

Is Maximum Gap Between Stations asked at Google/Amazon/Meta?

This problem tests fundamental array traversal and greedy thinking, which are common in technical interviews at top companies like Google, Amazon, and Meta. While it may not appear verbatim, similar problems about finding maximum differences or gaps are frequently asked.

What data structure is used in Maximum Gap Between Stations?

No complex data structure is required. The optimal solution uses only a simple array (or list) and a few variables to track the current and maximum gap. This makes it an excellent exercise for basic iteration skills.

What is the time complexity of Maximum Gap Between Stations?

The optimal solution runs in O(n) time, where n is the number of stations. If the input is unsorted and you sort it first, the time complexity becomes O(n log n) due to the sorting step.

Description Hints 4 Solution Video 20:04

4026. Maximum Gap Between Stations

Medium52.4% acceptance

You are given two strings skill and station of lengths n and m, respectively.

skill[i] represents the skill of worker i, and station[j] represents the skill supported by station j.

You must assign every worker to a distinct station. Let j_i be the index of the station assigned to worker i. A valid assignment must satisfy:

station[j_i] == skill[i] for every 0 <= i < n.
The assigned station indices must be strictly increasing in worker order, meaning j₀ < j₁ < ... < j_{n - 1}.

The gap of an assignment is the maximum difference between the station indices assigned to two consecutive workers. In other words, it is max(j_i - j_{i - 1}) over all 1 <= i < n.

If there is only one worker, the gap is 0.

Return the maximum possible gap among all valid assignments. It is guaranteed that at least one valid assignment exists.

Example 1:

Input: skill = "aa", station = "aaaa"

Output: 3

Explanation:

The two workers must be assigned to two different 'a' stations.
Assigning them to stations [0, 3] gives a gap of 3.

Example 2:

Input: skill = "xyz", station = "xyzz"

Output: 2

Explanation:

Assign worker 0 to station j = 0, and worker 1 to station j = 1.
To maximize the gap, assign worker 2 to station j = 3.
This gives the assignment [0, 1, 3] with gaps [1, 2], so the gap is 2.

Example 3:

Input: skill = "cbc", station = "cbcdbc"

Output: 4

Explanation:

Assign worker 0 to station j = 0, and worker 1 to station j = 1.
To maximize the gap, assign worker 2 to station j = 5.
This gives the assignment [0, 1, 5] with gaps [1, 4], so the gap is 4.

Constraints:

skill.length == n
station.length == m
1 <= n <= m <= 10⁵
skill and station consist of lowercase English letters.
It is guaranteed that a valid assignment exists for every worker.

Topics

Hints open one at a time

Hint 1

For each adjacent pair of workers i - 1 and i, try to maximize the distance between their assigned stations while still allowing all earlier and later workers to be matched.

Hint 2

Compute the earliest possible station index for every worker by greedily matching skill from left to right.

Hint 3

Compute the latest possible station index for every worker by greedily matching skill from right to left.

Hint 4

For each 1 <= i < n, workers before i can use their earliest possible positions and workers from i onward can use their latest possible positions. The largest possible gap between workers i - 1 and i is latest[i] - earliest[i - 1].

20:04

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumGap(self, skill: str, station: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"aa"
"aaaa"

Input

"xyz"
"xyzz"

Input

"cbc"
"cbcdbc"

Your code is saved on this device.Solution