CODEWITHSUNDEEP
algorithm
quirkystack
quirkystack

Reputation: 1407

Finding minimum element to the right of an index in an array for all indices

Given an array, I wish to find the minimum element to the right of the current element at i where 0=<i<n and store the index of the corresponding minimum element in another array.

For example, I have an array A ={1,3,6,7,8} The result array would contain R={1,2,3,4} .(R array stores indices to min element). I could only think of an O(N^2) approach.. where for each element in A, I would traverse the remaining elements to right of A and find the minimum. Is it possible to do this in O(N)? I want to use the solution to solve another problem.

Upvotes: 0

Views: 676

Answers (2)

Anil Vaitla
Anil Vaitla

Reputation: 2978

Looks like HW. Let f(i) denote the index of the minimum element to the right of the element at i. Now consider walking backwards (filling in f(n-1), then f(n-2), f(n-3), ..., f(3), f(2), f(1)) and think about how information of f(i) can give you information of f(i-1).

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 881153

You should be able to do this in O(n) by filling the array from the right hand side and maintaining the index of the current minimum, as per the following pseudo-code:

def genNewArray (oldArray):
    newArray = new array[oldArray.size]
    saveIndex = -1
    for i = newArray.size - 1 down to 0:
        newArray[i] = saveIndex
        if saveIndex == -1 or oldArray[i] < oldArray[saveIndex]:
            saveIndex = i
    return newArray

This passes through the array once, giving you the O(n) time complexity. It can do this because, once you've found a minimum beyond element N, it will only change for element N-1 if element N is less than the current minimum.

The following Python code shows this in action:

def genNewArray (oldArray):
    newArray = []
    saveIndex = -1
    for i in range (len (oldArray) - 1, -1, -1):
        newArray.insert (0, saveIndex)
        if saveIndex == -1 or oldArray[i] < oldArray[saveIndex]:
            saveIndex = i
    return newArray

oldList = [1,3,6,7,8,2,7,4]
x = genNewArray (oldList)

print "idx", [0,1,2,3,4,5,6,7]
print "old", oldList
print "new", x

The output of this is:

idx [0, 1, 2, 3, 4, 5, 6, 7]
old [1, 3, 6, 7, 8, 2, 7, 4]
new [5, 5, 5, 5, 5, 7, 7, -1]

and you can see that the indexes at each element of the new array (the second one) correctly point to the minimum value to the right of each element in the original (first one).

Note that I've taken one specific definition of "to the right of", meaning it doesn't include the current element. If your definition of "to the right of" includes the current element, just change the order of the insert and if statement within the loop so that the index is updated first:

idx [0, 1, 2, 3, 4, 5, 6, 7]
old [1, 3, 6, 7, 8, 2, 7, 4]
new [0, 5, 5, 5, 5, 5, 7, 7]

The code for that removes the check on saveIndex since you know that the minimum index for the last element can be found at the last element:

def genNewArray (oldArray):
    newArray = []
    saveIndex = len (oldArray) - 1
    for i in range (len (oldArray) - 1, -1, -1):
        if oldArray[i] < oldArray[saveIndex]:
            saveIndex = i
        newArray.insert (0, saveIndex)
    return newArray

Upvotes: 1

Related Questions