Adjacent Unique Sequences

1. Think about how you can solve this in one pass using the concept of ‘states’ and history.

2. Try playing around with the idea of how you can solve this logically by simulating the behavior of an “unordered stack.”

3. Consider a single state where unique element mapped to its current count (mod 2).

Algorithm Description

Consider a state $s_k$ of traversal, with each unique element mapped to its current count (mod 2). Note: before traversal our $s_0$ is an empty map as no elements have been seen, which is an implicit $s_0 = \{e_1 : 0, e_2 : 0, ..., e_k : 0\}$. Traverse the sequence one element at a time, each time creating a new $s_k$ with the updated count. For each $s_k$, hash all states into a statelookup to allow efficient collision detection. If we reach some $s_k = s_j,j < k$, return false, as we have found a nonempty adjacent subsequence with no unique element. Upon traversing to the end of the list, return true as none was found.

Note for coding: Because we are using a unique element mapped to its current count (mod 2). We can effectively store each state in a HashSet as the field of integers modulo 2 (similar to $GF(2)$) which only contain elements 0 and 1 which is essentially equivalent to the same state that can be modeled by a HashSet.

Proof of Correctness

Consider the state collision $s_k=s_j,j < k$, and the elements traversed $[e_1, e_2,...,e_j,e_{j+1},...,e_k,...]$. To go from $s_j$ to $s_k$, we have processed the new elements $e_{j+1},...,e_k$. Because $s_k = s_j, j \neq k$, we know that for all $s_k :e_j = a \pmod 2$, $s_j : e_j = a \pmod 2$. This means that the element path between the two states contains no unique element. This element path is nonempty bceause $j \neq k$. Trivially, the path between the two states is an adjacent subsequence, and therefore we have found a nonempty adjacent subsequence that contains no unique element.

If we traverse the list with no such collision, there is no such path and therefore no such nonempty adjacent subsequence that contains no unique element.

Time and Space Complexity

Time: $~O(N)$, we do one pass through out list.

Space: $O(kN)$, for $k$ unique elements, as worst case we store every state with each unique element.

Sample Solution

import java.util.HashSet;

public boolean adjacentSequences(int[] s) {
  HashSet<HashSet<Integer>> previousStates = new HashSet<>();
  HashSet<Integer> currState = new HashSet<>();
  previousStates.add(currState); //empty state
  for (int i = 0; i < s.length; i++) {
      int e = s[i];
      if (currState.contains(e)) { // if current count (mod 2) == 1
          currState.remove(e);
      } else { // if current count (mod 2) == 0
          currState.add(e);
      }
      HashSet<Integer> currStateClone = (HashSet<Integer>) currState.clone(); //SEE NOTE
      if (!previousStates.add(currStateClone)) { //if we have reached this state before
          return false;
      }
  }
  return true;
}

NOTE: We make a copy of the set to get around the fact that when we add currState to previousStates, a pointer to currState will be added. This is because currState is a HashSet Object and when mutated, previousStates will also be mutated.

However, this means in the worst case scenarios the code above will actually run in $O(N^2)$ time on certain inputs such as [1, 2, 3, 4, 5]. To truly run in $O(N)$ time, we can hash our current state as a primitive variable type, such as an integer, but the code given above is good enough for most normal-use cases and is much easier conceptually to understand.