3

I am trying to find the highest frequency element in the given as follows.

First, I am trying to build a dictionary and count the each element based on frequency.

I am stuck how to extract max value from the constructed dictionary.

Input: [3,2,3]

Output: 3

func majorityElement(_ nums1: [Int]) -> Int {

    var num1Dict = Dictionary(nums1.map{ ($0, 1) }, uniquingKeysWith : +)
    return num1Dict.values.max() // ????

}
Community
  • 1
  • 1
casillas
  • 16,351
  • 19
  • 115
  • 215

3 Answers3

1

You have correctly constructed num1Dict, which will be something like this for the input [3,2,3]:

[2:1, 3:2]

values.max() will return 2, because out of all the values in the dictionary (1 and 2), 2 is the highest.

See your error now?

You need to return the key associated with the highest value, not the highest value.

One very straightforward way is to do this:

func majorityElement(_ nums1: [Int]) -> Int? { // you should probably return an optional here in case nums1 is empty

    let num1Dict = Dictionary(nums1.map{ ($0, 1) }, uniquingKeysWith : +)
    var currentHigh = Int.min
    var mostOccurence: Int?
    for kvp in num1Dict {
        if kvp.value > currentHigh {
            mostOccurence = kvp.key
            currentHigh = kvp.value
        }
    }
    return mostOccurence

}
Sweeper
  • 213,210
  • 22
  • 193
  • 313
  • Is there a shorthand(high order function) of solving this problem rather than combination of using `for` loop and `if` condition? – casillas Feb 25 '19 at 16:55
  • 1
    @hotspring Yes, but using for loops is the fastest way I can think of. For a slower but shorter way, do `num1Dict.sorted(by: { $0.value > $1.value }).first!.key`. – Sweeper Feb 25 '19 at 16:57
  • you can also do `num1Dict.filter { $0.value == num1Dict.values.max() }.first!.key` – barbarity Feb 25 '19 at 17:11
  • @barbarity Yes, but note how that has a time complexity of O(n^2). – Sweeper Feb 25 '19 at 17:12
  • @Sweeper I think the compiler is smart enough to know `num1Dict.values.max()` doesn't change but in any case you can always do one lines: `let max = num1Dict.values.max()` and then `num1dict.filter { $0.value == max }.first!.key` – barbarity Feb 25 '19 at 17:18
  • The dictionary still needs to be iterated over twice though, which is why I said using a for loop is the fastest way I can think of. @barbarity – Sweeper Feb 25 '19 at 17:21
  • but iterating twice is `2n` which in terms of computation is O(n) – barbarity Feb 25 '19 at 17:38
  • @barbarity complexity is not the same as speed. I could have a constant O(1) operation that takes 1000 years. So unless `filter` is faster than a for loop, using a for loop is the fastest solution. You can try to do some benchmarks. I don't know. – Sweeper Feb 25 '19 at 17:41
  • @Sweeper You're over looking the fact that `nums1.map` is making an entire pass trhough `nums1`, and allocating an array of tuples. You should use `nums1.lazy.map` instead – Alexander Feb 25 '19 at 18:27
  • @Sweeper Plus, you're hand rolling an implementation of `max(by:)`, and it's actually incorrect. Rather than returning `nil` on empty arrays, it returns `0`. If you call this method and you get a `0` back, how do you know if it's "`0` as in there were no elements" and "`0` as in the most common element is `0`?" That's one extra check. That's an anti-pattern in Swift. That's what optionals are for. – Alexander Feb 25 '19 at 18:39
  • @Alexander In OP's attempt, the method returns a non-optional `Int`, so I just assumed the array is always non-empty. Good point. – Sweeper Feb 25 '19 at 18:42
  • @Sweeper That's your opportunity to guide OP in the right direction. Returning `Int` for something that can have an undefined result would be simply incorrect. – Alexander Feb 25 '19 at 18:43
1

You can use reduce(into:) to generate a Dictionary with the elements and their frequencies, then sort your array using those frequencies, then simply return the last element (based on ascending ordering) of the sorted array.

extension Array where Element: Comparable & Hashable {
    func sortByNumberOfOccurences() -> [Element] {
        let occurencesDict = self.reduce(into: [Element:Int](), { currentResult, element in
            currentResult[element, default: 0] += 1
        })
        return self.sorted(by: { current, next in occurencesDict[current]! < occurencesDict[next]!})
    }

    func elementWithHighestFrequency() -> Element? {
        return sortByNumberOfOccurences().last
    }
}

Disclaimer: the sortByNumberOfOccurences method is copied from another answer of mine.

Dávid Pásztor
  • 51,403
  • 9
  • 85
  • 116
0

The mathematical name for what you're looking for (the most frequent element in a collection) is called the mode. There could be ties (e.g. [1, 1, 2, 2, 3, 3] has 3 modes: [1, 2, 3])

If you want any one of the modes (not caring which ones, specifically), you can use Dictionary.max(by:), which you can use to find the (element, count) pair with the highest count (which is the dict value). Then, you can get the key of this pair, which will be the mode element.

extension Sequence where Element: Hashable {
    func countOccurrences() -> [Element: Int] {
        return self.reduce(into: [:]) { (occurences, element) in occurences[element, default: 0] += 1}
    }

    func mode() -> Element? {
        return self.countOccurrences()
            .max(by: { $0.value < $1.value })?
            .key
    }

    func modes() -> [Element] {
        var firstModeNumOccurences: Int? = nil
        let modes = countOccurrences()
            .sorted { pairA, pairB in pairA.value > pairB.value } // sorting in descending order of num occurences
            .lazy
            .prefix(while:) { (_, numOccurences) in
                if firstModeNumOccurences == nil { firstModeNumOccurences = numOccurences }
                return numOccurences == firstModeNumOccurences
            }
            .map { (element, _) in element }

        return Array(modes)
    }
}

print([1, 2, 3, 3, 4, 4].mode() as Any) // => 3 or 4, non-deterministic
print([1, 2, 3, 3, 4, 4].modes() as Any) // => [3, 4]
Alexander
  • 59,041
  • 12
  • 98
  • 151