Problem 268490 · hard · Phase 02 Linear Data Structures

Towers That Are Hidden Up Close

linked list · monotonic deque · sliding window · splicing

Towers stand in a row, stored as a singly linked list of heights from front to back. A viewer standing at a tower can only see k towers ahead. A tower is hidden if at least one of the next k towers after it (in the original list) is strictly taller. Remove every hidden tower and return the head of the remaining chain, keeping the survivors in their original order. All decisions use the original list, not the list after removals. Re-link the existing nodes; do not create new ones.

Examples

Input:  heights = 3 -> 1 -> 4 -> 1 -> 5 -> 9 -> 2 -> 6, k = 1
Output: 3 -> 4 -> 9 -> 6

Input:  heights = 3 -> 1 -> 4 -> 1 -> 5 -> 9 -> 2 -> 6, k = 2
Output: 9 -> 6
Explanation: 3 is hidden by 4 (two steps ahead); 9 survives because 2 and 6 are shorter.

Input:  heights = 5 -> 5 -> 5, k = 2
Output: 5 -> 5 -> 5

Constraints

  • 0 <= number of nodes <= 3 * 10**4
  • 1 <= k <= 3 * 10**4
  • 0 <= height <= 10**9
  • Target: O(n) time. Checking the next k towers separately for every tower is too slow for the large tests.

Goals

  • Decide a node's fate only after its whole look-ahead window has passed
  • Keep undecided nodes in a deque whose values never increase
  • Attach surviving nodes in their original order as soon as they are safe
Starting Python…