data_array

Stream Analyzer

question_mark

psychology_alt The Problem

"Reading an infinite stream of characters (e.g., G, X, A, C, X...), find the 2nd character that has not repeated so far."

Current Answer
—

Stream Controls

Manually add characters or generate a stream.

Input Stream

Count: 0
Waiting for input...

queue_music Non-Repeating List

Ordered by arrival time. Only chars with count == 1 are here.
Empty...

bar_chart Frequency Map

No data yet...
solution.js 

class StreamAnalyzer {
  constructor() {
    // Stores frequency of each char
    this.counts = {}; 
    // Stores chars that appeared exactly once, in order
    this.nonRepeating = []; 
  }

  processChar(char) {
    // 1. Update frequency
    this.counts[char] = (this.counts[char] || 0) + 1;

    // 2. Manage the non-repeating list
    if (this.counts[char] === 1) {
      // First appearance: Add to list
      this.nonRepeating.push(char);
    } else {
      // Repeated: Remove from unique list if present
      // (Note: using .filter is O(N), Linked List is O(1))
      this.nonRepeating = this.nonRepeating
        .filter(c => c !== char);
    }
  }

  getKthNonRepeating(k) {
    // k is 1-based index
    if (k > this.nonRepeating.length) {
       return null;
    }
    return this.nonRepeating[k - 1];
  }
}

How it works

To solve this efficiently, we need to maintain two pieces of information as the stream flows in:

  • Counts (Hash Map): Tracks how many times we've seen every character. This allows O(1) lookups to check if a character is new or a repeat.
  • Order (List/Queue): Maintains the sequence of characters that are currently unique.
Optimization Note: In the code above, we use a simple JavaScript Array and .filter() to remove repeating characters. This is O(N) where N is the number of unique characters. For a massive production system, you would use a Doubly Linked List combined with a HashMap pointing to the list nodes. This would allow O(1) removal of nodes when a character repeats.