341. Searching in an Array Where Adjacent Differ by at Most K

Given an array of n integers where every pair of adjacent elements differs by at most k in absolute value (the array itself need not be sorted), and a target value x, find the index of the first occurrence of x, or print -1 if it doesn't occur.

Input: The first line contains n. The second line contains n space-separated integers where adjacent elements differ by at most k. The next line contains k. The final line contains the target value x. Output: Print the 0-indexed position of the first occurrence of x, or -1 if x does not occur.

1 <= n <= 10^5, 1 <= k <= 10^4, |arr[i+1] - arr[i]| <= k for every i

This only works because the array ISN'T required to be sorted, just 'smoothly varying' - a completely different guarantee from standard binary search, which requires genuine sorted order.

In an array that ISN'T sorted but where neighboring values never differ by more than k, find a target value's first position - using the k-gap guarantee to skip ahead faster than a plain scan. Brute force: Scan the array left to right one position at a time, checking each value against the target - this always works correctly (O(n)), but doesn't exploit the special 'adjacent values differ by at most k' guarantee to go faster. Optimised: Because neighboring values can change by at most k, you can safely compute a MINIMUM number of steps needed to possibly reach the target from your current position (based on how far off in value you currently are), letting you skip multiple positions at once whenever you're still far from the target - in the best case this is much faster than a plain scan, though it still degrades to O(n) in the worst case (e.g. k=1).

Check each index from 0 to n-1 in order, comparing the element at that index to x, and return the first index where they match; if no index matches after scanning the entire array, return -1. This is correct for any array regardless of the bounded-difference property and doesn't exploit any structure in the input. Time: O(n) Space: O(1)

Make a single pass through the array, and for every value not already recorded in a hash map, store its index as the first occurrence of that value (skip storing again if the value is already present, so only the earliest index is kept). After building the map in one linear pass, answer the query for x with a single O(1) hash lookup, returning the stored index if present or -1 otherwise. This trades extra memory for a much faster query after the initial preprocessing. Time: O(n) preprocessing, O(1) per query Space: O(n)

Start at index i = 0. At each step, if arr[i] equals x, return i. Otherwise, since adjacent elements can differ by at most k, x cannot possibly appear within the next floor(|arr[i] - x| / k) positions (reaching from arr[i] to a value of x requires at least that many steps of size at most k), so safely jump i forward by max(1, |arr[i] - x| / k) instead of advancing one index at a time. Repeat until i reaches or exceeds n, returning -1 if x was never matched. This has the same O(n) worst-case bound as a plain scan (when k is small, e.g. k=1) but needs no extra memory and typically skips large portions of the array when k is large relative to the value gaps, making it faster in practice than both the brute scan and the hashing approach. Time: O(n) worst case, often sub-linear in practice Space: O(1)

1. Start at index 0, comparing the current value to the target. 2. If it matches, that's your answer (the first occurrence, since you're scanning left to right). 3. Otherwise, compute how big a 'safe' jump you can take forward: since adjacent values differ by at most k, the target can't possibly appear within (|current value - target| / k) positions ahead, so skip that many steps at once. 4. Repeat until you find the target or run past the end of the array.

Time: O(n) in the worst case (when k is small, like 1, forcing single-step movement), but often much faster in practice when k is large and the target is far from the starting value. Space: O(1) - just the current index and a few comparisons, no extra storage needed.

x not present anywhere in the array (print -1); k = 1 (the smallest allowed step size, forcing a near-linear scan); and n = 10^5 (largest, confirming the skip-ahead approach beats a naive scan when k is large).

Be upfront that this technique's worst-case complexity is still O(n), same as a plain linear scan - its real value is the AVERAGE-case speedup when k is large, not a guaranteed asymptotic improvement, and interviewers often probe whether you understand that distinction.