## Greedy Algorithms

As the name suggests, greedy algorithms work by making a decision and then sticking to it. Greedy algorithms doesn’t always give the exact solution since there maybe different solutions satisfying a set of constraints.

Greedy algorithms are easier to think about since we only need to come up with a choice that satisfies a set of constraints we’ve been given. For example, **finding the maximum** number in a set of numbers is example of **greedy algorithm** since the choice we make is to go with the largest number and then take care of the rest.

Basic idea in a greedy algorithm is

- Find out what constraints are to be applied.
- Make a subproblem and apply the same constraints to it.

**NOTE:** This algorithm strategy attempts to give “**an”** optimal solution **not** **“the”** optimal solution.

### Example:

### Create the maximum number by concatenating a bunch of numbers

Let’s take a look at this using a couple of examples

- Suppose we’ve numbers 8,0,9 then we can make the maximum number
**980.**To make the maximum number we should start with big digits so we pick**9, 8 and 0**in that order. - Suppose now we’ve numbers 67, 61 and 4. Now the maximum number we can make is
**67614**which is again by picking**67, 61 and 4**in that order. - Suppose we’ve
**68, 601, 6, 619**now the maximum number would be**686619601**by choosing**68, 6, 619 and 601**in that order.

If we’re to design an algorithm we can think of something like the following,

- Find the number having the largest starting digit.
- If there are more than one numbers having same digit we choose the number with the next bigger digit or the number which had no further digits, if it was the largest digit in the next comparison of digits.
- Append this number to the current maximum.
- Repeat this process for all numbers until none is left.

## Code

This one is written in go since it was simpler to create subarrays. The code uses a book keeping structure to identify which of the numbers have been processed. I’ve used an array of pointers for slice since when we modify slice it’s created a fresh by copying and structs in go are copied **by value** .

The code is really simple and easy to understand, you can also find some more algorithms and their test suites on

```
package algo
import (
"log"
"strconv"
"unicode/utf8"
)
type numberProcess struct {
processed bool
value string
}
// MaxNumber returns the maximum number which can be made by
// concatenating a bunch of non-negative numbers. The numbers
// themselves can be of any length and in any order.
func MaxNumber(numbers []string) string {
maxNumber := ""
count := len(numbers)
var allNumbers []*numberProcess
for _, val := range numbers {
allNumbers = append(allNumbers, &numberProcess{processed: false, value: val})
}
//Until we've numbers left
//We do this process.
for count > 0 {
maxNumber += maxNumberInternal(allNumbers)
count -= 1
}
return maxNumber
}
// maxNumberInternal returns the maximum number using which
// we can create a bigger number.
func maxNumberInternal(numbers []*numberProcess) string {
currentDigit := 1 //start by looking at the first digit.
currentMax := -1 //since negative numbers aren't possible, this acts as a sentinel
didProcessed := false //were we able to process at least one number.
var whichNumber *numberProcess
find_again:
initialLength := len(numbers)
for i := 0; i < len(numbers); i++ {
if numbers[i].processed {
continue
}
didProcessed = true
numberDigit := getDigitAt(numbers[i].value, currentDigit)
// if there's no current maximum digit set,
// set it to this one.
if currentMax < 0 {
currentMax = numberDigit
whichNumber = numbers[i]
continue
}
// if the current maximum is lesser, then we can safely
// remove the numbers we've seen so far. This block essentially
// shortens the rest of the slice and starts to look up from
// the beginning.
if currentMax < numberDigit {
currentMax = numberDigit
whichNumber = numbers[i]
numbers = numbers[i:]
i = 0 //0 since it'll be incremented by the for loop.
} else if currentMax > numberDigit { //if the currentMaximum is bigger just remove this number.
numbers = removeFromSlice(numbers, i)
i -= 1
}
}
// If we processed something and there were multiple numbers
// with the same digits then we've to try and find again.
// Note that when we do actually come here it implies that there
// were multiple numbers found with the same currentMax and that we need
// to lookup again, albeit only on those numbers.
if didProcessed && len(numbers) > 1 && initialLength != len(numbers) {
currentDigit += 1
didProcessed = false
currentMax = -1
whichNumber = nil
goto find_again
}
if whichNumber != nil {
whichNumber.processed = true
return whichNumber.value
}
return ""
}
// removeFromSlice removes from a specific index within slice
// and returns a new slice without that index element in it.
func removeFromSlice(numbers []*numberProcess, index int) []*numberProcess {
var newSlice []*numberProcess
if len(numbers) == 0 || index < 0 || index >= len(numbers) {
return newSlice
}
newSlice = append(newSlice, numbers[:index]...)
newSlice = append(newSlice, numbers[index+1:]...)
return newSlice
}
func getDigitAt(number string, digitNumber int) int {
value := ""
//Though we could've easily iterated using indexing we did it using runes
//Note that we need to find out the digit at digitNumber and if it's not
//possible, i.e. the number is shorter in length than digitNumber we just
//return the last digit of number since that's the only one that matters
//due to which we're about to do a tie break.
for i, w := 0, 0; digitNumber > 0 && i < len(number); i += w {
runeVal, width := utf8.DecodeRuneInString(number[i:])
value = string(runeVal)
w = width
digitNumber -= 1
}
intVal, err := strconv.Atoi(value)
if err != nil { //This should never happen for correct input.
log.Fatalf("Error finding digit for number %s at index %d",
number, digitNumber)
return 0
}
return intVal
}
```