Find the Index of the First Occurrence in a String - Problem

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.

This is a classic string matching problem where we need to find if one string exists as a substring within another string and return its starting position.

Input & Output

Example 1 — Basic Case

$ Input: haystack = "sadbutsad", needle = "sad"

› Output: 0

💡 Note: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.

Example 2 — Not Found

$ Input: haystack = "leetcode", needle = "leeto"

› Output: -1

💡 Note: "leeto" did not occur in "leetcode", so we return -1.

Example 3 — Single Character

$ Input: haystack = "hello", needle = "ll"

› Output: 2

💡 Note: "ll" occurs at index 2 in "hello", so we return 2.

Constraints

1 ≤ haystack.length, needle.length ≤ 10⁴
haystack and needle consist of only lowercase English characters.

Visualization

Tap to expand

Asked in

f Facebook 25 a Amazon 20 M Microsoft 18 G Google 15

The key insight is to systematically check each position in the haystack string to see if the needle matches starting from that position. The brute force approach works well for this problem with O(n×m) time complexity. For production code, using built-in string search methods like indexOf() or find() is recommended. Time: O(n×m), Space: O(1).

Common Approaches

✓ Brute Force - Check Every Position

⏱️ Time: O(n×m) Space: O(1)

For each position in haystack, check if needle matches starting from that position. This involves nested loops - outer loop for each starting position, inner loop to compare characters.

Built-in String Search

⏱️ Time: O(n×m) Space: O(1)

Most programming languages provide optimized built-in methods for string searching like indexOf(), find(), or index(). These are typically implemented with efficient algorithms and are well-tested.

Two Pointers with Smart Skip

⏱️ Time: O(n×m) Space: O(1)

Similar to brute force but with two pointers approach - one for haystack position and one for needle position. We can add optimizations like skipping positions when we know they won't match.

Brute Force - Check Every Position — Algorithm Steps

Step 1: Iterate through each possible starting position in haystack
Step 2: At each position, check if needle matches character by character
Step 3: If complete match found, return the starting index
Step 4: If no match found after checking all positions, return -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Position 0

Compare needle with haystack starting at index 0

Check Position 1

If no match, move to next position and compare again

Found Match

Return the index where complete match is found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int solution(char* haystack, char* needle) {
    if (strlen(needle) == 0) return 0;
    
    int haystackLen = strlen(haystack);
    int needleLen = strlen(needle);
    
    if (needleLen > haystackLen) return -1;
    
    for (int i = 0; i <= haystackLen - needleLen; i++) {
        bool match = true;
        for (int j = 0; j < needleLen; j++) {
            if (haystack[i + j] != needle[j]) {
                match = false;
                break;
            }
        }
        if (match) return i;
    }
    
    return -1;
}

int main() {
    char haystack[10001], needle[10001];
    fgets(haystack, sizeof(haystack), stdin);
    fgets(needle, sizeof(needle), stdin);
    haystack[strcspn(haystack, "\n")] = 0;
    needle[strcspn(needle, "\n")] = 0;
    int result = solution(haystack, needle);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Nested loops: outer loop runs n times, inner loop runs up to m times

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

95.1K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the Index of the First Occurrence in a String - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler