N-stable Array: Determine Whether an Array Is N-stable and Find the Minimum Modifications to Make It So

Question

## Problem

An array is called N-stable if no element differs from its neighbors by more than `N`. Given an array and a value `N`, determine if it is N-stable. If not, return the minimum number of elements you must change (to any value) to make it N-stable.

```python
def n_stable(
    arr: list[int],
    N: int
) -> tuple[bool, int]:  # (is_stable, min_changes)
    pass
```

**Example:**
```
arr = [1, 5, 6, 7, 20], N = 4
# |1-5|=4 OK, |5-6|=1 OK, |6-7|=1 OK, |7-20|=13 NOT OK
-> (False, 1)  # change arr[4] to anything within 4 of 7

arr = [1, 2, 3, 4], N = 2
-> (True, 0)
```

## Follow-ups

1. Is the greedy approach (change the rightmost violating element) always optimal? Prove or give a counterexample.
2. How does this problem change if you can only change an element to a value within a fixed range `[lo, hi]`?
3. What if the array is circular (last element is also a neighbor of the first)? How does that affect the violation detection?
4. Formulate this as a graph problem and describe a shortest-path approach to the minimum changes question.

N-stable Array: Determine Whether an Array Is N-stable and Find the Minimum Modifications to Make It So

Question Details

Full Details

Topics

More from Uber