Towers Above Both Neighbourhoods

Hard

A row of towers has heights given by the array heights. You are also given a positive integer k. The tower at index i is **prominent** if: - at least k towers to its left are strictly lower (indices j < i with heights[j] < heights[i]); - at least k towers to its right are strictly lower (indices j > i with heights[j] < heights[i]). Return the number of prominent towers.

Example 1

heights=[1, 4, 2, 5, 3, 1], k=2 → 1

The tower of height 5 (index 3) has 1, 4 and 2 below it on the left and 3 and 1 on the right. The tower of height 4 (index 1) fails: only one lower tower stands to its left.

Example 2

heights=[2, 2, 2, 2], k=1 → 0

Equal towers do not count as lower, so none qualify.

Example 3

heights=[1, 3, 1, 3, 1], k=1 → 2

Constraints

1 ≤ len(heights) ≤ 10⁵
1 ≤ heights[i] ≤ len(heights)
1 ≤ k ≤ len(heights)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Binary Search Divide and Conquer Ordered Set Merge Sort

Similar problems

Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard Triples Both Rankings Agree On Hard

Input

heights=[1, 4, 2, 5, 3, 1], k=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.