The next video in my iOS Interview questions series all about coding challenges explains a common question that asks you to find the most common element in an array. I have been asked to code this during a phone screen interview and on a whiteboard for an iOS position, so it’s good to know for a variety of reasons.
We solve this Swift coding challenge by iterating over an array and building a dictionary to keep count of each time we find a specific object.
As with all these coding challenges, there are MANY ways to solve this, so if you have improvements to the code please leave a comment so everyone can learn from it.
Source Code:
https://www.dropbox.com/sh/kycbbxq6lzaemi5/AABswnuuOyUfkF7rFBFuaCGoa?dl=0
Patreon:
https://www.patreon.com/seanallen
Follow me on Twitter:
https://twitter.com/SeanA0400
Instagram:
@SeanA0400
Amazon Auto Links: No products found.
+Sean Allen
Hey, I refactored my solution I commented earlier. This time I used an NSCountedSet to have a count of how many times an element appeared and compared it to the maximum recorded number. The solution is pretty straightforward IMO, please let me know what you think.
func elements(colors: [String]) ->[String]{
let set = NSCountedSet(array: colors)
var max = 1
var stringArray = [String]()
for case let color as String in set{
if set.count(for: color) > max{
stringArray.removeAll()
stringArray.append(color)
max = set.count(for: color)
}
else if set.count(for: color) == max{
stringArray.append(color)
}
}
return stringArray
}
elements(colors: [“red”, “blue”, “red”, “green”, “yellow”, “blue”, “red”, “blue”, “green”])
How you got all that knowledge man ?
Here’s my one loop attempt:
import Foundation
var colors = [“red”, “blue”, “red”, “blue”, “yello”, “blue”, “green”, “red”]
var maxCount = 0
var topArray = [String]()
let countDictionary = colors.reduce(into: [String: Int]()) {
$0[$1, default: 0] += 1
if let count = $0[$1], count > maxCount {
topArray = [$1]
maxCount = count
} else if $0[$1] == maxCount {
topArray.append($1)
}
}
print(countDictionary)
print(topArray) // here is the answer
I’m try return all highest colours with filter.
func getMostCommonColor(array: [String]) -> [String] {
var colorDictionary: [String: Int] = [:]
array.forEach({ colorDictionary[$0] = (colorDictionary[$0] ?? 0) + 1 })
return colorDictionary.filter { $1 == colorDictionary.values.max() }.map { $0.key }
}
func getMostCommonColor(array: [String]) -> [String] {
let uniqueColors = Set(array)
typealias ColorFrequency = (color: String, count: Int)
var colorFrequencies: [ColorFrequency] = []
for color in uniqueColors {
let colorFreq = ColorFrequency(color: color, count: array.filter{$0 == color}.count)
colorFrequencies.append(colorFreq)
}
let maxFrequency = colorFrequencies.max(by: {$0.1 < $1.1}).map{$0.count} return colorFrequencies.filter{$0.count == maxFrequency}.map{$0.color} } getMostCommonColor(array: colorArray)
dictionary in Swift has default value if key doesn’t exist so we can use
dic[color, default: 0] += 1. just in one line instead of 4 lines of code
hey allen ive been a fan of yours for a while now. is there any way I can contact you regarding a hw Im working on? im having problems adding an element to an array from a detail view. Its overriding the last element in the array and idk wtf is going on ive been trying to solve this for 2 days now! thankssss
import Foundation
var arr = [“red”, “green”, “green”, “black”, “blue”, “yellow”, “red”, “green”, “yellow”, “red”, “red”, “green”, “green”, “grey”, “purple”, “orange”, “grey”, “blue”, “red”, “green”, “yellow”, “orange”, “purple”, “black”, “red”, “blue”, “green”, “orange”, “blue”, “white”, “yellow”, “blue”, “red”, “green”, “orange”, “purple”, “blue”, “black”]
var hash = [String: Int]()
var values = [(String, Int)]()
arr.forEach {
let val = hash[$0] ?? 0
hash[$0] = val + 1
}
var max = hash.max {
return $0.1 < $1.1 } print(max)
Genuinely so refreshing to find someone teaching Swift & iOS development with clarity and a bit of enthusiasm! Have already learnt so much from you. Thank you and please don’t stop! If I start making some money from iOS development in future I will definitely support your Patreon, but for now, the best I can do is subscribe here on YouTube. 🙂
+Sean Allen
Hey Sean,
I was thinking about this problem today and found an even shorter solution than using NSCountedSet. It does use a high order function of mapping over the colors to create tuples of the color as the first element of the tuple and the number 1 as the second element of the tuple. I then convert the tuples into a dictionary and add 1 to the value for every time the element appears in the dictionary, to create a key value pair of the color with how many times the color appears in the dictionary. I then get the maxValue of the dictionary, and loop through it to find every key that has the maxValue (in case there are any ties for first place) and append it to an array that I return at the end of the loop. Check it out!
func mostCommonColor(colors: [String])->[String]{
let tupleOfColors = colors.map{($0, 1)}
let dictOfColors = Dictionary(tupleOfColors, uniquingKeysWith: +)
let maxValue = dictOfColors.values.max()
var array = [String]()
for (key, values) in dictOfColors{
if dictOfColors[key] == maxValue!{
array.append(key)
}
}
print(array)
return array
}
Hey Sean, great tutorial very well done. Just to add for bit more medium level iOS Developers instead of doing the second for loop, I would do something as it follows:
func getMostCommonColor(array: [String]) -> [String] {
var topColors: [String] = []
var colorDictionary: [String: Int] = [:]
for color in array {
if let count = colorDictionary[color] {
colorDictionary[color] = count + 1
} else {
colorDictionary[color] = 1
}
}
let highestValue = colorDictionary.values.max()
let colors = colorDictionary.filter { (color, count) -> Bool in
return count == highestValue
}
topColors = colors.map{$0.key}
return topColors
}
Using bit of functional programming shows a bit of knowledge on it which i suppose it gives good impression. Let me know what you think.
Hi folks my solution looks a bit different, but im in linear complexity, because im using only one loop
func getMostCommon(in array: Array) -> T? {
var mostCommon: T = array.first!
var counter = -1
var counterDict: [T: Int] = [:]
for elem in array {
if let entry = counterDict[elem] {
let updateEntry = entry + 1
counterDict.updateValue(updateEntry, forKey: elem)
if updateEntry > counter {
mostCommon = elem
counter = updateEntry
}
} else {
counterDict[elem] = 1
}
}
return mostCommon
}
Seems like you could use “reduce” for color counts.
How about this?
func getMostCommonElement(array: [Int]) -> (element: Int, repetitions: Int) {
let set = NSCountedSet()
set.addObjects(from: array)
var max = 0
var maxElement = 0
for elem in array {
let count = set.count(for: elem)
if count > max {
max = count
maxElement = elem
}
}
return (maxElement, max)
}
Someone please correct me if I’m wrong, but I don’t think you need to iterate over the values in the dictionary at all, just keep 2 local variables called max element and max count and check that through each iteration. This would be a true O(n) and not O(n+k) (where k is the number of elements that are duplicates). Also it might be worth noting in the interview that this requires O(n) space complexity (in case there are possible solutions that are 0(1) space complexity. Here’s what mine looks like:
func mostCommonElement(_ elems: [T]) -> T? {
var maxCount: Int = 0
var maxElement: T? = nil
var map: [T: Int] = [:]
for elem in elems {
if let occurrence = map[elem] {
map[elem] = occurrence + 1
} else {
map[elem] = 1
}
if map[elem]! > maxCount {
maxElement = elem
maxCount = map[elem]!
}
}
return maxElement
}
top quality video, as always…but now… you got a top quality beard, noice
You could also create an extension to Array.
colors.mostCommonElement()
extension Array where Element: Hashable {
func mostCommonElement() -> [Element] {
var topElements = [Element]()
var amountPerElement = [Element: Int]()
self.forEach { item in
if let count = amountPerElement[item] {
amountPerElement[item] = count + 1
} else {
amountPerElement[item] = 1
}
}
let max = amountPerElement.values.max()
for (item, count) in amountPerElement {
if amountPerElement[item] == max {
topElements.append(item)
}
}
return topElements
}
}
wouldn’t something similar to:
colorArray.filter{$0 == element}.count
work?
Hey Sean, I think you could also solve this problem using MapReduce, like in this tutorial https://useyourloaf.com/blog/swift-guide-to-map-filter-reduce/
Could you solve the same problem using this if that is possible?
Sean I really liked the way you explained the above question in such a easy manner and I too faced this question in some interview
Good solution. I got a couple of tips for ya.
Depending on the role/company you’re going for, you mightn’t be allowed to use Swift’s Dictionary functionalities such as iterating through a dictionary. I personally assume that I’m writing code which has limited functionality, such as C or Java, but with Swift syntax.
Instead of the second array iteration, you could use two variables (topCount, topColor) which keeps record of the most common count of each element and then change/append the output array if its higher/same.
You also might want to state the time/space complexity for extra browny points.
Also, don’t forget to validate your input data. Checking for empty arrays and throwing an exception, etc…
***********Objective C Solution************
//Global Variables
NSMutableDictionary *colorsDict;
NSInteger timesNumber;
NSString *finalColor;
//viewDidLoad
colorsDict=[[NSMutableDictionary alloc] init];
[self getHighestOfColors:@[@”voilet”,@”blue”,@”red”,@”pink”,@”red”,@”blue”,@”green”,@”blue”,@”red”,@”red”,@”red”,@”orange”,@”green”,@”orange”,@”red”,@”green”,@”red”,@”blue”,@”orange”,@”blue”,@”green”,@”red”,@”voilet”,@”red”,@”red”,@”voilet”,@”orange”,@”blue”,@”red”]];
// and here final method
-(void)getHighestOfColors:(NSArray*)colorsArray {
for (NSString *color in colorsArray) {
if (colorsDict[color]) {
NSInteger count=[colorsDict[color] integerValue];
count=count+1;
[colorsDict setValue:[NSNumber numberWithInteger:count] forKey:color];
if (count>=timesNumber) {
timesNumber=count;
finalColor=color;
}
} else {
[colorsDict setValue:[NSNumber numberWithInteger:1] forKey:color];
}
}
NSLog(@”nColors Array=%@nMax Color=%@nMax Color Count=%ld”,colorsDict,finalColor,(long)timesNumber);
}
Sean++
I’m assuming the time complexity is O(n) n being the initial colours array?
This one is a tad shorter, 8 lines instead of 17. (Did not count whitespace 😉
func getMostCommonColor(array:[String]) -> String {
var counters = [String: Int]()
for c in array {
counters[c] = (counters[c] ?? 0) + 1
}
let maxElement = counters.reduce(counters.first!) { $1.1 > $0.1 ? $1 : $0 }
return maxElement.0
}
If one would return a list of all the colors sorted by popularity, one could just
return counters.reduce(counters.first!) { $1.1 > $0.1 ? $1 : $0 }
thus shaving off another line of code.
Anyway, great videos, keep em coming! 🙂
Hello Sean,
It can be cleaner if you replace ‘colorDictionary[color]’ with ‘count’ on line 27.
I guess you find out while you making editing.
Thanks for greats videos!
It would be interesting to do this without calling max on the values but instead updating the highest value as you loop through each color in the dictionary. I might try it. Great video!
Another way by using the new grouping initializer for Dictionaries of Swift 4:
func getMostCommonColor(array: [String]) -> String {
let groupedDic = Dictionary(grouping: array, by: { $0 })
let newDic = groupedDic.mapValues() { $0.count }
return newDic.sorted(by: { $0.value < $1.value }).last?.key ?? "" }
probably it doesn’t make any difference in execution time, but what about shorter form like this?
colors.forEach { (color) in
colorsDictionary[color] = (colorsDictionary[color] ?? 0) + 1
}
sir if most repeated number is zero then it doesn’t work . how to solve this problem
thank you
let colorArray : [String] = [“red”, “green”, “red”, “blue”,”green”];
func mostcommonColor(colors : [String]) -> [String]{
let colorsWithCount = colors.map{($0, 1)}
let colors = Dictionary(colorsWithCount, uniquingKeysWith: +)
let maxValue = colors.values.max()
return Array(colors.filter({$0.value == maxValue}).keys)
}
print(mostcommonColor(colors: colorArray))
Great video. I wish I could find info on how to deal with ties. Any clue on how you would return the first element in your array in case of ties. Meaning if you ran your function on this array, [green, red, red, green]. It would obviously be a tie but I’d like to return the first element in the array that we initially sorted through. I’ve been trying to do this with an array of Ints. Having myarray = [1,2,3,4] will return a 4. My hope is to get a return of 1 because that was my initial element in myarray.
Any insight?