Searching in an array where adjacent differ by at most k

Problem Statement

Given an array where adjacent elements differ by at most k, search for a given element x. If x is present, return its index; otherwise, return -1.

Constraints:

• Adjacent elements differ by at most k: |arr[i] - arr[i+1]| <= k
• Array is not necessarily sorted
• k >= 1

Example:

• Input: arr = [4, 5, 6, 7, 6], k = 1, x = 6
• Output: 2 (or 4, since 6 appears at both indices)
• Explanation: 6 is found at index 2

Example 2:

• Input: arr = [20, 40, 50, 70, 70, 60], k = 20, x = 60
• Output: 5
• Explanation: 60 is found at index 5

Approach 1: Brute Force (Linear Search)

Intuition

Simply scan through all elements to find the target.

Algorithm

1. Traverse the array from index 0 to n-1
2. If current element equals x, return index
3. Return -1 if not found

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

Complexity Analysis

• Time Complexity: O(n) - May need to check all elements
• Space Complexity: O(1) - No extra space

Approach 2: Jump Search Based on Difference (Optimal)

Intuition

Since adjacent elements differ by at most k, we can calculate the minimum number of steps needed to reach x from the current element and jump directly.

Key Insight:

• If arr[i] = a and we're looking for x
• Difference = |x - a|
• Minimum steps to reach x = ceil(|x - a| / k)
• We can safely skip to index i + max(1, |x - a| / k)

Algorithm

1. Start from index i = 0
2. If arr[i] == x, return i
3. Calculate jump = max(1, |arr[i] - x| / k)
4. Move i += jump
5. Repeat until i >= n
6. Return -1 if not found

public class Solution {
    public int searchWithJump(int[] arr, int k, int x) {
        int n = arr.length;
        int i = 0;
        
        while (i < n) {
            // Found the element
            if (arr[i] == x) {
                return i;
            }
            
            // Calculate minimum steps needed
            int diff = Math.abs(arr[i] - x);
            int jump = Math.max(1, diff / k);
            
            i += jump;
        }
        
        return -1;
    }
}

Dry Run Example

Why This Works

Complexity Analysis

• Time Complexity: O(n/k) average case
  • In the worst case (x is at the end, values oscillate), it's O(n)
  • In the best case, we jump in large steps
• Space Complexity: O(1) - Only using variables

Finding All Occurrences

Variation: Bidirectional Search

Start from both ends and meet in the middle.

Edge Cases

Comparison with Standard Approaches

| Approach | Time Complexity | When to Use | |----------|----------------|-------------| | Linear Search | O(n) | Always works | | Jump Search | O(n/k) avg | Adjacent differ by ≤ k | | Binary Search | O(log n) | Sorted array | | Hash Table | O(1) avg | Preprocessing allowed |

Key Takeaways

1. Constraint Exploitation: The constraint |arr[i] - arr[i+1]| <= k allows smart jumping
2. Jump Calculation: jump = max(1, |current - target| / k) is the key formula
3. Safe Skipping: We can safely skip positions because target can't exist there
4. Average Case: O(n/k) is much better than O(n) when k is small
5. Worst Case: Still O(n) when values oscillate around target
6. Applications: Step-limited search, constrained sequences, sensor data with limited change rate