CODEWITHSUNDEEP
swiftalgorithm
Glenn Posadas
Glenn Posadas

Reputation: 13290

Swift Mini-Max Sum One Test Case Failed - HackerRank

Before anything else, I checked if this kind of question fits Stackoverflow, and based on one similar question (javascript) and from this question: https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-sites-do-i-post-on -- it does.

So here it goes. The challenge is pretty simple, in my opinion:

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

For example, . Our minimum sum is and our maximum sum is . We would print

16 24

Input Constraint: 1 <= arr[i] <= (10^9)

My solution is pretty simple. This is what I could do best:

func miniMaxSum(arr: [Int]) -> Void {
    let sorted = arr.sorted()
    let reversed = Array(sorted.reversed())
    var minSum = 0
    var maxSum = 0

    _ = sorted
        .filter({ $0 != sorted.last!})
        .map { minSum += $0 }  
    _ = reversed
        .filter({ $0 != reversed.last!})
        .map { maxSum += $0 }    

    print("\(minSum) \(maxSum)")
}

As you can see, I have two sorted arrays. One is incrementing, and the other one is decrementing. And I'm removing the last element of the two newly sorted arrays. The way I remove the last element is using filter, which probably creates the problem. But from there, I thought I could get easily the minimum and maximum sum of the 4 elements.

I had 13/14 test cases passed. And my question is, what could be the test case in which this solution will likely to fail?

Problem link: https://www.hackerrank.com/challenges/mini-max-sum/problem

Upvotes: 2

Views: 2181

Answers (6)

Yar
Yar

Reputation: 16

Try this:

func miniMaxSum(arr: [Int]) -> Void {
let min = arr.min()
let max = arr.max()
let total = arr.reduce(0, +)
print(total - max!, total - min!, separator: " ")
}

Upvotes: 0

ielyamani
ielyamani

Reputation: 18591

Here is the O(n) solution:

func miniMaxSum(arr: [Int]) {
    var smallest = Int.max
    var greatest = Int.min
    var sum = 0

    for x in arr {
        sum += x
        smallest = min(smallest, x)
        greatest = max(greatest, x)
    }

    print(sum - greatest, sum - smallest, separator: "  ")
}

Upvotes: 3

Alexander
Alexander

Reputation: 63311

I know this isn't codereview.stackexchange.com, but I think some clean up is in order, so I'll start with that.

  1. let reversed = Array(sorted.reversed())

    The whole point of the ReversedCollection that is returned by Array.reversed() is that it doesn't cause a copy of elements, and it doesn't take up any extra memory or time to produce. It's merely a wrapper around a collection, and intercepts indexing operations and changes them to immitate a buffer that's been reversed. Asked for .first? It'll give you .last of its wrapped collection. Asked for .last? It'll return .first, etc.

    By initializing a new Array from sorted.reversed(), you're causing an unecessary copy, and defeating the point of ReversedCollection. There are some circumstances where this might be necessary (e.g. you want to pass a pointer to a buffer of reversed elements to a C API), but this isn't one of them.

    So we can just change that to let reversed = sorted.reversed()

  2. -> Void doesn't do anything, omit it.

  3. sorted.filter({ $0 != sorted.last!}) is inefficient.

    ... but more than that, this is the source of your error. There's a bug in this. If you have an array like [1, 1, 2, 3, 3], your minSum will be 4 (the sum of [1, 1, 2]), when it should be 7 (the sum of [1, 1, 2, 3]). Similarly, the maxSum will be 8 (the sume of [2, 3, 3]) rather than 9 (the sum of [1, 2, 3, 3]).

    You're doing a scan of the whole array, doing sorted.count equality checks, only to discard an element with a known position (the last element). Instead, use dropLast(), which returns a collection that wraps the input, but whose operations mask the existing of a last element.

    _ = sorted
    .dropLast()
    .map { minSum += $0 }      
_ = reversed
    .dropLast()
    .map { maxSum += $0 }

  4. _ = someCollection.map(f)

    ... is an anti-pattern. The distinguishing feature between map and forEach is that it produces a resulting array that stores the return values of the closure as evaluated with every input element. If you're not going to use the result, use forEach

    sorted.dropLast().forEach { minSum += $0 }  
reversed.dropLast().forEach { maxSum += $0 }

    However, there's an even better way. Rather than summing by mutating a variable and manually adding to it, instead use reduce to do so. This is ideal because it allows you to remove the mutability of minSum and maxSum.

    let minSum = sorted.dropLast().reduce(0, +)
let maxSum = reversed.dropLast().reduce(0, +)

  5. You don't really need the reversed variable at all. You could just achieve the same thing by operating over sorted and using dropFirst() instead of dropLast():

    func miniMaxSum(arr: [Int]) {
    let sorted = arr.sorted()

    let minSum = sorted.dropLast().reduce(0, +)
    let maxSum = sorted.dropFirst().reduce(0, +)

    print("\(minSum) \(maxSum)")
}

  6. Your code assumes the input size is always 5. It's good to document that in the code:

    func miniMaxSum(arr: [Int]) {
    assert(arr.count == 5)

    let sorted = arr.sorted()

    let minSum = sorted.dropLast().reduce(0, +)
    let maxSum = sorted.dropFirst().reduce(0, +)

    print("\(minSum) \(maxSum)")
}

  7. A generalization of your solution uses a lot of extra memory, which you might not have available to you.

    This problem fixes the number of summed numbers (always 4) and the number of input numbers (always 5). This problem could be generalized to picking summedElementCount numbers out of any sized arr. In this case, sorting and summing twice is inefficient:

    • Your solution has a space complexity of O(arr.count)
      • This is caused by the need to hold the sorted array. If you were allowed to mutate arr in-place, this could reduce to `O(1).

    • Your solution has a time complexity of O((arr.count * log_2(arr.count)) + summedElementCount)

      • Derivation: Sorting first (which takes O(arr.count * log_2(arr.count))), and then summing the first and last summedElementCount (which is each O(summedElementCount))

          O(arr.count * log_2(arr.count)) + (2 * O(summedElementCount))
= O(arr.count * log_2(arr.count)) + O(summedElementCount) // Annihilation of multiplication by a constant factor
= O((arr.count * log_2(arr.count)) + summedElementCount) // Addition law for big O

    This problem could instead be solved with a bounded priority queue, like the MinMaxPriorityQueue in Google's Gauva library for Java. It's simply a wrapper for min-max heap that maintains a fixed number of elements, that when added to, causes the greatest element (according to the provided comparator) to be evicted. If you had something like this available to you in Swift, you could do:

    func miniMaxSum(arr: [Int], summedElementCount: Int) {
    let minQueue = MinMaxPriorityQueue<Int>(size: summedElementCount, comparator: <)
    let maxQueue = MinMaxPriorityQueue<Int>(size: summedElementCount, comparator: >)

    for i in arr {
        minQueue.offer(i)
        maxQueue.offer(i)
    }

    let (minSum, maxSum) = (minQueue.reduce(0, +), maxQueue.reduce(0, +))

    print("\(minSum) \(maxSum)")
}

    • This solution has a space complexity of only O(summedElementCount) extra space, needed to hold the two queues, each of max size summedElementCount.

      • This is less than the previous solution, because summedElementCount <= arr.count

    • This solution has a time complexity of O(arr.count * log_2(summedElementCount))

      • Derviation: The for loop does arr.count iterations, each consisting of a log_2(summedElementCount) operation on both queues.

          O(arr.count) * (2 * O(log_2(summedElementCount)))
= O(arr.count) * O(log_2(summedElementCount)) // Annihilation of multiplication by a constant factor
= O(arr.count * log_2(summedElementCount)) // Multiplication law for big O

      • It's unclear to me whether this is better or worse than O((arr.count * log_2(arr.count)) + summedElementCount). If you know, please let me know in the comments below!

Upvotes: 1

Martin R
Martin R

Reputation: 539915

Here

_ = sorted
    .filter({ $0 != sorted.last!})
    .map { minSum += $0 }

your expectation is that all but the largest element are added. But that is only correct it the largest element is unique. (And similarly for the maximal sum.)

Choosing an array with all identical errors makes the problem more apparent:

miniMaxSum(arr: [1, 1, 1, 1, 1])
// 0 0

A simpler solution would be to compute the sum of all elements once, and then get the result by subtracting the largest respectively smallest array element. I'll leave the implementation to you :)

Upvotes: 3

Naser Mohamed
Naser Mohamed

Reputation: 146

Try this one accepted:

func miniMaxSum(arr: [Int]) -> Void {
    let sorted = arr.sorted()
    let minSum = sorted[0...3].reduce(0, +)
    let maxSum = sorted[1...4].reduce(0, +)
    print("\(minSum) \(maxSum)"
}

Upvotes: 1

Anupam Mishra
Anupam Mishra

Reputation: 3588

Try this-

func miniMaxSum(arr: [Int]) -> Void {

var minSum = 0
var maxSum = 0
var minChecked = false
var maxChecked = false
let numMax = arr.reduce(Int.min, { max($0, $1) })
print("Max number in array: \(numMax)")

let numMin = arr.reduce(Int.max, { min($0, $1) })
print("Min number in array: \(numMin)")

for item in arr {

    if !minChecked && numMin == item {
        minChecked = true
    } else {
        maxSum = maxSum + item
    }

    if !maxChecked && numMax == item {
        maxChecked = true
    } else {
        minSum = minSum + item
    }
}
print("\(minSum) \(maxSum)")
}

Upvotes: 0

Related Questions