Show problems as
Classic problem #975HardArrayDynamic ProgrammingStackSortingMonotonic StackOrdered Set

Odd Even Jump

Real-world version: Sound Launch Stations On A Relay Pipeline
Tracked in this browser only
Read Odd Even Jump on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pipeline carries pressure gauges at stations 0 through n - 1, and readings[i] is the gauge value at station i. A message can be relayed forward from station to station, always to a station with a larger index. The relays a message makes are numbered 1, 2, 3, and so on in the order they happen, and the numbering decides where each relay is allowed to land.

Suppose the message currently sits at station i.

  • On an odd-numbered relay, look at every station j > i whose reading is greater than or equal to readings[i]. Among those, the message must go to a station holding the smallest such reading. If two or more stations hold that smallest reading, it goes to the one with the smallest index.
  • On an even-numbered relay, look at every station j > i whose reading is less than or equal to readings[i]. Among those, the message must go to a station holding the largest such reading. If two or more stations hold that largest reading, it goes to the one with the smallest index.

If no station ahead of i qualifies for the relay that is due, the message can go no further and is stuck at station i.

Call station s a sound launch station when a message released at s reaches station n - 1 after some number of relays. Station n - 1 is sound because a message released there is already at the end.

Return how many of the n stations are sound launch stations.

Examples

Example 1

Input
readings = [7, 7, 3, 9, 7]
Output
4

From station 0 the first relay is odd: stations 1, 3 and 4 hold 7, 9 and 7, the smallest qualifying reading is 7, and station 1 is the earlier of the two stations holding it. The second relay is even and station 4 holds 7, so the message lands on the last station. Stations 1, 2 and 4 also finish at station 4. A message released at station 3 needs a reading of at least 9 ahead of it and station 4 holds 7, so it is stuck.

Example 2

Input
readings = [24, 6, 24, 40]
Output
2

A message released at station 2 relays to station 3, whose reading of 40 is the smallest one at least 24 ahead of it, and station 3 is the last station. Station 3 itself is sound. A message released at station 0 relays to station 2, then needs a reading of at most 24 ahead of station 2 and only 40 remains, so it is stuck; the message released at station 1 ends up stuck at station 2 in the same way.

Example 3

Input
readings = [83, 61, 40, 22]
Output
1

Every station ahead of any other holds a smaller reading, so the odd first relay never has a qualifying destination and a message stays where it is released. Only station 3, which is already the last station, is sound.

Constraints

  • 1 <= readings.length <= 2 * 10^4
  • 0 <= readings[i] <= 10^5 - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sound_launch_stations(readings: list[int]) -> int:
Java
public int soundLaunchStations(int[] readings)

More on the same topics