Iterative, bottom up, divide and conquer algorithm

Question

I was reading through this LeetCode article on a common algorithm problem, "Longest Common Prefix." They show a few different approaches, but my question pertains to just "Divide and Conquer." Its example shows the typical recursive top down approach you often see in books and blogs everywhere.

Looking at this got me thinking I should be able to do this "iteratively" and "bottom up" as well. Something like a bottom up merge sort approach. So here's where I ended up:

// type "Stack", function "prefix", and "min" implementations are not shown for brevity.
// Just assume they're defined somewhere and they work correctly.
//
// "prefix" function accepts two strings and returns a string
// Examples:
// prefix("abcd", "ab") returns "ab"
// prefix("abcd", "efgh") returns ""
// ... you get the idea.
//
// "min" does exactly what you'd expect. Its arguments are both type int.
func lcpDAndC(a []string) string {
        n := len(a)

        if n == 0 {
                return ""
        }

        var (
                stack Stack
                p, q  string
        )
        for lo := 0; lo < n; lo += 2 {
                hi := min(lo+1, n-1)
                stack = stack.Push(prefix(a[lo], a[hi])
        }

        for stack.Len() > 1 {
                p, q = stack.Pop2()
                stack.Push(prefix(p, q))
        }

        return stack.Pop1()
}

So my question is: Is this still considered "bottom up" and "divide and conquer?" I think it's safe to assume starting at the leaves right away (the bottom up part) can just be a matter of working on two elements at a time as it passes through the array once ("divide" ... but also "conquer?"). The stack here is of course playing an equal role as the call stack would in the recursive approach. Although, a queue would work just as well, which is another reason I'm thinking I've gone off the deep end here.

If this isn't a proper application of "bottom up" and "divide and conquer," does this at least apply some other theory that I don't know of?

asds_asds asds_asds · Accepted Answer · 2020-04-27T05:59:04

The recursion used in the article is Top Down since they break larger cases into smaller ones and then combine the result of the smaller ones.

In recursion function calls are pushed on top of one another onto the function call stack. They are popped off either

(1) Once the base case is reached

or

(2) Results of function calls above them in the stack has been computed and it's their turn now.

Your code does not do a Bottom Up Recursion and is also not D&C,

Consider this case:-

["care","car","cat","cater","click","clang","core","coral"]

Stack Initially:-

cor
cl
cat
car

While Loop Iteration #1:

c
cat
car

While Loop Iteration #2:

c
car

While Loop Iteration #3:

Your while loop combines the elements in a serial fashion and does not use the property of D&C. If you change lo+=2 in the for loop to lo+=1 then your code is the same as Approach 1: Horizontal scanning.

Using a Queue, however, would make the code a Bottom-Up Recursion. Notice how every time two elements are popped they represent two mutually exclusive halves that would've been found in the recursion tree of a Top Down approach as well. Consider this case:-

["care","car","cat","cater","click","clang","core","coral"]

Queue Initially:-

cor
cl
cat
car

While Loop Iteration #1:

ca
cor
cl

While Loop Iteration #2:

c
ca

While Loop Iteration #3:

Iterative, bottom up, divide and conquer algorithm

1 Answers