-1

Given an array of integers for example let array = [1, 3, 4, 7, 8, 9, 12, 14, 15] What is the best way of finding the largest amount of consecutive integers preferably without using a for-in loop. If we would pass this array into a function it would return 3 as '7, 8, 9' is the largest amount of consecutive integers.

let array = [1, 3, 4, 7, 8, 9, 12, 14, 15]

func getMaxConsecutives(from array: [Int]) -> Int {
    var maxCount = 1
    var tempMaxCount = 1
    var currentNumber = array[0]
    for number in array {
        if currentNumber == number - 1 {
            tempMaxCount += 1
            maxCount = tempMaxCount > maxCount ? tempMaxCount : maxCount
            currentNumber = number
        } else {
            tempMaxCount = 1
            currentNumber = number
        }
    }
    return maxCount
}

getMaxConsecutives(from: array)

This works as intended but I would like a more efficient solution something that is not O(n). I appreciate any creative answers.

AD Progress
  • 4,190
  • 1
  • 14
  • 33
  • 4
    It will always be O(n). There is no magic other way than to walk the whole array once. You can avoid using the word `for` and couch the loop far more elegantly but you cannot avoid walking the array. – matt Oct 31 '20 at 23:59
  • Similar question: https://stackoverflow.com/q/47137246/1974224 – Cristik Nov 01 '20 at 00:38
  • 1
    @matt In practice, that's often not the case. Say a[0] to a[100] are consecutive, and a[101] isn't. Then I would check that a[201]-a[151]=50, and if it isn't, then a sequence of 101 consecutive numbers can only start with a[152], so I check that a[252]-a[202] = 50 etc. – gnasher729 Nov 01 '20 at 00:56
  • 1
    @gnasher729 Yeah nice. That's like what I said in the last paragraph of my answer only even more short-circuity. :) – matt Nov 01 '20 at 00:58
  • @gnasher729 that’s still O(n), even if for some cases it can be done in less than n steps – Cristik Nov 01 '20 at 05:33
  • By the way, I don't understand why do some people downvote a legit question like this. I understand some programmers might not like the question but then they do not have to answer it. I think we should respect each other and try to help each other out here if we can. This is why I want to thank you all for the answers they are much appreciated. – AD Progress Nov 01 '20 at 15:00

2 Answers2

2

You can do it like this:

let array = [1, 3, 4, 7, 8, 9, 12, 14, 15]  
if let maxCount = IndexSet(array).rangeView.max(by: {$0.count < $1.count})?.count {
    print("The largest amount of consecutive integers: \(maxCount)")
    //prints 3
}
Leo Dabus
  • 229,809
  • 59
  • 489
  • 571
stackich
  • 3,607
  • 3
  • 17
  • 41
  • 1
    No need to map the elements indices into an array and/or a for loop to get the max count. `if let maxCount = IndexSet(array).rangeView.max(by: {$0.count < $1.count})?.count {` – Leo Dabus Nov 01 '20 at 01:02
  • Very nice. There’s still a loop thru the whole array! It’s just well concealed. :) – matt Nov 01 '20 at 01:45
  • @matt I think there is no built-in array-method without at least one loop concealed :D – stackich Nov 01 '20 at 01:50
  • @stackich Could you just add a simple explanation to your answer. So that others who are searching a similarly elegant way of solving a similar problem understand your solution. – AD Progress Nov 01 '20 at 14:58
  • 1
    @ADProgress my answer is just a shorten way of doing this(more readable): let indexSet = IndexSet(array) let rangeView = indexSet.rangeView let newArray = rangeView.map { Array($0.indices) } //newArray is a matrix which contains all consecutive arrays is your 'array', //so it is: [[1], [3, 4], [7, 8, 9], [12], [14, 15]] //since matrix is array of arrays, we now just have to find the largest array inside: if let maxCount = IndexSet(array).rangeView.max(by: {$0.count < $1.count})?.count {} – stackich Nov 02 '20 at 07:42
  • Thanks for the explanation. Could you add it to your answer for others. It is a piece of good learning information. – AD Progress Nov 02 '20 at 15:27
  • It was there but @LeoDabus edited to show the short way only :). I will edit again. – stackich Nov 02 '20 at 15:30
2

I think I can write it more tightly (basically as a one-liner):

let array = [1, 3, 4, 7, 8, 9, 12, 14, 15]
let (_,_,result) = array.reduce((-1000,1,0)) {
    $1 == $0.0+1 ? ($1,$0.1+1,max($0.2,$0.1+1)) : ($1,1,$0.2) 
}
print(result) // 3

But we are still looping through the entire array — so that we are O(n) — and there is no way to avoid that. After all, think about what your eye does as it scans the array looking for the answer: it scans the whole array.

(One way to achieve some savings: You could short-circuit the loop when we are not in the middle of a run and the maximum run so far is longer than what remains of the array! But the gain might not be significant.)

matt
  • 515,959
  • 87
  • 875
  • 1,141
  • Could you explain what exactly is reduce doing in this instance as I am having a hard time to follow it through. – AD Progress Nov 01 '20 at 10:39
  • 1
    It's absolutely identical to what your code is doing. That's my whole point. I can _say_ it more compactly and without the word `for`, but it is not any more "efficient". So you may as well just keep using your code. – matt Nov 01 '20 at 12:43
  • I get it is identical just cannot follow it through. I guess there is some sort of tuple going on hence the $0.2 just cannot fully figure it out. If you have a minute then could you explain the parts. I understand the ternary operator just don't understand the things like. What will be assigned to $1 and $0.2 and what is in reduce the (-1000,1,0) – AD Progress Nov 01 '20 at 14:52
  • 1
    Yes, I just translated your state variables into a tuple so that state is maintained between iterations. So $1 is your `number` (the current array element being considered), $0.0 is your `currentNumber`, $0.1 is your `tempMaxCount`, and $0.2 is your `maxCount`. – matt Nov 01 '20 at 15:05
  • and the -1000 is just a random number to represent tempMaxCount – AD Progress Nov 01 '20 at 15:07
  • 1
    It's a big negative number to represent the initial value of `currentNumber` so that no matter what the first element of the array is, it won't be in sequence with it. – matt Nov 01 '20 at 15:08
  • Thanks @matt. I like both of the answers. Would you agree if the 25 points goes to stackich as he does not have a lot yet? – AD Progress Nov 01 '20 at 15:12
  • 1
    Absolutely (it's your question, do as you please), but please keep in mind that neither answer does the thing you asked for, because, as I am trying to impress upon you, the thing you are asking for is impossible. The answer will _always_ be O(n). Both answers loop through the array and both are O(n). They are the same as your code, but in disguise. – matt Nov 01 '20 at 15:13
  • That is good to know. This was a challenge which I set to myself and I thought it can be improved somehow. But I am glad to know that it is the most efficient way possible. Apart perhaps from the short-circuit method but that would take away readability and make the code even harder to understand not mentioning to follow mentally :) without gaining much on efficiency. So thanks again for your input and have a fantastic day! – AD Progress Nov 01 '20 at 15:17