Minimum Height Difference Between Distant Peaks
Updated
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) → intExamples
Example 1
heights = [1, 5, 3, 9, 7]gap = 2return = 2Valid 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 = 30Only the pair (0,3) satisfies |i - j| >= 3, giving |10 - 40| = 30.
Example 3
heights = [1, 2, 3]gap = 5return = -1No index pair is 5 apart in a length-3 array, so the answer is -1.
Constraints
1 <= heights.length <= 10^40 <= heights[i] <= 10^91 <= gap <= 10^4
More Roblox interview questions
- Design Search Autocomplete SystemPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Most Frequent Call Path From Function Trace LogsPHONE SCREEN · Seen Nov 2026
- Candy Crush Grid Matching and GravityPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Implement a Rate LimiterPHONE SCREEN · Seen Oct 2026
- Rate Limit by Multiple Request FieldsPHONE SCREEN · Seen Oct 2026
- Topological Sort with Secondary OrderingPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Time-Aware Search AutocompletePHONE SCREEN · Seen Oct 2026
- Centered Block Placement QueriesOA · Seen Oct 2026
- Most Frequent Call Stack Per ThreadPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Robot Navigation Around LasersOA · Seen Oct 2026
Similar questions at other companies
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions
- Count Perfect PairsAdyen · OAAdyen interview questions
- Profitable Project PairsAkuna Capital · OAAkuna Capital interview questions
- 3SumAT&T · OAAT&T interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- Find Minimum Possible SizeMathWorks · OAMathWorks interview questions
- Count Pair Sums in a RangeAdobe · OAAdobe interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
Roblox interview experiences
- Roblox New Grad Early OA Tasks: 10 Experiences (Part 7 of 7)
- Roblox New Grad Engineer Rounds: 13 Experiences (Part 6 of 7)
- Roblox New Grad HackerRank OA: 18 Experiences (Part 5 of 7)
- Roblox New Grad CodeSignal Finals: 23 Experiences (Part 4 of 7)
- Roblox New Grad Games and BQ: 25 Experiences (Part 3 of 7)
- Roblox New Grad Coding Rounds: 23 Experiences (Part 2 of 7)