Find Index First Occurrence LeetCode: Walkthrough

LeetCode 28, Find the Index of the First Occurrence in a String, asks you to implement what every language already gives you for free. Python has find(), Java has indexOf(), C has strstr(), and JavaScript has indexOf(). But the point of this problem is not to call a built-in — it is to understand the mechanics underneath.

This is one of the most straightforward string problems on LeetCode, yet it tests fundamentals that come up in harder problems later. If you can write a clean brute-force substring search, you have the foundation for KMP, Rabin-Karp, and other advanced string algorithms.

In this walkthrough, we will break down the find index first occurrence leetcode problem step by step, cover the brute force that interviewers expect, and explain why you should not reach for KMP unless explicitly asked.

You are given two strings: haystack and needle. Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. That is the entire problem statement.

The naming comes from the old C function strstr(), which searched for a substring (the needle) inside a larger string (the haystack). LeetCode 28 was originally called "Implement strStr()" before being renamed to its current, more descriptive title.

The constraints are generous: both strings contain only lowercase English letters, haystack length is up to 10,000, and needle length is up to 10,000. This means even an O(m*n) brute force runs comfortably within time limits.

The brute force approach is straightforward: for each starting position i in haystack (from 0 to len(haystack) - len(needle)), check whether the substring starting at i matches needle character by character. If all characters match, return i. If you exhaust all positions without a match, return -1.

In Python, this is almost a one-liner: compare haystack[i:i+len(needle)] == needle for each valid i. In Java or C++, you write a nested loop where the outer loop iterates over start positions and the inner loop compares characters.

The time complexity is O(m * n) where m is the length of haystack and n is the length of needle. The space complexity is O(1) since you only use a couple of index variables. For the constraints given (both up to 10,000), this is roughly 100 million operations in the worst case — fast enough.

Using haystack.find(needle) in Python or haystack.indexOf(needle) in Java technically solves the problem in one line. Some interviewers accept this as a starting point, but most will immediately ask you to implement it manually. The built-in exists to test whether you understand what happens inside.

The manual implementation demonstrates that you can handle index arithmetic, boundary conditions, and early termination. These are the same skills that come up in sliding window, two pointers, and other string manipulation problems.

If you open with the built-in, follow up immediately by saying you know it is O(m*n) internally (or O(m+n) with optimized implementations) and offer to write the explicit loop. This shows awareness without wasting time.

Let us trace through the two examples from the problem to see exactly how the brute force works.

Example 1: haystack = "sadbutsad", needle = "sad". Start at i=0: compare s==s, a==a, d==d — full match. Return 0. We find the answer at the very first position. Note that "sad" also appears at index 6, but we return the first occurrence.

Example 2: haystack = "leetcode", needle = "leeto". Start at i=0: compare l==l, e==e, e==e, t==t, c!=o — mismatch at position 4. Try i=1: e!=l — mismatch immediately. Continue through i=2, i=3, etc. No position produces a full match, so return -1.

Notice how the brute force short-circuits: the moment a character mismatches, it moves to the next starting position. In practice, most comparisons fail on the first or second character, making the average case much faster than the O(m*n) worst case.

Edge cases for this problem are simple but important to verify. An empty needle should return 0 — this matches the behavior of strstr and indexOf in all major languages. If needle is longer than haystack, there is no possible match, so return -1 immediately.

When needle equals haystack exactly, you return 0. When there are multiple occurrences, you return the index of the first one. The brute force naturally handles this because it iterates from left to right and returns on the first match.

One subtle boundary: make sure your outer loop runs from i=0 to i=len(haystack)-len(needle), inclusive. Off-by-one errors here are the most common bug in interview submissions for this problem.

LeetCode 28 is a foundation problem for string matching. The brute force O(m*n) approach is the baseline that every more advanced algorithm improves upon. KMP achieves O(m+n) by precomputing a failure function that avoids redundant comparisons. Rabin-Karp uses hashing to skip positions quickly.

But for interviews, the brute force is what is expected and accepted. Spending 15 minutes implementing KMP correctly under pressure is risky, and interviewers know it. Save KMP for system design discussions about text search engines, not for a 20-minute coding round.

This problem also reinforces clean index management — a skill that transfers directly to sliding window, two pointers, and substring problems like Longest Substring Without Repeating Characters (#3) and Minimum Window Substring (#76). Practice the fundamentals with YeetCode flashcards to build recall that sticks.