How to sort array of integer first by value and second by number of repetition using swift in time complexity < O(n^2) and space complexity O(n)

Question

This is the solution I had tried but It was in the order of O(n^2) so didn't passed the test result

func sortArrayByValueAndByFrequency(nums : [Int]) {
    var countDict = [Int : Int]()
    var count  = Int()
    var values = Int()
    var output = [Int]()
    for index in 0 ..< nums.count {
        for index2 in 0 ..< nums.count{
            if nums[index2] == nums[index] {
                values = nums[index2]
                count += 1
            }
        }
        countDict[values] = count

        count = 0
    }

    let sortedByKey = countDict.sorted { ($0.key < $1.key)}
    let sortedByValue = sortedByKey.sorted { ($0.value < $1.value)}
    for (k,v) in sortedByValue {
        for _ in 1 ... v {
            output.append(k)
        }
    }

    output.forEach { (orderedNumber) in
        print(orderedNumber)
    }
}

Example input/output:

Example array = [1,1,2,3,4,5,5,6,7,7,7,8,9,9,9,20,25,21,20]
Expected output = [2,3,4,6,8,21,25,1,1,5,5,20,20,7,7,7,9,9,9]

example 2 = [1,2,3,4,4,3,3]
output = [1,2,4,4,3,3,3]

This question was asked to me on HackerRank

Your title is backwards. Given your example array and example output, the title should state "first by number of repetition, then second by value". — rmaddy, Jul 07 '18 at 23:01
Whatever helps to solve the problem, But I think I am first sorting by value with repetition 1 then sorting by value for higher number of repetition. — Ashim Dahal, Jul 07 '18 at 23:06
Your output is sorted by repetition count. Then for those with the same repetition count, you sort by value. That's the opposite of your title. If the sort was being done as written in your title, the 2nd part would be irrelevant because the whole array would be sorted by value which would simply put it in plain numerical order. — rmaddy, Jul 07 '18 at 23:11

score 4 · Accepted Answer · answered Jul 07 '18 at 23:07

4

First determine the number of occurrences of each value (O(n)), then sort the values, with the number of occurrences as the first sort criterion, and the value itself as the second sort criterion (O(n log(n))). The sorting is conveniently done with a tuple-comparison (compare Swift - Sort array of objects with multiple criteria):

let array = [1,1,2,3,4,5,5,6,7,7,7,8,9,9,9,20,25,21,20]

let countDict = array.reduce(into: [Int:Int]()) {
    $0[$1, default: 0] += 1
}

let sorted = array.sorted(by: {
  (countDict[$0]!, $0) < (countDict[$1]!, $1)
})

print(sorted)
// [2, 3, 4, 6, 8, 21, 25, 1, 1, 5, 5, 20, 20, 7, 7, 7, 9, 9, 9]

answered Jul 07 '18 at 23:07

Martin R

529,903
94
1,240
1,382

This wouldn't be `O(1)` but rather `O(n)` space though? Although that constraint does seem a bit weird. – dfrib Jul 07 '18 at 23:12
@dfri: You are right, an additional dictionary is needed as in the code in the question. I must admit that I hadn't noticed that restriction in the title. – Martin R Jul 07 '18 at 23:14
Even Swifts own sorting would fail that criteria, if I'm not mistaken (partly quicksort?), so unless OP's challenge covers writing sorting algorithms, it's arguably a mistake (or lack of details) in that restriction. – dfrib Jul 07 '18 at 23:20
@dfri: It is introsort (a variant of quicksort), compare https://stackoverflow.com/q/27677026/1187415. That needs only O(1) storage if I remember correctly. – Martin R Jul 07 '18 at 23:24
I recall quicksort needing `O(log n)` for space, but I might be mistaken. Anyway, I would guess this was the answer OP was looking for, in lack of additional details anyway. Tuple-sorting was neat :) – dfrib Jul 07 '18 at 23:27
Space of O(n) is good for this problem but swift inbuild sorted will fail the test case – Ashim Dahal Jul 07 '18 at 23:28
1

@AshimDahal if so, consider updating the title of your question removing the `O(1)` space restriction, as well as providing a link to the problem you are trying to solve (Hackerrank / etc?). – dfrib Jul 07 '18 at 23:30
@dfri have updated the title, It was asked to me on Hackerrank but I don't have link to it. It was given to me as part of coding challenge. – Ashim Dahal Jul 07 '18 at 23:34
@AshimDahal: There can be various reasons why test cases fail on Hackerrank. I had it once that the standard method of reading and splitting lines and converting them into integers was too slow. Without additional information (such as how large the array is, what the time limit is) it is difficult to give further advice. – Martin R Jul 07 '18 at 23:37
Will using `reduce` for the dictionary population have a non-negligible overhead (say, for large arrays) due to dictionary copying (as compared to empty-initialization followed by population e.g. in a loop) or is this elided somehow? – dfrib Jul 07 '18 at 23:40
@dfri: [`reduce(into:_:)`](https://developer.apple.com/documentation/swift/array/2924692-reduce) was specifically made to *avoid* the dictionary copying: [SE-0171 Reduce with inout](https://github.com/apple/swift-evolution/blob/master/proposals/0171-reduce-with-inout.md) – Martin R Jul 07 '18 at 23:42
@MartinR Ah, I’m not really up to date with Swift 4 and I missed the `into` label. Thanks! – dfrib Jul 07 '18 at 23:43
@dfri & MartinR, Do you guys know what is the time complixity of sorted function in swift 3 or swift 4 – Ashim Dahal Jul 07 '18 at 23:54
@AshimDahal - The [source](https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift.gyb) will tell you the algorithm used; then your favourite ADT book, or failing that Wikipedia, will tell you the time complexity. – CRD Jul 08 '18 at 19:39

How to sort array of integer first by value and second by number of repetition using swift in time complexity < O(n^2) and space complexity O(n)

1 Answers1