Check if one array contains another array in order

Question

Function that checks if one array contains elements of another array but in order?

[1,2,3,4,5] -> [3,5] gives true
[1,2,3,4,5] -> [5,2] gives false

Is it possible to make the solution optimised?

Answer 1

The solution is to step through the arrays in a staggered way. That way the complexity is O(n) rather than O(n²):

extension Sequence where Element: Equatable {
    func containsInOrder<S1>(_ arr: S1) -> Bool where S1: Sequence, S1.Element == Element {
        var it = makeIterator()
        var it1 = arr.makeIterator()
        var v = it.next()
        var v1 = it1.next()
        while v != nil, v1 != nil {
            if v == v1 {
                v1 = it1.next()
            }
            v = it.next()
        }
        return v1 == nil
    }
}

Use it like this:

[1,2,3,4,5].containsInOrder([3, 5])  // true
[1,2,3,4,5].containsInOrder([5, 3])  // false
"Hello World!".containsInOrder("HW") // true

Updated for Sequences...

Answer 2

You can think of AnyIterator as a "pauseable sequence", which can resume execution after an operation on an element.

That's helpful for this problem, because you can think of the solution as, "for every element in the second sequence, search for a match in the remaining iterations of the first sequence".

extension Sequence where Element: Equatable {
  /// Whether this sequence contains all the elements of another, in order.
  func isOrderedSuperset<Elements: Sequence>(of elements: Elements) -> Bool
  where Elements.Element == Element {
    elements.allSatisfy(AnyIterator(makeIterator()).contains)
  }
}

XCTAssert([-10, 1, 2, 5, 2, 3, 0, 4, 6, 9, 5, 4].isOrderedSuperset(of: 1...5))
XCTAssert("??".isOrderedSuperset(of: "??"))
XCTAssertFalse("??????".isOrderedSuperset(of: "??????"))
XCTAssertFalse(
  CollectionOfOne(true).isOrderedSuperset(of: [true, false])
)

---

It's actually more complex, but AnyIterator effectively looks like the following. Behaviorally, it's the same as if IteratorSequence were a reference type.

struct PauseableSinglePassSequence<Element> {
  init<Iterator: IteratorProtocol>(_ iterator: Iterator)
  where Iterator.Element == Element {
    var iterator = iterator
    _next = { iterator.next() }
  }

  private let _next: () -> Element?
}

extension PauseableSinglePassSequence: IteratorProtocol & Sequence {
  func next() -> Element? {
    _next()
  }
}

Answer 3

Just for fun. You can iterate your second collection elements and try to find the first index of each element in the first collection. If found just offset the startIndex of the next search otherwise return false:

extension Collection {
    func containsElementsInOrder<S: Sequence>(_ elements: S) -> Bool where S.Element == Element, Element: Equatable {
        var startIndex = self.startIndex
        for element in elements {
            if let index = self[startIndex...].firstIndex(of: element) {
                startIndex = self.index(after: index)
            } else {
                return false
            }
        }
        return true
    }
}

---

Usage:

[1,2,3,4,5].containsElementsInOrder([3, 4])   // true
[1,2,3,4,5].containsElementsInOrder([1, 4])   // true
[1,2,3,4,5].containsElementsInOrder([1])      // true
[1,2,3,4,5].containsElementsInOrder([])       // true
[Int]().containsElementsInOrder([])           // true
[Int]().containsElementsInOrder([1,2,3])      // false
[1,2,3,4,5].containsElementsInOrder([5,4,3])  // false
[1,2,3,4,5].containsElementsInOrder([4, 5])   // true
[1,2,3,4,5].containsElementsInOrder([4,4,5])  // false

Note that this would work for Strings and substrings as well:

"12345".containsElementsInOrder("34")               // true
"12345".containsElementsInOrder("14")               // true
"12345".containsElementsInOrder("1")                // true
"12345".containsElementsInOrder("")                 // true
"".containsElementsInOrder([])                      // true
"".containsElementsInOrder("123")                   // false
"12345".containsElementsInOrder("543")              // false
"12345".containsElementsInOrder("45")               // true
"12345"[...].containsElementsInOrder("445")         // false
"12345".containsElementsInOrder("4456".dropLast())  // false
"12345".containsElementsInOrder(["4","4","5"])      // false

Answer 4

extension RandomAccessCollection where Self: RangeReplaceableCollection, Element: Equatable {
    func containsInOrder(other: Self) -> Bool {
        (self.isEmpty && other.isEmpty) ||
        containsInOrderWithoutEdgeCases(other: other) ||
            (self.last == other.last && containsInOrderWithoutEdgeCases(other: other.dropLast()))
    }
    
    private func containsInOrderWithoutEdgeCases<C: RandomAccessCollection>(other: C) -> Bool
        where C.Element == Element {
        other.reduce(self[...]) { acc, next in
            acc.drop(while: { $0 != next }).dropFirst()
        }.isEmpty == false
    }
}

Explanation

You could find each element of the second array in the first array by using something like

firstArray.drop(while: { $0 != target }).dropFirst()

This can then be fed into a reduce function, with the first array as the initial result. If the resulting array is not empty, then the first array contains the second array's elements in order.

extension RandomAccessCollection where Self: RangeReplaceableCollection, Element: Equatable {

   func containsInOrderWithoutEdgeCases<C: RandomAccessCollection>(other: C) -> Bool
        where C.Element == Element {
        other.reduce(self[...]) { acc, next in
            acc.drop(while: { $0 != next }).dropFirst()
        }.isEmpty == false
    }
}

Note that I used self[...] to get an SubSequence from self. The reduce works on SubSequences.

There are some edge cases not handled by this, so those need to be considered too. For example, cases when at least one of the arrays are empty.

The most interesting case is that, when the last element of the second array matches the last element of the first array. In this case, reduce would give an empty result even when the first array contains the elements of the second array, in order.

Therefore, if self.last == other.last, then the elements of other except last must also be contained in self, in order. Hence we arrive at the code at the top of the answer.

Test cases

[1,2,3,4,5].containsInOrder(other: [3, 4]) // true
[1,2,3,4,5].containsInOrder(other: [1, 4]) // true
[1,2,3,4,5].containsInOrder(other: [1]) // true
[1,2,3,4,5].containsInOrder(other: []) // true
[Int]().containsInOrder(other: []) // true
[Int]().containsInOrder(other: [1,2,3]) // false
[1,2,3,4,5].containsInOrder(other: [5,4,3]) // false
[1,2,3,4,5].containsInOrder(other: [4, 5]) // true
[1,2,3,4,5].containsInOrder(other: [7, 7, 7]) // false
[1,2,3,4,5].containsInOrder(other: [7, 5]) // false
[1,2,3,4, 5, 5].containsInOrder(other: [5, 5, 5]) // false