Find the Index of the First Occurrence · Optimal Solution

Slide a window. Match or move on.

A search engine highlights query terms within documents by locating where each keyword first appears — but raw text offers only characters, not an index. The approach slides a window across the haystack, comparing it character-by-character against the needle. For each candidate position, match as far as you can; if every character agrees, return that position. If not, advance and try the next start. O(n · m) worst case — simple, correct, and often fast in practice.

Interactive

Watch each window succeed or fail

Concept

Every start gets a fair trial

Each valid start index defines one candidate window with the same length as the needle. The algorithm tries every window left to right, returning the first full match.

candidate windows

Start index 0 through haystack.length − needle.length. Each defines a window of needle.length characters. Any start beyond that would run past the end.

character-by-character comparison

Within each window, compare characters left to right against the needle. Stop at the first mismatch — no need to check the rest of that window.

a partial match is still a failure

A window that matches 4 out of 5 characters is not a partial success — it's a failed candidate. Only a full match counts. Keep scanning later windows.

Algorithm

Slide, compare, decide

A nested loop: the outer loop picks window starts, the inner loop compares characters.

  1. 1

    Compute the last valid start

    The last candidate window starts at haystack.length − needle.length. Any later start would run past the end of the haystack.

  2. 2

    For each start, compare character by character

    At position start, compare haystack[start + j] with needle[j] for j = 0, 1, …. Stop at the first mismatch.

  3. 3

    If all characters match — return start

    A window where every character agrees is the first occurrence. Return its start index immediately.

  4. 4

    If no window matches — return −1

    After exhausting all candidate windows without a full match, the needle does not occur in the haystack.

Edge Cases

Where windows collapse

Some inputs have very few candidate windows, or none at all.

Needle longer than haystack

When the needle is longer, no valid start index exists. The last valid start would be negative. The outer loop never runs — return −1 immediately.

Needle equals haystack

Only one window exists (start = 0), and it spans the entire haystack. If every character matches, the answer is 0. If any character differs, the answer is −1.

Single-character needle

Each window is one character wide. The comparison is a single equality check. The first matching character's index is the answer.