Is this a typo in Space Complexity section example?

Hello,

So I started reading through the Data Structures and Algorithms Book and noticed something that doesn’t seem to match the explanation.

In the Space Complexity example, the optimization example has the following code:

func printSorted(array: [Int]) {
    // 1
    guard !array.isEmpty else { return }
    
    // 2
    var currentCount = 0
    var minValue = Int.min
    
    // 3
    for value in array {
        if value == minValue {
            print(value)
            currentCount += 1
        }
    }
    
    while currentCount < array.count {
        
        // 4
        var currentValue = array.max()!
        
        for value in array {
            if value < currentValue && value > minValue {
                currentValue = value
            }
        }
        
        // 5
        for value in array {
            if value == currentValue {
                print(value)
                currentCount += 1
            }
        }
        
        // 6
        minValue = currentValue
    }
}

From the explanation of the example, section 3 states:

“The algorithm begins by printing out all values matching the minValue, and updates the currentCount according to the number of print statements made.”

To me, this sounds like the minValue should be the minimum value in the array, so is minValue supposed to be array.min() instead of Int.min? It looks like the if statement will never be hit unless the array passed in contains the actual Int.min value (i.e -9223372036854775808)

Am I missing something about the logic/why it is Int.min or is this a typo?

Hi @cabmeurer ,
Good question when you code it does seem a bit confusing. However, that is not the case. In a larger overview, Int.min is the smallest number that is represented as an Int. It is used for sorting the numbers, with each pass, the number is replaced with the number larger than the smallest number and so on.

Have you tried to run the code? It does run and work

cheers,

1 Like

Hello @jayantvarma
Thank you for the quick response. That all makes sense to me, I was playing around with it and am wondering why we need this check:

   for value in array {
        if value == minValue {
            print(value)
            currentCount += 1
        }
    }

It looks like we will never step into the if statement unless the array actually contains an Int.min. For example this works:

func printSorted(array: [Int]) {
    
    guard !array.isEmpty else { return }
    
    var currentCount = 0
    var minValue = Int.min
    
    while currentCount < array.count {
        
        var currentValue = array.max()!
        
        for value in array {
            if value < currentValue && value > minValue {
                currentValue = value
            }
        }
        
        for value in array {
            if value == currentValue {
                print(value)
                currentCount += 1
            }
        }
        
        minValue = currentValue
    }
}

The other idea would be what I was asking before… if we set the minValue to the array.min(), this works the same as the above solution:

func printSorted(array: [Int]) {
    // 1
    guard !array.isEmpty else { return }
    
    // 2
    var currentCount = 0
    var minValue = array.min()!
    
    // 3
    for value in array {
        if value == minValue {
            print(value)
            currentCount += 1
        }
    }
    
    while currentCount < array.count {
        
        // 4
        var currentValue = array.max()!
        
        for value in array {
            if value < currentValue && value > minValue {
                currentValue = value
            }
        }
        
        // 5
        for value in array {
            if value == currentValue {
                print(value)
                currentCount += 1
            }
        }
        
        // 6
        minValue = currentValue
    }
}

Hi @cabmeurer
what you are finding it not wrong, it can also work. I recollect around 2014 when swift was new and this Java developer was speaking of how to rotate an array and he did not want to believe that you can do that easily in Swift. There are always more solutions to a problem, which is the most optimal and why the authors chose that only they can tell.

But good find.

Cheers,

Jayant

1 Like