FastPrep
Problem · Array

Minimum Height Difference Between Distant Peaks

Learn this problem
● MediumRoblox logoRobloxFULLTIMEOA
See Roblox hiring insights

Problem statement

You are given an integer array heights representing the heights of mountain peaks along a ridge (in index order) and an integer gap.

Return the minimum value of |heights[i] - heights[j]| over all index pairs (i, j) with |i - j| >= gap.

If no such pair exists (i.e., gap exceeds the largest possible index distance heights.length - 1), return -1.

A brute-force scan over all valid pairs is O(n^2). A faster approach slides a pointer gap positions behind the current index and maintains a sorted multiset of the eligible earlier heights, querying the closest value to the current height in O(n log n) overall.

Function

minHeightDifference(heights: int[], gap: int) → int

Examples

Example 1

heights = [1, 5, 3, 9, 7]gap = 2return = 2
Valid pairs with |i - j| >= 2: (0,2)|1-3|=2, (0,3)|1-9|=8, (0,4)|1-7|=6, (1,3)|5-9|=4, (1,4)|5-7|=2, (2,4)|3-7|=4. The minimum is 2.

Example 2

heights = [10, 20, 30, 40]gap = 3return = 30
Only the pair (0,3) satisfies |i - j| >= 3, giving |10 - 40| = 30.

Example 3

heights = [1, 2, 3]gap = 5return = -1
No index pair is 5 apart in a length-3 array, so the answer is -1.

Constraints

  • 1 <= heights.length <= 10^4
  • 0 <= heights[i] <= 10^9
  • 1 <= gap <= 10^4

More Roblox problems

drafts saved locally
public int minHeightDifference(int[] heights, int gap) {
  // write your code here
}
heights[1, 5, 3, 9, 7]
gap2
expected2
checking account