Tag Archives: Arrays

Searching for an element in array of adjacent numbers

Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?

For example consider the array {1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5.

The simplest solution is to check if the number is present or not using linear search. This algorithm takes O(n) time in the worst case.
But we are not utilizing the fact that the adjacent numbers differ by 1.

How do we utilize this property to improve the performance?

Let us assume we are searching for a number x+3 in an array.
Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have

x, x+1, x+2, x+3, ...
x, x+1, x, x+1, ...
x, x-1, x, x+1, ...
x, x-1, x-2, x-1, ...
x, x+1, x+2, x+1, ...
etc...

We can safely jump to index 3 and check if the number is present. Why? Because in any pattern there is no chance of having x+3 before the index 3.
If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.

The time complexity of the above procedure is still O(n), because in the worst case, we make n/2 jumps. But this is an improvement over the linear search (n comparisons in the worst case).

Example, search for number 6 in the array {4, 5, 4, 5, 4, 5, 4, 5, 4, 5}, we have to make 5 jumps to conclude that 6 is not present.

Here is the C++ implementation of the same.

Check if an array has a sub-array with given sum

Given an array of numbers and a sum, how to check if there is any sub-array with the given sum.

For example consider an array A = [7, 2, 9, 1, 5], and the sum is 12, then we can find a sub-array [2, 9, 1] which sums up to 12. So the answer is Yes. If we want to check for sum 14, we can not find a sub-array with that sum.

A simple method is to check if a sum can be found for all possible sub-arrays. This solution takes O(n3) time.

A more efficient method is the sliding window method. We maintain two indices, one indicates the beginning of the window, and the other indicates the ending of the window.

While iterating through the elements, we increment the end-index as long as the current sum is less than or equal to the target. If we find the target sum, then we are done. If we exceed the target sum, we deduct the beginning elements from the current sum until it is less than or equal to target sum.

This approach takes O(n) time. Here is the C++ code.