Divide and conquer strategy python

Question

I am trying to write a code which to compare each element of a list and give the index of the closet larger number in two direction: left or right. Using the divide and conquer method

For example:

Input: arr=[5,2,6,8,1,4,3,9]
Output:
Left=[None, 0, None, None, 3, 3, 5, None]
Right=[2, 2, 3, 7, 5, 7, 7, None]

Input: arr=[4,2,3,1,8,5,6,9]
Output:
L=[None, 0, 0, 2, None, 4, 4, None]
R=[4, 2, 4, 4, 7, 6, 7, None]

This is what I have now:

arr = [5,2,6,8,1,4,3,9]
def Left(arr):
    L = []
    for i in range(len(arr)):
        flag = True
        for j in range(i,-1,-1):
            if (arr[i] < arr[j]):
                L.append(j)
                flag = False
                break
        if flag:
            L.append(None)
    return L

def Right(arr):
    R = []
    for i in range(len(arr)):
        flag = True
        for j in range(i, len(arr), 1):
            if (arr[i] < arr[j]):
                R.append(j)
                flag = False
                break
        if flag:
                R.append(None)
    return R

print(*Left(arr), sep = ",")
print(*Right(arr), sep =",")

Am I doing it in a right way? Thank you.

Answer 1

This is my python version code for the algorithm in its "closest larger right" version.
Obviously, as you can see it is recursive. Recursion is really elegant but a bit tricky because few lines of code condense lots of concepts regarding to algorithms design and the own language they are coded. In my opinion 4 relevant moments are happening:

• 1) Recursive calls. Function is call to itself. During this step the list progresible slice into halves. Once the atomic unit is reached the base algorithm will be executed over them firstly (step 3). if not solution is reached greater list sizes will be involved in the calculation in further recursions.
• 2) Termination condition. Previous step is not run forever, it allows stop recursion and going to the next step (base algorithm). Now the code has len(arr) > 1: that means that the atomic unit will be pairs of numbers (or one of three in case of odd list). You can increase the number so that the recursive function will stay less time slicing the list and summarizing the results, but the counterpart is that in a parallelized environment "workers" will have to digest a bigger list.
• 3) Base algorithm. It makes the essential calculation. Whatever the size of the list, it returns the indexes of its elements to the right closest larger number
• 4) "Calculation saving". The base algorithm no need to calculated indexes on those numbers resolved in previous recursions. There is also a break to stop calculations once the number gets the index in the current recursion list.

Other algorithms models could be design, more efficient for sure. It occurs to me ones based on dictionaries or on different slicing strategies.

def closest_larger_right(arr):

    len_total = len(arr)
    result = [None] * len_total

    def recursive(arr, len_total, position=0):

        # 2) Termination condition
        if len(arr) > 1:

            mid = len(arr) // 2
            left = arr[:mid]
            right = arr[mid:]

            position_left = 0 + position
            position_right = len(left) + position

            # 1) Recursive calls
            recursive(left, len_total, position_left)
            recursive(right, len_total, position_right)

            # 3) Base algorithm
            for i in range(len(arr)-1):
                # 4) Calculation saving
                if result[i + position] is None:
                    for j in range(i+1, len(arr), 1):
                        if (arr[i] < arr[j]):
                            result[i + position] = j + position
                            break
            return result

    return recursive(arr, len_total)

# output: [2, 2, 3, 7, 5, 7, 7, None]
print(closest_larger_right([5, 2, 6, 8, 1, 4, 3, 9]))

Answer 2

I am not sure how a divide-and-conquer algorithm can be applied here, but here's an improvement to your current algorithm that also already has optimal running time of O(n) for n elements in the array:

stack = []
left = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        stack.pop()
    left.append(stack[-1] if stack else None)
    stack.append(i)

This uses a stack to keep track of the indices of the larger elements to the left, popping indices from the stack as long as their element are smaller than the current element, and then adding the current index itself. Since each element is added to and popped from the stack at most once, running time is O(n). The same can be used for the right-side elements simply by iterating the array in reverse order.