Show problems as
Classic problem #653EasyHash TableTwo PointersTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

Two Sum IV - Input is a BST

Real-world version: Two Calibration Cards to a Target
Tracked in this browser only
Read Two Sum IV - Input is a BST on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A cold store files its calibration cards in a branching index. Every card carries one signed offset in tenths of a degree, and no two cards carry the same offset. Each card holds at most two cards below it, one on its low side and one on its high side, and the filing rule holds everywhere: every offset filed anywhere below a card on its low side is smaller than that card's offset, and every offset filed anywhere below it on its high side is larger.

The index reaches you as index, a band listing, one band of the index at a time from the top down and left to right within a band. Slot 0 holds the topmost card. Each card that appears in the listing takes the next two unclaimed slots for what hangs below it, the low side first and the high side second. A slot holding null means nothing hangs there, and such a slot claims no slots of its own. Trailing null slots are left off the end of the listing.

Return true when the index holds two different cards whose offsets add up to k, and false otherwise. One card cannot be counted twice, so an offset that is exactly half of k is no use on its own.

Examples

Example 1

Input
index = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], k = 20
Output
true

The card carrying 6 and the card carrying 14 are two different cards and their offsets come to 20.

Example 2

Input
index = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], k = 100
Output
false

The two largest offsets in the index are 13 and 14, which come to 27, so no pair of cards reaches 100.

Example 3

Input
index = [4], k = 8
Output
false

There is only one card. Its offset is half of 8, but a single card cannot be counted twice.

Example 4

Input
index = [0, -3, 3], k = 0
Output
true

The card carrying -3 and the card carrying 3 are different cards and their offsets cancel out.

Example 5

Input
index = [2, null, 5], k = 7
Output
true

The index has two cards, and 2 with 5 comes to 7.

Constraints

  • The number of cards is in the range [1, 10^4].
  • -10^4 <= card offset <= 10^4
  • All the offsets are different, and index obeys the filing rule.
  • -10^5 <= k <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_target(index: list[int | None], k: int) -> bool:
Java
public boolean findTarget(Integer[] index, int k)

More on the same topics