Compute waits and find distance-k node pairs

Part 1 — Array next-higher wait: Given an integer array A where A[i] is the measurement for day i (0-indexed), return an array W of the same length such that W[i] is the smallest positive number d where i + d < n and A[i + d] > A[i]. If no such day exists, set W[i] = 0. Aim for an O(n) time solution and justify its correctness and space usage.

Part 2 — Binary tree distance-k pairs: Given a binary tree with unique node values and an integer k ≥ 0, define the distance between two nodes u and v as follows: if one is an ancestor of the other, the distance is the number of intermediate nodes on the path between them; otherwise, it is the sum of their distances to their lowest common ancestor. Return the set of all unordered pairs (u, v), u ≠ v, whose distance equals k. Design an algorithm faster than O(n^ 2), describe the data structures you would use, analyze time and space complexity, and discuss edge cases such as k = 0 or an empty tree.

Next Higher Waits

For each index, return the distance to the next later value that is strictly higher, or 0 if none exists.

Examples

Example 1

Input: ([73,74,75,71,69,72,76,73],)
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Explanation: Daily-temperatures style.

Example 2

Input: ([3,2,1],)
Output: [0, 0, 0]

Explanation: No higher future value.

Hints

1. Choose a representation that makes the core operation simple.
2. Handle empty and boundary inputs before the main algorithm.

Binary Tree Node Pairs at Distance K

Given unique level-order tree values and k, return sorted unordered value pairs whose standard edge distance is exactly k.

Examples

Example 1

Input: ([1,2,3,4,5,6,7], 2)
Output: [[1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [4, 5], [6, 7]]

Explanation: Pairs two edges apart.

Example 2

Input: ([1,2,3], 1)
Output: [[1, 2], [1, 3]]

Explanation: Adjacent pairs.

Hints

1. Choose a representation that makes the core operation simple.
2. Handle empty and boundary inputs before the main algorithm.