All indexes of repeating elements in array

Hi,
I'm trying to get all the indexes of a duplicate element with the following extension. Which takes O(n). I'm worndering, if there is any O(1) solution for the same.

extension Array where Element:BinaryInteger {
    func allIndex(of i:Int ) -> [Int]? {
        var ret = [Int]()
        for (idx,item) in self.enumerated() {
            if (item == i) {
                ret.append(idx)
            }
        }
        return ret
    }
}

let data:[Int] = [5,7,4,-3,9,1,10,4,5,8,9,3]
//print(data)

print("index \(data.allIndex(of: 9)!)")
// index [4, 10] 

2nd part of the question is, is there a way to get the indexes using the filter method?

No, but you can use filter on enumerated sequence, or even on the indices:

extension Array where Element: Equatable {
  func allIndices(of value: Element) -> [Index] {
    indices.filter { self[$0] == value }
  }
}

I'd suggest that question like this be asked over stackoverflows. It's quite off-topic for this forum, but the answer is no. Unless the array has some special structure, O(n) is about as low as you get.

Edit:
change function signature slightly.

2 Likes

Thanks @Lantua

Also, you'd never return nil, even in your algorithm. If the array doesn't contain value, it'll just return an empty array (of indices). So you can simply return [Index] instead of [Int]?

3 Likes

@Lantua Thanks for this trick. I was wondering why you are using self[$0] instead of $0. Array.indices returns Range<Int> and you are indexing it on the array with this Range index. Please correct me if I am wrong with my understanding.

I think the best way to understand this is not to think of it in terms of the return type but instead of the associated type. It'd help you when working with other collections, like Set or Dictionary.

Since Array conforms to the Collection protocol, Array.indices returns a value of type Indices, which is a collection containing all valid indices. So when I do indices.map { i in }, each i is a valid index for this collection. Since you're comparing the value of the array with the target, you instead use self[i], which is a value in the collection, instead of i, which is an index to the value in the collection.

Note that my code above works with any equatable Element, instead of Int, so you'll easier see the type mismatch when you're comparing the value (Element) with the index (Int).

1 Like

A recently approved, but not added to a public release, library deals with discontiguous index ranges. One of the extension methods to Collection is this.

@CTMacUser Link is missing. Can you please edit or share the link.

It's at Apple's GitHub site as RangeSet.