Searching & Sorting · 9 of 36

Searching in an array where adjacent differ by at most k

Climb a staircase where each step changes height by at most k, and skip the steps that cannot possibly be the height you want.

EasyJump search

Simple way: time O(n)
room O(1)
Clever way: time O(n)
room O(1)

The problem, simply

You get an array where any two neighbors differ by at most k. So |arr[i] - arr[i + 1]| <= k for every i. The array is not sorted. Find the first index where the number x appears, or return -1.

The neighbor rule lets you skip boxes you know cannot hold x.

A story to remember it

Picture it

array

Neighbors differ by at most k = 2. Standing on index 0 (value 2) and looking for 12: the next four boxes can be at most 4, 6, 8 and 10, so jump straight to index 5.

looking now
checking
ignored

Examples

Big jumps

In: arr = [2, 4, 6, 8, 6, 4, 5, 7, 9, 11, 12], k = 2, x = 12
Out: 10

Only four of the eleven boxes are checked: index 0, 5, 9 and 10.

A repeated value

In: arr = [4, 5, 6, 7, 6], k = 1, x = 6
Out: 2

6 is at index 2 and 4. The jumps never skip a box that could hold x, so the first one is found.

Bigger k

In: arr = [20, 40, 50, 70, 70, 60], k = 20, x = 60
Out: 5

From 20 the gap is 40, so jump 2 boxes. After that every gap is smaller than 20, so the jumps are 1.

Not there

In: arr = [1, 2, 3], k = 1, x = 10
Out: -1

From 1 the jump is 9 boxes, which is past the end. So 10 is not in the array.

Way 1: the simple way

Check every box from left to right.

java

class Solution {
    public int search(int[] arr, int k, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x) return i;
        }
        return -1;
    }
}

How long it takes: O(n). Extra room: O(1). It never uses the neighbor rule.

Way 2: the clever way

From box i, the value can change by at most k per box. To change by |arr[i] - x|, you need at least |arr[i] - x| / k boxes. So jump that many boxes at once.

Start at i = 0.
If arr[i] == x, return i.
Otherwise jump max(1, |arr[i] - x| / k) boxes, with whole number division. The max(1, ...) makes sure we always move.
If i runs past the end, return -1.

The boxes we skip are closer than |arr[i] - x| / k steps, so each of them is less than |arr[i] - x| away from arr[i] and cannot equal x.

Jump over boxes that cannot hold x

01 / 05

array

Neighbors differ by at most k = 2. We look for x = 12, starting at index 0.

k: 2
x: 12

looking now
seen
answer
ignored

java

class Solution {
    public int search(int[] arr, int k, int x) {
        int i = 0;
        while (i < arr.length) {
            if (arr[i] == x) return i;
            int jump = Math.max(1, Math.abs(arr[i] - x) / k);   // boxes that cannot be x
            i += jump;
        }
        return -1;
    }
}

How long it takes: in the worst case the values stay close to x without hitting it, every jump is 1, and this is still O(n). When the values start far from x, it skips a lot. Extra room: O(1).

Watch out for

A jump of 0 when |arr[i] - x| < k would loop forever. Always jump at least 1.
k = 0 means all values are equal. Then division by zero happens. Handle it first: check arr[0] == x.
The answer is the first index of x, because no skipped box can hold x.

What interviewers ask next

Same idea when neighbors differ by exactly 1 (a "step array"). The jump is |arr[i] - x|.
Why is the worst case still O(n)? Take k = 1 and values going 5, 6, 5, 6, ... while looking for 7. Every jump is 1 and 7 never appears.
Find all positions of x. After finding one, continue with a jump of max(1, ...) from the next box, since x can come back after at least 1 box.
A 2D version: a grid where neighbors differ by at most k. You can still skip, but the classic sorted matrix search (start at the top right corner) is the more common question.

Remember this

Grown-up words: the stepping stones are an array with bounded neighbor differences, hopping over stones is jump search, and the rule "at most k per step" is what makes the skipped boxes safe.