Count max consecutive integers in array

this is a first shot in Swift. Easy to convert to C. But should be optimzed.

var maxSeqLength = 1
var bestSeqLength = 1
var maxSeq = Set()
var bestSeq = Set()
let theArray =  [3, 5, 6, 7, 11, 12]
for i in 0 ..< theArray.count - 1 {
    print("i", i, theArray[i+1] - theArray[i])
    if theArray[i+1] - theArray[i] == 1 {
        maxSeqLength += 1
        maxSeq.insert(theArray[i])
        maxSeq.insert(theArray[i+1])
        if maxSeqLength > bestSeqLength {
            bestSeqLength = maxSeqLength
            bestSeq = maxSeq
        }
    } else {
        maxSeqLength = 1
        maxSeq = Set()
    }
}

print(bestSeqLength, Array(bestSeq).sorted())

Result:

3 [5, 6, 7]

Slightly better:

var maxSeq = (length: 1, val: Set())
var bestSeq = maxSeq
let theArray =  [3, 5, 6, 7, 11, 12]
for i in 0 ..< theArray.count - 1 {
    if theArray[i+1] - theArray[i] == 1 {
        maxSeq = (length: maxSeq.length + 1, val: maxSeq.val.union([theArray[i], theArray[i+1]]))
        if maxSeq.length > bestSeq.length {
            bestSeq = maxSeq
        }
    } else {
        maxSeq = (length: 1, val: Set())
    }
}

print(bestSeq.length, Array(bestSeq.val).sorted())

This cards array is an array of card objects with values of as follows:

2,3,4,10,11

The result for bestseq is 10,11

NSInteger maxSeqLength = 1;
    NSInteger bestSeqLength = 1;
    NSMutableArray *maxSeq = [NSMutableArray new];
    NSMutableArray *bestSeq = [NSMutableArray new];
    
    // cycle
    for(NSInteger i = 0; i < cards.count - 1; i++){
        NSLog(@"i: %ld ", (long)i);
        
        // vars
        Card *thisCard = [cards objectAtIndex:i];
        Card *nextCard = [cards objectAtIndex:i+1];
        
        // check
        if((nextCard.value - thisCard.value) == 1){
            // set
            maxSeqLength += 1;
            [maxSeq addObject:thisCard];
            [maxSeq addObject:nextCard];
            
            // check
            if(maxSeqLength > bestSeqLength){
                // set
                bestSeqLength = maxSeqLength;
                bestSeq = maxSeq;
            }
        }
        else{
            // set
            maxSeqLength = 1;
            [maxSeq removeAllObjects];
        }
    }

With the code I proposed, I get the correct result:

var maxSeq = (length: 1, val: Set())
var bestSeq = maxSeq
let theArray =  [2,3,4,10,11]
for i in 0 ..< theArray.count - 1 {
    if theArray[i+1] - theArray[i] == 1 {
        maxSeq = (length: maxSeq.length + 1, val: maxSeq.val.union([theArray[i], theArray[i+1]]))
        if maxSeq.length > bestSeq.length {
            bestSeq = maxSeq
        }
    } else {
        maxSeq = (length: 1, val: Set())
    }
}
 
print(bestSeq.length, Array(bestSeq.val).sorted())

3 [2, 3, 4]

I see a potential problem in your code.

As maxSeq and bestSeq are Array and not Set, when you addObject at lines 18 and 19, you may add some objects twice.

But that does not explain the result.

Could you add log to trace what happens.

At line 9 and 20 to log maxSeq and bestSeq

At line 25 to log bestSeq and maxSeq

I am not fluent in objc, but I suspect that when you write

bestSeq = maxSeq;

you copy a reference of object? From now on, they are the same objects.

You need to copy the content of maxSeq in bestSeq

something like

bestSeq = [maxSeq copy] // I'm really not fluent in objc

Consider the affect of this line:

bestSeq = maxSeq;

It resets the pointer of 'bestSeq' to the array maxSeq. As such, whenever you change maxSeq you will change bestSeq. What you want is to reset bestSeq to an array that contains the current contents of maxSeq, not to point to maxSeq. Try to understand this and figure out how to correct that line.

Yes, that's why I advised (if that's the correct objc syntax)

bestSeq = [maxSeq copy]

You gave away the answer! (Give or take an ending ";")

Since the array is mutable, I prefer mutating it rather than redirecting it. You don't need to create a new mutableDictionary and trash the old one and you don't need to copy a bunch of objects:

[bestSeq setDictionary:maxSeq];

Thanks.

In Swift I've been trained to forget the ending ';' of the old Pascal times !

We finally get to do what Dilbert's boss wanted and not overuse the semicolons. 🙂

hi,

i think your question has been answered quite well by Claude31, but i've looked back at this question several times -- just for fun -- and would offer alternative views ... in Swift, however (because my Objective C is a little rusty).

let's say the array under consideration is

let x = [2,3,5,6,7,8,10,11,12,13,17,20,21,22,23,24]

option 1: (based on the fact that the array consists of integers and is sorted)

consider a second array in which the index of each element is subtracted from each element. if you have a sequential run, then the run will stick out in the second array as equal integers. in this case, you would have

[2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 7, 9, 9, 9, 9, 9]

so we could have a slightly different question -- count the longest run of the same integer. the solution here is not much different.

nevertheless, let's use these values to build a dictionary of the elements of x, keyed by this second list of values. there's a fancy, functional way to do this in Swift (1 line of code), but a procedural way to do this is the following (and this should convert to Objective C without too much trouble)

var dict = Dictionary<int,[int]>()
for index in 0...(x.count-1) {
  let key = x[index]-index
  if dict[key] == nil {
    dict[key] = [Int]()
  }
  dict[key]!.append(x[index])
}

now you have all the runs identified:

for key in dict.keys {
  print(dict[key]!.sorted(by: < )
}

yes, this is more info than what you needed -- you only asked for the longest run and it's easy to go from here.

option 2: (recursive)

build a simple routine that identifies the longest run at the beginning of the array, and compares that recursively with the length of the longest run in what remains. under the hood, this is the same type of code solution from Claude31, except that the book-keeping is a lot simpler.

func longestRun(array x: [Int]) -> Int {
  if x.count < 2 {
    return x.count
  }
  // look through the array starting from the beginning for the first
  // element that breaks a sequential run.  that is, find the first
  // index with a = x[index] and b = x[index+1] where b != a + 1.
  // if found, the array has an opening run of length index+1, and
  // we can recursively find the longest run among elements starting at b.
  // simply report the larger of the two.
  for index in 0...(x.count-2) {
    if x[index] + 1 != x[index+1] {
      let xRemainder = Array(x[(index+1)...(x.count-1)])
      let n = longestRun(array: xRemainder)
      return max(index+1, n)
    }
  }
  // if no such sequential break was found, the array is already a sequential run
  return x.count
}

print(longestRun(array: x))

this prints 5. with not too much work, you could return the actual run from the array -- the return type would be [Int], and you'd return either the beginning of x or xRemainder, whichever was longer.

hope that's of interest,

DMG