Possible Final Sensor Readings
A monitoring system stores distinct sensor readings in their recorded order.
The system may repeatedly remove readings from the beginning or end of the current sequence. Determine which original readings can become the only remaining reading.
Possible Final Sensor Readings
Implement the following method:
String possibleFinalReadings(List<Integer> readings)
readings contains the sensor readings in their original order.- The method returns a binary string with one character for every original position.
- The character at position
i is 1 when readings.get(i) can become the final reading.
- Otherwise, the character at position
i is 0.
Cleanup Operations
Beginning Cleanup
Select a non-empty group of consecutive readings beginning with the first current reading. Keep only the smallest reading in the selected group.
Ending Cleanup
Select a non-empty group of consecutive readings ending with the last current reading. Keep only the largest reading in the selected group.
Rules
- The operations may be performed zero or more times in any order.
- An operation may select the entire current sequence.
- After an operation, the remaining readings are joined while preserving their relative order.
- All sensor readings are distinct.
Constraints
1 ≤ readings.size() ≤ 200,0000 ≤ i < readings.size()1 ≤ readings.get(i) ≤ 1,000,000- No two values in
readings are equal.
Examples
Example 1
possibleFinalReadings( readings = List.of(7, 12, 3, 15, 5, 9) )
Output: "101101"
The readings 7, 3, 15, and 9 can each become the only remaining reading.
Example 2
possibleFinalReadings( readings = List.of(18, 14, 7, 3) )
Output: "1111"
Every reading can become the final reading.
Example 3
possibleFinalReadings( readings = List.of(2, 6, 11, 17, 23) )
Output: "10001"
Only the first and last readings can become the final reading.
Example 4
possibleFinalReadings( readings = List.of(99) )
Output: "1"
The single reading is already the final reading.