CODEWITHSUNDEEP
algorithmsorting
wrek
wrek

Reputation: 1161

Algorithm: finding closest differences between two elements of array

You have a array, and a target. Find the difference of the two elements of the array. And this difference should be closest to the target.

(i.e., find i, j such that (array[i]- array[j]) should be closest to target)

Attempt: I use a order_map (C++ hash-table) to store each element of the array. This would be O(n). Then, I output the ordered element to a new array (which is sorted increasing number).

Next, I use two pointers.

int mini = INT_MAX, a, b;
for (int i=0, j = ordered_array.size() -1 ; i <j;) {
    int tmp = ordered_array[i] - ordered_array[j];
    if (abs(tmp - target) < mini) {
             mini = abs(tmp - target); 
             a = i;
             b = j;
       }
    if (tmp == target) return {i,j}; 
    else if (tmp > target) j --; 
    else i ++; 
}
return {a,b};

Question:

Is my algorithm still runs at O(n)?

Upvotes: 0

Views: 998

Answers (2)

Henry
Henry

Reputation: 43798

If the array is already sorted, there is an O(n) algorithm: let two pointers swipe up through the array, whenever the difference between the pointed at elements is smaller than target increase the upper one, whenever it is larger than target increase the lower one. While doing so, keep track of the best result found so far.

When you reach the end of the array the overall best result has been found.

It is easy to see that this is really O(n). Both pointers will only move upwards, in each step you move exactly one pointer and the array has n elements. So after at most 2n steps this will halt.

As already mentioned in some comments, if you need to sort the array first, you need the O(n log n) effort for sorting (unless you can use some radix sort or counting sort).

Upvotes: 2

MBo
MBo

Reputation: 80287

Your searching phase is linear. Two-pointers approach is equivalent to this:

Make a copy of sorted array   
Add `target` to every entry (shift values up or down) (left picture)   
Invert shifted array indexing (right picture)   
Walk through both arrays in parallel, checking for absolute difference 
All stages are linear  (and inverting is implicit in your code)

enter image description here

P.S. Is C++ hash map ordered? I doubt. Sorted array creation is in general O(nlogn) (except for special methods like counting or radix sort)

Upvotes: 1

Related Questions