Scale Engineer

Find the Index of the First Occurrence in a String

Easy
#0028Time: O(n * m)Space: O(1)19 companies
Patterns
Two PointersString Matching
Data structures
String
Companies
AccentureAdobeAmazonApple

Prompt

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

Constraints:

  • 1 <= haystack.length, needle.length <= 104
  • haystack and needle consist of only lowercase English characters.

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward approach. We iterate through the haystack with a pointer i, and for each position, we try to match the needle string. A second pointer j is used to iterate through the needle.

Algorithm

    1. Get the lengths of haystack (n) and needle (m).
    1. Handle edge cases: if m is 0, return 0. If n < m, return -1.
    1. Loop through haystack with an index i from 0 up to n - m.
    1. Inside the loop, start a second loop with index j from 0 to m - 1 to compare characters.
    1. Check if haystack.charAt(i + j) is equal to needle.charAt(j).
    1. If a character mismatch is found, break the inner loop.
    1. After the inner loop, if j has reached m, it means the entire needle was matched. Return the starting index i.
    1. If the outer loop finishes without returning, it means no match was found. Return -1.

Walkthrough

The algorithm iterates through the haystack string from the first character up to the last possible starting position for needle. The last possible starting point is haystack.length() - needle.length(). For each potential starting index i in haystack, we check if the substring of haystack starting at i matches the needle character by character. We use an inner loop to compare haystack[i+j] with needle[j]. If all characters of needle match, we have found the first occurrence, and we return the starting index i. If an inner loop comparison fails, we break out of it and continue the outer loop from the next starting position i+1. If the outer loop completes without finding a match, it means needle is not in haystack, so we return -1.

class Solution {    public int strStr(String haystack, String needle) {        int n = haystack.length();        int m = needle.length();        if (m == 0) {            return 0;        }        if (n < m) {            return -1;        }         for (int i = 0; i <= n - m; i++) {            int j;            for (j = 0; j < m; j++) {                if (haystack.charAt(i + j) != needle.charAt(j)) {                    break;                }            }            if (j == m) {                return i; // Found the needle            }        }         return -1; // Needle not found    }}

Complexity

Time

O(n * m)

Space

O(1)

Trade-offs

Pros

  • Easy to understand and implement.

  • Requires no extra space.

Cons

  • Inefficient, especially for long strings or cases with many repeated partial matches. Its performance degrades significantly in the worst-case scenarios.

Solutions

public class Solution {    public int StrStr(string haystack, string needle) {        for (var i = 0; i < haystack.Length - needle.Length + 1; ++i) {            var j = 0;            for (; j < needle.Length; ++j) {                if (haystack[i + j] != needle[j]) break;            }            if (j == needle.Length) return i;        }        return -1;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem