> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Furthest Building You Can Reach

> Tested Python solution for LeetCode 1642 with 36 pytest cases. Generate a practice environment with lcpy.

LeetCode 1642, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Greedy](/catalog/topics/greedy), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/furthest-building-you-can-reach/description/).

Generate this problem as a practice environment: tested reference solution, 36 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1642   # by problem number
lcpy gen -s furthest_building_you_can_reach   # by problem name
```

## Problem

You are given an integer array `heights` representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building `i` to building `i+1` (0-indexed),

* If the current building's height is **greater than or equal** to the next building's height, you do **not** need a ladder or bricks.
* If the current building's height is **less than** the next building's height, you can either use **one ladder** or `(h[i+1] - h[i])` **bricks**.

Return *the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.*

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/10/27/q4.gif)

```
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
```

```
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
```

```
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
```

### Constraints

* 1 \<= heights.length \<= 10^5
* 1 \<= heights\[i] \<= 10^6
* 0 \<= bricks \<= 10^9
* 0 \<= ladders \<= heights.length

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/furthest_building_you_can_reach/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/furthest_building_you_can_reach/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log k) where k = ladders
    # Space: O(k)
    def furthest_building(self, heights: list[int], bricks: int, ladders: int) -> int:
        climbs: list[int] = []
        for i in range(len(heights) - 1):
            climb = heights[i + 1] - heights[i]
            if climb <= 0:
                continue
            heapq.heappush(climbs, climb)
            if len(climbs) > ladders:
                bricks -= heapq.heappop(climbs)
            if bricks < 0:
                return i
        return len(heights) - 1
```

## Complexity

| Time | Space |
| - | - |
| O(n log k) where k = ladders | O(k) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.