Unlock the Divide and Conquer method for solving problems | A New Approach in 2024

Introduction

Embarking on the journey of algorithmic problem-solving unveils a powerful strategy that has withstood the test of time—the “Divide and Conquer” method. This approach, steeped in elegance and efficiency, is a cornerstone in the realm of algorithm design. The essence of the “Divide and Conquer method” lies in breaking down complex problems into more manageable sub-problems, conquering them individually, and then intelligently combining their solutions to tackle the overarching challenge.

Much like a strategic general on the battlefield, this divide and conquer method strategically divides the problem landscape, enabling a systematic and optimized conquering of each segment.

In this introduction, we will delve into the principles that underlie the divide-and-conquer approach, exploring its applications across various algorithmic challenges.

As we navigate this algorithmic terrain, the Divide and Conquer method emerges as a guiding compass for unraveling intricate problems with finesse and efficiency. Join me on this exploration of a time-honored technique that continues to empower programmers and algorithm enthusiasts alike in their quest for elegant solutions.

Divide and Conquer method to solve the algorithmic problem – Sunset view problem

Problem Statement:- Given an array representing the height of buildings and the direction in which these buildings face, return an array containing indexes of all buildings in ascending order that can see the sunset( a building can see the sunset if its height is greater than all buildings height’s following it in the direction of the sunset.

Let us understand the problem with an example:- buildings heights -> [1, 4, 2, 3, 1, 2] and direction -> east

 4|.   __
 3|.   |.   |.    ___
 2|.   |    |__|.    |.   ___
  1|__|.   |.   |.    |__|.   |.        <-----  looking from this side since buildings are facing east
   |__|__|__|__|__|__|_____________ east----->

From a visual inspection of the above diagram, we can see that buildings with heights 4(index 1), 3(index 3), and 2(index 5) can only see the sunset in the east direction so the output will be [1, 3, 5] indexes of eligible buildings

If the direction would be west

                                                                                                            4|.   __
                                                                                                            3|.   |.   |.    ___
                                                                                                            2|.   |    |__|.    |.   ___
      looking from this side since buildings are facing west-->     1|__|.   |.   |.    |__|.   |.        
                                                                                                               |__|__|__|__|__|__|_____________ east----->

From a visual inspection of the above diagram, we can see that buildings with heights 1(index 0), and 4(index 1) can only see the sunset in the east direction so the output will be [0, 1] indexes of eligible buildings

Approach to dividing the problem (divide part of “divide and conquer method”)

• 2 subproblems Since two directions in which buildings are facing, let us solve one and then see if this solution can be applied to another direction
• Start with the basic solution (brute force) and optimize it to arrive at the final solution

Solution(Conquer part of “divide and conquer method”):-

brute force (basic solution)

for each building check if it is taller than all previous buildings (assuming the direction is east)

algorithm

sunsetView(buildings []int) -> []int {// returns int's array representing indexes of eligible buildings
    outputIndexes = []
    for i := 0; i < length; i++ {
	for j := 0; j <i; j++ {
		if buildings[j] < buildings[i] {
			continue
		} else {
			isTaller = false
			break
		}
	}
	if isTaller {
                  // append index i to output
		outputIndexes = append(outputIndexes, i)
	}
    }
    return outputIndexes
}
time Complexity = O(n2) since we are iterating the array n (array's length) times, basically for inside a for loop
Refer computation complexity to learn more on time complexity

Identify issues with the above approach and find a way to rectify them

suppose buildings[i] < buildings[i+1] < buildings[i+2] then We can imagine that this scenario might be occurring in the above code many many times

Can we use any information provided in the problem statement?

Yes, given problem states that a building must be greater than all following buildings for it to see the sunset if we can store the last building which is eligible to view the sunset then we need to compare the current building height to this building. Since the last building will always be visible we will add this to our result set and compare the previous index to this and continues this operation until we reach the first index.

# divide and conquer method

psuedo code
func SunsetView(buildings []int) -> []int {
     length = len(builldings)
     lastIndex = length - 1
    
    outputIndexes := []
    outputIndexes := append(outputIndexes, lastIndex) // store last building's index since this always be visible
    for i := lastIndex - 1; i >= 0; i-- {
        lastTallestBuildingIndex = outputIndexes[len(outputIndexes) - 1] // last element in outputIndexes
        lastTallestBuildingHeight = buildings[lastTallestBuildingIndex]
        if building[i] > lastTallerBuildingHeight {
            lastTallerBuildingHeight = building[i]
            //append lastTallerBuildingHeight index (i) to outputIndexes (result set)
            outputIndexes = append(outputIndexes, i)
        }
    }
    return outputIndexes
}

Note for the west direction we need to do this from first to last index, basically, the reverse of this order.

time Complexity = O(n) since we are iterating the array only once

space Complexity = O(n) since we are storing indexes of the array

Check for boundary condition

if the length of the building’s array is zero (null or empty array) then return []int{} empty array(obvious)

if the length of the building’s array is 1 then return []int{0} since a single building will always be visible since no other building will be taller than this.

// Implementation in golang (please learn this, this is a simple language to understand
package main

import "fmt"

func main() {
     buildings := []int{1, 3, 5, 2, 1}
     result := SunsetViews(buildings, "east")
    fmt.Println(result)
}

func SunsetViews(buildings []int, direction string) []int {
	// Write your code here.
    //use stack to check if current building height is greater > all the next
    // so process end building first and so on
    // in case direction is west, reverse the output array

    if len(buildings) == 0 {
        return []int{}
    }

    if len(buildings) == 1 {
        return []int{0}
    }
    
    var outputIndexes []int
    length := len(buildings)
    if direction == "EAST" {
        // scan from end
        outputIndexes = append(outputIndexes, length - 1)
        for i := length - 2; i >= 0; i-- {
            outputIndexes = addBuildingToSunsetViews(buildings, outputIndexes, i)
        }
        reverseArray(outputIndexes)
    } else {
        // scan from start
        outputIndexes = append(outputIndexes, 0)
        for i := 1; i < length; i++ {
           outputIndexes = addBuildingToSunsetViews(buildings, outputIndexes, i)
        }
    }
	return outputIndexes
}

func addBuildingToSunsetViews(buildings, outputIndexes []int, currIndex int) []int {
    lastBuildingIndex := outputIndexes[len(outputIndexes) - 1]
    lastBuildingHeight := buildings[lastBuildingIndex]
    if buildings[currIndex] > lastBuildingHeight {
        outputIndexes = append(outputIndexes, currIndex)
    }
    return outputIndexes
}

func reverseArray(array []int) {
    for i, j := 0, len(array) - 1; i < j; {
        array[i], array[j] = array[j], array[i]
        i++
        j--
    }
}
// check it here:- SunsetView

Note: Please install Go to run it locally

Key Takeaways of Divide and Conquer method to solve any coding problem

• Divide problem into subprolems. This is the most important and difficult part and key to problem-solving.Take the help of all the key information already given in the problem statement. Use common sense to derive information that is not given in the problem or indirectly implied by the problem (e.g, the age of people should range from 0 – 200 years)
• First, solve these subproblems. This is the easy part.
• Combine all sub-solutions into a final solution.
• Test the solution.
• Keep practicing divide and conquer method on as many problems as you can. Practice is the key to success.

Conclusion

In conclusion, the Divide and Conquer method stands as an enduring beacon in the landscape of algorithmic problem-solving. Its brilliance lies in the systematic breakdown of complexity, allowing for efficient conquering of individual facets. As we traverse through diverse algorithmic challenges, this strategy consistently proves its mettle, offering not only solutions but a structured approach that enhances scalability and performance.

The elegance of Divide and Conquer method persists as a timeless guide, empowering programmers to dissect intricate problems with clarity and precision. Its legacy endures, marking a steadfast methodology that continues to shape the way we unravel and triumph over complex algorithmic puzzles.